A Greedy Monitoring Station Selection for Rumor Source Detection in Online Social Networks
- 7 July 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computational Social Systems
- Vol. 11 (2) , 2644-2655
Abstract
In monitoring station observation, for the best accuracy of rumor source detection, it is important to deploy monitors appropriately into the network. There are, however, a very limited number of studies on the monitoring station selection. This article will study the problem of detecting a single rumormonger based on an observation of selected infection monitoring stations in a complete snapshot taken at some time in an online social network (OSN) following the independent cascade (IC) model. To deploy monitoring stations into the observed network, we propose an influence-distance-based $k$ -station selection method where the influence distance is a conceptual measurement that estimates the probability that a rumor-infected node can influence its uninfected neighbors. Accordingly, a greedy algorithm is developed to find the best $k$ monitoring stations among all rumor-infected nodes with a 2-approximation. Based on the infection path, which is most likely toward the $k$ infection monitoring stations, we derive that an estimator for the “most like” rumor source under the IC model is the Jordan infection center in a graph. Our theoretical analysis is presented in the article. The effectiveness of our method is verified through experiments over both synthetic and real-world datasets. As shown in the results, our $k$ -station selection method outperforms off-the-shelf methods in most cases in the network under the IC model.Keywords
Funding Information
- National Science Foundation (1822985)
- National Natural Science Foundation of China (62202109)
- Basic and Applied Basic Research Foundation of Guangdong Province (2021A1515110321, 2022A1515010611)
- Guangzhou Basic and Applied Basic Research Foundation (202201010676)
This publication has 23 references indexed in Scilit:
- A Survey on Gas Leakage Source Detection and Boundary Tracking with Wireless Sensor NetworksIEEE Access, 2016
- Detecting Multiple Information Sources in Networks under the SIR ModelIEEE Transactions on Network Science and Engineering, 2016
- Scalable Rumor Source Detection under Independent Cascade Model in Online Social Networks2015
- Identification of Patient Zero in Static and Temporal Networks: Robustness and LimitationsPhysical Review Letters, 2015
- Information Source Detection in the SIR Model: A Sample-Path-Based ApproachIEEE/ACM Transactions on Networking, 2014
- Estimating infection sources in a network with incomplete observations2013
- Finding an infection source under the SIS model2013
- Social structure of Facebook networksPhysica A: Statistical Mechanics and its Applications, 2012
- Identifying the starting point of a spreading process in complex networksPhysical Review E, 2011
- Finding community structure in networks using the eigenvectors of matricesPhysical Review E, 2006