Rumor Source Detection in Finite Graphs with Boundary Effects by Message-passing Algorithms

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

doi:10.1145/3110025.3110028

Rumor Source Detection in Finite Graphs with Boundary Effects by Message-passing Algorithms

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

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

16 Citations (Scopus)

Abstract

Finding 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 rumor graph, how to accurately identify the initial source of the spreading? In the seminal work by Shah and Zaman in 2011, this statistical inference problem was formulated as a maximum likelihood estimation problem and solved using a rumor centrality approach for graphs that are degree-regular. This however is optimal only if there are no boundary effects, e.g., the underlying number of susceptible vertices is countably infinite. In general, all practical real world networks are finite or exhibit complex spreading behavior, and therefore these boundary effects cannot be ignored. In this paper, we solve the constrained maximum likelihood estimation problem by a generalized rumor centrality for spreading in graphs with boundary effects. We derive a graph-theoretic characterization of the maximum likelihood estimator for degree-regular graphs with a single end vertex at its boundary and propose a message-passing algorithm that is near-optimal for graphs with more complex boundary consisting of multiple end vertices.

Original language	English
Title of host publication	Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2017)
Publisher	Association for Computing Machinery
Pages	86-90
ISBN (Print)	978-1-4503-4993-2
DOIs	https://doi.org/10.1145/3110025.3110028
Publication status	Published - Jul 2017
Event	The 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining : ASONAM 2017 - Sydney, Australia, Sydney, Australia Duration: 31 Jul 2017 → 3 Aug 2017 http://asonam.cpsc.ucalgary.ca/2017/

Conference

Conference	The 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining
Place	Australia
City	Sydney
Period	31/07/17 → 3/08/17
Internet address	http://asonam.cpsc.ucalgary.ca/2017/

Bibliographical note

Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 3 Good Health and Well-being

Access Output

10.1145/3110025.3110028

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{983e861684cf4e9d9254af97f514bee8,

title = "Rumor Source Detection in Finite Graphs with Boundary Effects by Message-passing Algorithms",

abstract = "Finding 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 rumor graph, how to accurately identify the initial source of the spreading? In the seminal work by Shah and Zaman in 2011, this statistical inference problem was formulated as a maximum likelihood estimation problem and solved using a rumor centrality approach for graphs that are degree-regular. This however is optimal only if there are no boundary effects, e.g., the underlying number of susceptible vertices is countably infinite. In general, all practical real world networks are finite or exhibit complex spreading behavior, and therefore these boundary effects cannot be ignored. In this paper, we solve the constrained maximum likelihood estimation problem by a generalized rumor centrality for spreading in graphs with boundary effects. We derive a graph-theoretic characterization of the maximum likelihood estimator for degree-regular graphs with a single end vertex at its boundary and propose a message-passing algorithm that is near-optimal for graphs with more complex boundary consisting of multiple end vertices.",

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

note = "Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).; The 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining : ASONAM 2017 ; Conference date: 31-07-2017 Through 03-08-2017",

year = "2017",

month = jul,

doi = "10.1145/3110025.3110028",

language = "English",

isbn = "978-1-4503-4993-2",

pages = "86--90",

booktitle = "Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2017)",

publisher = "Association for Computing Machinery",

address = "United States",

url = "http://asonam.cpsc.ucalgary.ca/2017/",

}

Yu, P-D, Tan, CW & Fu, H-L 2017, Rumor Source Detection in Finite Graphs with Boundary Effects by Message-passing Algorithms. in Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2017). Association for Computing Machinery, pp. 86-90, The 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining , Sydney, Australia, 31/07/17. https://doi.org/10.1145/3110025.3110028

Rumor Source Detection in Finite Graphs with Boundary Effects by Message-passing Algorithms. / Yu, Pei-Duo; Tan, Chee Wei; Fu, Hung-Lin.
Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2017). Association for Computing Machinery, 2017. p. 86-90.

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Rumor Source Detection in Finite Graphs with Boundary Effects by Message-passing Algorithms

AU - Yu, Pei-Duo

AU - Tan, Chee Wei

AU - Fu, Hung-Lin

N1 - Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

PY - 2017/7

Y1 - 2017/7

N2 - Finding 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 rumor graph, how to accurately identify the initial source of the spreading? In the seminal work by Shah and Zaman in 2011, this statistical inference problem was formulated as a maximum likelihood estimation problem and solved using a rumor centrality approach for graphs that are degree-regular. This however is optimal only if there are no boundary effects, e.g., the underlying number of susceptible vertices is countably infinite. In general, all practical real world networks are finite or exhibit complex spreading behavior, and therefore these boundary effects cannot be ignored. In this paper, we solve the constrained maximum likelihood estimation problem by a generalized rumor centrality for spreading in graphs with boundary effects. We derive a graph-theoretic characterization of the maximum likelihood estimator for degree-regular graphs with a single end vertex at its boundary and propose a message-passing algorithm that is near-optimal for graphs with more complex boundary consisting of multiple end vertices.

AB - Finding 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 rumor graph, how to accurately identify the initial source of the spreading? In the seminal work by Shah and Zaman in 2011, this statistical inference problem was formulated as a maximum likelihood estimation problem and solved using a rumor centrality approach for graphs that are degree-regular. This however is optimal only if there are no boundary effects, e.g., the underlying number of susceptible vertices is countably infinite. In general, all practical real world networks are finite or exhibit complex spreading behavior, and therefore these boundary effects cannot be ignored. In this paper, we solve the constrained maximum likelihood estimation problem by a generalized rumor centrality for spreading in graphs with boundary effects. We derive a graph-theoretic characterization of the maximum likelihood estimator for degree-regular graphs with a single end vertex at its boundary and propose a message-passing algorithm that is near-optimal for graphs with more complex boundary consisting of multiple end vertices.

UR - https://www.scopus.com/pages/publications/85040254305

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85040254305&origin=recordpage

U2 - 10.1145/3110025.3110028

DO - 10.1145/3110025.3110028

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 978-1-4503-4993-2

SP - 86

EP - 90

BT - Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2017)

PB - Association for Computing Machinery

T2 - The 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

Y2 - 31 July 2017 through 3 August 2017

ER -

Rumor Source Detection in Finite Graphs with Boundary Effects by Message-passing Algorithms

Abstract

Conference

Bibliographical note

UN SDGs

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this