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

Abstract

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.
Pages439-443
Number of pages5
ISBN (Electronic)9781509030972
DOIs
StatePublished - 31 Jan 2018
Event2017 IEEE Information Theory Workshop, ITW 2017 - Kaohsiung, Taiwan
Duration: 6 Nov 201710 Nov 2017

Publication series

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

Conference

Conference2017 IEEE Information Theory Workshop, ITW 2017
CountryTaiwan
CityKaohsiung
Period6/11/1710/11/17

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

Cite this