Containment of misinformation spread in online social networks 论文

摘要

With their blistering expansions in recent years, popular on-line social sites such as Twitter, Facebook and Bebo, have become some of the major news sources as well as the most effective channels for viral marketing nowadays. However, alongside these promising features comes the threat of mis-information propagation which can lead to undesirable ef-fects, such as the widespread panic in the general public due to faulty swine flu tweets on Twitter in 2009. Due to the huge magnitude of online social network (OSN) users and the highly clustered structures commonly observed in these kinds of networks, it poses a substantial challenge to effi-ciently contain viral spread of misinformation in large-scale social networks. In this paper, we focus on how to limit viral propagation of misinformation in OSNs. Particularly, we study a set of problems, namely the βIT−Node Protectors, which aims to find the smallest set of highly influential nodes whose decon-tamination with good information helps to contain the viral spread of misinformation, initiated from the set I, to a de-sired ratio (1 − β) in T time steps. In this family set, we analyze and present solutions including inapproximability result, greedy algorithms that provide better lower bounds on the number of selected nodes, and a community-based heuristic method for the Node Protector problems. To ver-ify our suggested solutions, we conduct experiments on real world traces including NetHEPT, NetHEPT WC and Face-book networks. Empirical results indicate that our meth-ods are among the best ones for hinting out those important nodes in comparison with other available methods.