Rumor Source Detection: Power of Querying

Abstract

Social networks are the major routes for most individuals to exchange their opinions about new products, social trends and political issues via their interactions. It is often of significant importance to figure out who initially diffuses the information, i.e., finding a rumor source or a trend setter. The result by Shah and Zaman [1] reveals that such a task is highly challenging and the source detection probability cannot be beyond 31% for regular trees. As a natural step to increase the detection probability, a source finder may ask questions to those who have already infected. In this paper, we study the power of querying i.e., two querying scenarios with a given budget K: (a) interactive which asks K candidate nodes sequentially, where the questions is `who spreads a rumor to you?'. Note that one can obtain additional information in each query, which can be utilized to choose the next queriee, and (b) non-interactive which corresponds to a batch type of querying without any interactive question-and-answer mechanism. One just chooses K candidate nodes at once and perform a single query to each of them, asking `Are you a rumor source?'. We first develop the querying algorithms for both scenarios, and provide mathematical characterizations in terms of the degree of contributions made by queries, under regular tree topologies. Our anlaytical results show that under our algorithms the detection error probability asymptotically decays with O(1=pK) for non-interactive querying and exp(􀀀O(K)) in interactive querying. For the proof of the results, we use Polya's urn to characterize the asymptotic detection behavior which results in an incomplete beta function in [2]. Furthermore, we found that even a small query budget is highly beneficial in the source detection, e.g., under 3-regular tree, K = 5 interactive quries suffices to achieve the detection probability 99% whereas K > 20 non-interactive queries are need to achieve this. We present various simulation results for other general graphs that verifies our theoretical findings by using the Breath-First Search (BFS) heuristic approach and conclude that using queries is very useful to detect the rumor source even in the general graphs