Rumor restriction in Online Social Networks

Online Social Networks (OSNs) have recently emerged as an effective medium for information sharing. Unfortunately, it has been frequently observed that malicious rumors being spread over an OSN are not controllable, and this is not desirable. This paper proposes a new problem, namely the γ - k rumor restriction problem, whose goal is, given a social network, to find a set S of nodes with k protectors (γ * k protectors from the contaminated set, and (1 - γ) * k protectors from the decontaminated set) to protect the network such that the number of decontaminated nodes is maximum. We show that the objective function of the γ - k rumor restriction problem is submodular, and use this result to design a greedy approximation algorithm with performance ratio of 1 - 1/e for the problem under the linear threshold model and independent cascade model, respectively. To verify our algorithms, we conduct experiments on real word social networks including NetHEPT, WikiVote and Slashdot0811. The results show that our algorithm works efficiently and effectively.