Rumor source detection in unicyclic graphs

Pei Duo Yu, Chee Wei Tan, Hung-Lin Fu

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations


Detecting information source in viral spreading has important applications such as to root out the culprit of a rumor spreading in online social networks. In particular, given a snapshot observation of the network topology of nodes having the rumor, how to accurately identify the initial source of the spreading? In the seminal work [Shah et el. 2011], this problem was formulated as a maximum likelihood estimation problem and solved using a rumor centrality approach for graphs that are degree-regular trees. The case of graphs with cycles is an open problem. In this paper, we address the maximum likelihood estimation problem by a generalized rumor centrality for spreading in unicyclic graphs. In particular, we derive a generalized rumor centrality that leads to a new graph-theoretic design approach to inference algorithms.

Original languageEnglish
Title of host publication2017 IEEE Information Theory Workshop, ITW 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Electronic)9781509030972
StatePublished - 2 Jul 2017
Event2017 IEEE Information Theory Workshop, ITW 2017 - Kaohsiung, Taiwan
Duration: 6 Nov 201710 Nov 2017

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Conference2017 IEEE Information Theory Workshop, ITW 2017


Dive into the research topics of 'Rumor source detection in unicyclic graphs'. Together they form a unique fingerprint.

Cite this