Identification and Asymptotic Localization of Rumor Sources Using the Method of Types

Himaja Kesavareddigari, Sam Spencer, Atilla Eryilmaz, R. Srikant

Research output: Contribution to journalArticlepeer-review

Abstract

We are interested in identifying a rumor source on a tree network. We begin with extended star networks under the SI infection model with exponential waiting times. We present and analyze the types center, a highly tractable approximation of the ML source estimate, obtained using the method of types. We empirically show that this approximate ML estimator is exact for some small test cases. We prove that the approximation error is at most logarithmic in infection size on large networks, providing highly efficient source identification (especially compared to the accuracy in similar problems, such as the <formula><tex>$\mathcal{O}(\sqrt{n})$</tex></formula> best possible accuracy estimate in a line network). We also show that the qualitative properties of the types and rumor centers are different on extended star networks. We further propose a heuristic-based generalization of this approach to trees: the relative-leaf counting algorithm. In simulations on regular and non-regular trees, types center&#x0027;s performance is competitive with rumor centrality (which is optimal for d-regular trees), while requiring less computation time. In addition to providing a faster (and sometimes more accurate) alternative on its own, our approach could potentially be used with rumor centrality to improve results with less than twice the total computation time.

Original languageEnglish (US)
JournalIEEE Transactions on Network Science and Engineering
DOIs
StateAccepted/In press - 2019

Keywords

  • Graph and tree search strategies
  • Heuristic design
  • Network problems
  • Performance evaluation of algorithms and systems
  • Probability and Statistics
  • Symbolic and algebraic manipulation
  • Trees

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Identification and Asymptotic Localization of Rumor Sources Using the Method of Types'. Together they form a unique fingerprint.

Cite this