Rumor Containment by Blocking Nodes in Social Networks

Rumor spreads fast in social networks and may seriously damage our society. In this article, we present a mathematical programming formulation based on integer linear programming (ILP) to minimize rumor spread by blocking a subset of nodes (called blockers) in complex social networks modeled as a linear threshold model. We also propose a modified approach which solves the top -k blockers problem with a reduced computational effort and formally proves that its performance is still optimal. Then, the presented method is evaluated for its effectiveness of containing rumor spread in four different networks and its performance is compared with a greedy-based and two centrality-based approaches. The experimental analysis shows that the ILP-based method outperforms the other three approaches and is applicable to large-scale networks.

Automated summary

Rumors spread rapidly in social networks and have a serious impact on society. This article presents a mathematical programming formulation using integer linear programming to minimize rumor spread in complex social networks. A modified approach is also proposed to efficiently solve the top-k blockers problem, with a proof of its optimal performance. Experimental analysis demonstrates that the ILP-based method outperforms other approaches and is applicable to large-scale networks.