Information Source Finding in Networks: Querying With Budgets

Cited 1 time in webofscience Cited 0 time in scopus
  • Hit : 35
  • Download : 0
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: (i) whether the respondent is the source or not, and (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, referred to as adaptivity gap. We validate our theoretical findings over synthetic and real-world social network topologies.
Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
Issue Date
2020-10
Language
English
Article Type
Article
Citation

IEEE/ACM TRANSACTIONS ON NETWORKING, v.28, no.5, pp.2271 - 2284

ISSN
1063-6692
DOI
10.1109/TNET.2020.3009946
URI
http://hdl.handle.net/10203/281857
Appears in Collection
RIMS Journal PapersEE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 1 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0