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

Himaja Kesavareddigari, Sam Spencer, Atilla Eryilmaz, Rayadurgam Srikant

Research output: Contribution to journalArticle

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 - Jan 1 2019

Fingerprint

Stars

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

Cite this

Identification and Asymptotic Localization of Rumor Sources Using the Method of Types. / Kesavareddigari, Himaja; Spencer, Sam; Eryilmaz, Atilla; Srikant, Rayadurgam.

In: IEEE Transactions on Network Science and Engineering, 01.01.2019.

Research output: Contribution to journalArticle

@article{7cc799098ac4409788e0c891716e2e83,
title = "Identification and Asymptotic Localization of Rumor Sources Using the Method of Types",
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 $\mathcal{O}(\sqrt{n})$ 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'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.",
keywords = "Graph and tree search strategies, Heuristic design, Network problems, Performance evaluation of algorithms and systems, Probability and Statistics, Symbolic and algebraic manipulation, Trees",
author = "Himaja Kesavareddigari and Sam Spencer and Atilla Eryilmaz and Rayadurgam Srikant",
year = "2019",
month = "1",
day = "1",
doi = "10.1109/TNSE.2019.2911275",
language = "English (US)",
journal = "IEEE Transactions on Network Science and Engineering",
issn = "2327-4697",
publisher = "IEEE Computer Society",

}

TY - JOUR

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

AU - Kesavareddigari, Himaja

AU - Spencer, Sam

AU - Eryilmaz, Atilla

AU - Srikant, Rayadurgam

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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 $\mathcal{O}(\sqrt{n})$ 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'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.

AB - 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 $\mathcal{O}(\sqrt{n})$ 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'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.

KW - Graph and tree search strategies

KW - Heuristic design

KW - Network problems

KW - Performance evaluation of algorithms and systems

KW - Probability and Statistics

KW - Symbolic and algebraic manipulation

KW - Trees

UR - http://www.scopus.com/inward/record.url?scp=85064658637&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85064658637&partnerID=8YFLogxK

U2 - 10.1109/TNSE.2019.2911275

DO - 10.1109/TNSE.2019.2911275

M3 - Article

AN - SCOPUS:85064658637

JO - IEEE Transactions on Network Science and Engineering

JF - IEEE Transactions on Network Science and Engineering

SN - 2327-4697

ER -