Viral spread on large graphs has many real-life applications such as malware propagation in computer networks and rumor (or misinformation) spread in Twitter-like online social networks. Although viral spread on large graphs has been intensively analyzed on classical models such as Susceptible-Infectious-Recovered, there still exits a deficit of effective methods in practice to contain epidemic spread once it passes a critical threshold. Against this backdrop, we explore methods of containing viral spread in large networks with the focus on sparse random networks. The viral containment strategy is to partition a large network into small components and then to ensure the sanity of all messages delivered across different components. With such a defense mechanism in place, an epidemic spread starting from any node is limited to only those nodes belonging to the same component as the initial infection node. We establish both lower and upper bounds on the costs of inspecting inter-component messages. We further propose heuristic-based approaches to partition large input graphs into small components. Finally, we study the performance of our proposed algorithms under different network topologies and different edge weight models.
Another motivating application of this work is containment of rumor or misinformation diffusion in large social networks. Research on this topic is still at its infancy. Budak considered the problem of limiting the spread of misinformation in social networks @cite_23 . Their approach was to convince a small set of users in the online social network to spread good'' rumors that cancel out the influence of bad ones. Convincing people to spread good'' rumors in social networks, albeit an interesting idea, may not be feasible in practice. The strategy we consider in this work, however, does not require involvement of individual users.
@cite_23
1995698352
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 misinformation propagation which can lead to undesirable effects, 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 efficiently 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 β1T -- Node Protectors, which aims to find the smallest set of highly influential nodes whose decontamination with good information helps to contain the viral spread of misinformation, initiated from the set I, to a desired 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 verify our suggested solutions, we conduct experiments on real world traces including NetHEPT, NetHEPT_WC and Facebook networks. Empirical results indicate that our methods are among the best ones for hinting out those important nodes in comparison with other available methods.