Efficient Rumor Control via Disseminating Truthful Information by Influential Nodes

Rumor Control (RC), aimed at minimizing the spread of rumors in social networks, is of paramount importance, as the spread of rumors can lead to significant economic losses, societal disruptions, and even widespread panic. The RC problem has garnered extensive research attention, however, most existing solutions for rumor control face a trade-off between efficiency and effectiveness, which limits their practical application in real-world scenarios. In this light, this paper studies the Truth-spreading-based Rumor Control (TRC) problem, and introduces the Subgraph-based Greedy algorithm Optimized with CELF (SGOC), which employs subgraph techniques and the CELF strategy, as the basic solution for the TRC problem. To improve the performance of SGOC, we carefully design a shortest path length dictionary SPR and an Immune Nodes Set (INS), leading to the Shortest Path-Based Rumor Control (SPRC) algorithm. To further enhance the SPRC algorithm, we develop a pruning method that accelerates the construction process of INS, proposing the Improved Shortest Path-Based Rumor Control (ISPRC) algorithm, which demonstrates superior efficiency compared to both SPRC and SGOC. Extensive experiments conducted on five real-world datasets, demonstrate the effectiveness and efficiency of the proposed algorithms.