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.