  In this paper, we study a problem of detecting the source of diffused
information by querying individuals, given a sample snapshot of the information
diffusion graph, where two queries are asked: {\em (i)} whether the respondent
is the source or not, and {\em (ii)} if not, which neighbor spreads the
information to the respondent. We consider the case when respondents may not
always be truthful and some cost is taken for each query. Our goal is to
quantify the necessary and sufficient budgets to achieve the detection
probability $1-\delta$ for any given $0<\delta<1.$ To this end, we study two
types of algorithms: adaptive and non-adaptive ones, each of which corresponds
to whether we adaptively select the next respondents based on the answers of
the previous respondents or not. We first provide the information theoretic
lower bounds for the necessary budgets in both algorithm types. In terms of the
sufficient budgets, we propose two practical estimation algorithms, each of
non-adaptive and adaptive types, and for each algorithm, we quantitatively
analyze the budget which ensures $1-\delta$ detection accuracy. This
theoretical analysis not only quantifies the budgets needed by practical
estimation algorithms achieving a given target detection accuracy in finding
the diffusion source, but also enables us to quantitatively characterize the
amount of extra budget required in non-adaptive type of estimation, refereed to
as {\em adaptivity gap}. We validate our theoretical findings over synthetic
and real-world social network topologies.
