Rumor source detection in unicyclic graphs

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

doi:10.1109/ITW.2017.8277993

Rumor source detection in unicyclic graphs

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

Department of Applied Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

6 Scopus citations

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 language	English
Title of host publication	2017 IEEE Information Theory Workshop, ITW 2017
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	439-443
Number of pages	5
ISBN (Electronic)	9781509030972
DOIs	https://doi.org/10.1109/ITW.2017.8277993
State	Published - 2 Jul 2017
Event	2017 IEEE Information Theory Workshop, ITW 2017 - Kaohsiung, Taiwan Duration: 6 Nov 2017 → 10 Nov 2017

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2018-January
ISSN (Print)	2157-8095

Conference

Conference	2017 IEEE Information Theory Workshop, ITW 2017
Country/Territory	Taiwan
City	Kaohsiung
Period	6/11/17 → 10/11/17

Access to Document

10.1109/ITW.2017.8277993

Cite this

@inproceedings{65b420a908334e51a65491889f39b218,

title = "Rumor source detection in unicyclic graphs",

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.",

author = "Yu, {Pei Duo} and Tan, {Chee Wei} and Hung-Lin Fu",

note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 2017 IEEE Information Theory Workshop, ITW 2017 ; Conference date: 06-11-2017 Through 10-11-2017",

year = "2017",

month = jul,

day = "2",

doi = "10.1109/ITW.2017.8277993",

language = "English",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "439--443",

booktitle = "2017 IEEE Information Theory Workshop, ITW 2017",

address = "美國",

}

Yu, PD, Tan, CW & Fu, H-L 2017, Rumor source detection in unicyclic graphs. in 2017 IEEE Information Theory Workshop, ITW 2017. IEEE International Symposium on Information Theory - Proceedings, vol. 2018-January, Institute of Electrical and Electronics Engineers Inc., pp. 439-443, 2017 IEEE Information Theory Workshop, ITW 2017, Kaohsiung, Taiwan, 6/11/17. https://doi.org/10.1109/ITW.2017.8277993

Rumor source detection in unicyclic graphs. / Yu, Pei Duo; Tan, Chee Wei; Fu, Hung-Lin.
2017 IEEE Information Theory Workshop, ITW 2017. Institute of Electrical and Electronics Engineers Inc., 2017. p. 439-443 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2018-January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Rumor source detection in unicyclic graphs

AU - Yu, Pei Duo

AU - Tan, Chee Wei

AU - Fu, Hung-Lin

PY - 2017/7/2

Y1 - 2017/7/2

N2 - 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.

AB - 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.

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

U2 - 10.1109/ITW.2017.8277993

DO - 10.1109/ITW.2017.8277993

M3 - Conference contribution

AN - SCOPUS:85046345354

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 439

EP - 443

BT - 2017 IEEE Information Theory Workshop, ITW 2017

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2017 IEEE Information Theory Workshop, ITW 2017

Y2 - 6 November 2017 through 10 November 2017

ER -

Rumor source detection in unicyclic graphs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this