An Algorithmic Framework for Estimating Rumor Sources With Different Start Times

• Main Authors: Ji, Feng, Tay, Wee Peng, Varshney, Lav R.
• Other Authors: School of Electrical and Electronic Engineering
• Format: Article
• Language: English
• Published: 2017
• Subjects: Rumor source; Infection source
• Online Access: https://hdl.handle.net/10356/81429; http://hdl.handle.net/10220/43464
• Institution: Nanyang Technological University

We study the problem of identifying multiple rumor or infection sources in a network under the susceptible-infected model, and where these sources may start infection spreading at different times. We introduce the notion of an abstract estimator that, given the infection graph, assigns a higher value to each vertex in the graph it considers more likely to be a rumor source. This includes several of the single-source estimators developed in the literature. We introduce the concepts of a quasi-regular tree and a heavy center, which allows us to develop an algorithmic framework that transforms an abstract estimator into a two-source joint estimator, in which the infection graph can be thought of as covered by overlapping infection regions. We show that our algorithm converges to a local optimum of the estimation function if the underlying network is a quasi-regular tree. We further extend our algorithm to more than two sources, and heuristically to general graphs. Simulation results on both synthetic and real-world networks suggest that our algorithmic framework outperforms several existing multiple-source estimators, which typically assume that all sources start infection spreading at the same time.