Rooting our Rumor Sources in Online Social Networks: The Value of Diversity From Multiple Observations
Authors:
- 6 January 2015
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal of Selected Topics in Signal Processing
- Vol. 9 (4) , 663-677
Abstract
This paper addresses the problem of rumor source detection with multiple observations, from a statistical point of view of a spreading over a network, based on the susceptible-infectious model. For tree networks, multiple independent observations can dramatically improve the detection probability. For the case of a single rumor source, we propose a unified inference framework based on the joint rumor centrality, and provide explicit detection performance for degree-regular tree networks. Surprisingly, even with merely two observations, the detection probability at least doubles that of a single observation, and further approaches one, i.e., reliable detection, with increasing degree. This indicates that a richer diversity enhances detectability. Furthermore, we consider the case of multiple connected sources and investigate the effect of diversity. For general graphs, a detection algorithm using a breadth-first search strategy is also proposed and evaluated. Besides rumor source detection, our results can be used in network forensics to combat recurring epidemic-like information spreading such as online anomaly and fraudulent email spams.Keywords
Funding Information
- Doctoral Program of Higher Education (SRFDP) and Research Grants Council Earmarked Research Grants (RGC ERG) Joint Research Scheme
- National Natural Science Foundation of China (61379003)
- Research Grants Council of Hong Kong
This publication has 17 references indexed in Scilit:
- Using humans as sensors: An estimation-theoretic perspective2014
- A fast Monte Carlo algorithm for source localization on graphs2013
- Rooting out the rumor culprit from suspects2013
- Finding an infection source under the SIS model2013
- Spotting Culprits in Epidemics: How Many and Which Ones?2012
- Improving Hidden Markov Model Inferences With Private Data From Multiple ObserversIEEE Signal Processing Letters, 2012
- Multi-observer privacy-preserving Hidden Markov Models2012
- Rumors in a Network: Who's the Culprit?IEEE Transactions on Information Theory, 2011
- Detecting sources of computer viruses in networks2010
- Statistical voice activity detection using a multiple observation likelihood ratio testIEEE Signal Processing Letters, 2005