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.
@cite_29: In this paper we study the small-world network model of Watts and Strogatz, which mimics some aspects of the structure of networks of social interactions. We argue that there is one non-trivial length-scale in the model, analogous to the correlation length in other systems, which is well-defined in the limit of infinite system size and which diverges continuously as the randomness in the network tends to zero, giving a normal critical point in this limit. This length-scale governs the cross-over from large- to small-world behavior in the model, as well as the number of vertices in a neighborhood of given radius on the network. We derive the value of the single critical exponent controlling behavior in the critical region and the finite size scaling form for the average vertex-vertex distance on the network, and, using series expansion and Pade approximants, find an approximate analytic form for the scaling function. We calculate the effective dimension of small-world graphs and show that this dimension varies as a function of the length-scale on which it is measured, in a manner reminiscent of multifractals. We also study the problem of site percolation on small-world networks as a simple model of disease propagation, and derive an approximate expression for the percolation probability at which a giant component of connected vertices first forms (in epidemiological terms, the point at which an epidemic occurs). The typical cluster radius satisfies the expected finite size scaling form with a cluster size exponent close to that for a random graph. All our analytic results are confirmed by extensive numerical simulations of the model. Appears in Phys. Rev. E 60, 7332-7342 (1999).
@cite_1: Self-propagating mal-packets have become an emergent threat against information confidentiality, integrity, and service availability in wireless sensor networks. While playing an important role for people to interact with surrounding environment, wireless sensor networks suffer from growing security concerns posed by mal-packets because of sensor networks' low physical security, lack of resilience and robustness of underlying operating systems, and the ever-increasing complexity of deployed applications. In this paper, we study the propagation of mal-packets in 802.15.4 based wireless sensor networks. Based on our proposed mal-packet self-propagation models, we use TOSSIM, a simulator for wireless sensor networks, to study their propagation dynamics. We also present a study of the feasibility of mal-packet defense in sensor networks. Specifically, we apply random graph theory and percolation theory to investigate the immunization of highly-connected nodes, i.e., nodes with high degrees of connectivity. Our goal is to partition the network into as many separate pieces as possible, thus preventing or slowing down the mal-packet propagation. We study the percolation thresholds of different network densities and the effectiveness of immunization in terms of connection ratio, remaining link ratio, and distribution of component sizes. We also present an analysis of the distribution of component sizes.
@cite_27: Complex networks such as the sexual partnership web or the Internet often show a high degree of redundancy and heterogeneity in their connectivity properties. This peculiar connectivity provides an ideal environment for the spreading of infective agents. Here we show that the random uniform immunization of individuals does not lead to the eradication of infections in all complex networks. Namely, networks with scale-free properties do not acquire global immunity from major epidemic outbreaks even in the presence of unrealistically high densities of randomly immunized individuals. The absence of any critical immunization threshold is due to the unbounded connectivity fluctuations of scale-free networks. Successful immunization strategies can be developed only by taking into account the inhomogeneous connectivity properties of scale-free networks. In particular, targeted immunization schemes, based on the nodes' connectivity hierarchy, sharply lower the network's vulnerability to epidemic attacks.
@cite_2: We consider a spatial model related to bond percolation for the spread of a disease that includes variation in the susceptibility to infection. We work on a lattice with random bond strengths and show that with strong heterogeneity, i.e. a wide range of variation of susceptibility, patchiness in the spread of the epidemic is very likely, and the criterion for epidemic outbreak depends strongly on the heterogeneity. These results are qualitatively different from those of standard models in epidemiology, but correspond to real effects. We suggest that heterogeneity in the epidemic will affect the phylogenetic distance distribution of the disease-causing organisms. We also investigate small world lattices, and show that the effects mentioned above are even stronger.
@cite_20: Email worms constitute one of the major Internet security problems. In this paper, we present an email worm model that accounts for the behaviors of email users by considering email checking time and the probability of opening email attachments. Email worms spread over a logical network defined by email address relationship, which plays an important role in determining the spreading dynamics of an email worm. Our observations suggest that the node degrees of an email network are heavy-tailed distributed. We compare email worm propagation on three topologies: power law, small world and random graph topologies; and then study how the topology affects immunization defense on email worms. The impact of the power law topology on the spread of email worms is mixed: email worms spread more quickly on a power law topology than on a small world topology or a random graph topology, but immunization defense is more effective on a power law topology than on the other two
The percolation theory has established the critical threshold for wide-scale epidemic spreading and has been widely applied to study epidemic spreading in diverse network structures, such as small-world networks @cite_29 , heterogeneous networks @cite_2 , and sensor networks @cite_1 . In the context of scale-free networks, selectively immunizing those highly connected nodes is an effective approach to slowing down epidemic spread in such networks @cite_20 @cite_27 . In both problems of containing social-based malware and misinformation spread in social networks, however, the key challenge that faces node immunization is the difficulty of interacting with individual users due to the distributed nature of social networks. An alternative approach would be to achieve node immunization by sanitizing all messages that come to or come from those nodes to be immunized. In our problem, however, this may not be the most cost-effective approach because highly connected nodes could generate a large number of communication messages.