An algorithmic framework for estimating rumor sources with different start times

Feng Ji, Wee Peng Tay, Lav R. Varshney

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number7833026
Pages (from-to)2517-2530
Number of pages14
JournalIEEE Transactions on Signal Processing
Issue number10
StatePublished - May 15 2017


  • Rumor source
  • SI model
  • infection source
  • multiple source estimation
  • quasi-regular tree

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering

Cite this