A Distributed Algorithm for Rumor Blocking on Social Networks
摘要
The optimization of influence on social networks has received significant attention, yet there has been limited research on blocking rumors targeted at specific individuals. In this paper, we introduce the Rumor Blocking for Target Users (RBTU) problem, which aims to identify a set of influential seed nodes to minimize the number of target users affected by the rumor. To address scalability challenges, we propose a two-stage distributed algorithm that utilizes community partitioning and reverse sampling techniques. In the first stage, the original network is partitioned into non-overlapping communities. This division serves to reduce the complexity of the problem and allows for parallel processing. In the second stage, reverse sampling is performed independently for each community. This process involves the strategic selection of seed nodes to restrict the spread of the rumor. Additionally, we provide both theoretical and empirical analyses of our proposed algorithm. Theoretically, we prove that the objective function is submodular, which enables the greedy algorithm to achieve an approximate ratio of \((1-1/e)\) . Through numerical simulations, we demonstrate that our algorithm outperforms other comparison methods.