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

PY - 2017/7/31

Y1 - 2017/7/31

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 - http://www.scopus.com/inward/record.url?scp=85040254305&partnerID=8YFLogxK

U2 - 10.1145/3110025.3110028

DO - 10.1145/3110025.3110028

M3 - Conference contribution

AN - SCOPUS:85040254305

T3 - Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2017

SP - 86

EP - 90

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

A2 - Diesner, Jana

A2 - Ferrari, Elena

A2 - Xu, Guandong

PB - Association for Computing Machinery, Inc

Y2 - 31 July 2017 through 3 August 2017

ER -