Epidemic spreading in real networks: an eigenvalue viewpoint

By Yang Wang, Deepayan Chakrabarti, Chenxi Wang, Christos Faloutsos. 22nd International Symposium on Reliable Distributed Systems, 2003. Proceedings., 2003

982 citations recorded by the source corpus.

How will a virus propagate in a real network? Does an epidemic threshold exist for a finite graph? How long does it take to disinfect a network given particular values of infection rate and virus death rate? We answer the first question by providing equations that accurately model virus propagation in any network including real and synthesized network graphs. We propose a general epidemic threshold condition that applies to arbitrary graphs: we prove that, under reasonable approximations, the epidemic threshold for a network is closely related to the largest eigenvalue of its adjacency matrix. Finally, for the last question, we show that infections tend to zero exponentially below the epidemic threshold. We show that our epidemic threshold model subsumes many known thresholds for special-case graphs (e.g., Erdos-Renyi, BA power-law, homogeneous); we show that the threshold tends to zero for infinite power-law graphs. We show that our threshold condition holds for arbitrary graphs.

Subfields: Geometry and Topology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/5ebb58588b4ec58f3385c0aa7748977d4ac14b07

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Geometry and Topology

In Statistical and Nonlinear Physics

Citations in the corpus

Tracking information epidemics in blogspace (2005, background): “Particular attention has been paid to the influence of network structure on the existence of an epidemic threshold, which determines whether a disease will spread from a randomly chosen individual to a fraction of the network[25][31].”
Random walks and diffusion on networks (2016, background): “ll number of infected nodes, the propagator of infection events in simple epidemic processes such as susceptible{infected (SI) and susceptible{infected{recovered (SIR) models are the adjacency matrix [91, 92]. In contrast, a propagator of an RW is a type of Laplacian matrix, as we will discuss in de”
Information is not a Virus, and Other Consequences of Human Cognitive Limits (2016, background): “The analogy between the spread of a disease and information is the basis of computational methods that attempt to amplify the spread of information in networks by identifying influential “superspreaders” [1–5], and those that make inferences about the network from observations of how information…”
Randomizing Social Networks: a Spectrum Preserving Approach (2008, background): “In [12], the authors studied how a virus propagates in a real work and proved that the epidemic threshold for a network is closely related to λ1.”
What Stops Social Epidemics? (2011, background): “One of the more important results is the existence of an epidemic threshold (Wang et al. 2003; Prakash et al. 2010; Copyright c© 2013, Association for the Advancement of Artificial Intelligence (www.aaai.org).”
DOULION: counting triangles in massive graphs with a coin (2009, background): “This is an interesting approach since the top eigenvalue of the adjacency matrix representation of any graph is closely related to the epidemic threshold [30].”
Multilayer networks (2013, background): “, in which the node sets are disjoint, but all inter-layer and intra-layer adjacencies are allowed) [282] by generalizing the result for monoplex networks [345] — though one needs to be very careful about how such “results” have been stated in the literature [134] — that the epidemic threshold is gi”
A Survey of Statistical Network Models (2009, background): “The concept of information propagation also finds many applications in the network domain, such as virus propagation in computer networks [310], HIV infection networks [222; 163; 164], viral marketing [87] and more generally gossiping [170].”
Analysis and Control of Epidemics: A Survey of Spreading Processes on Complex Networks (2015, background): “In [55] and [63], the following threshold conditions are provided in terms of the infection strength / . x b d where ( ) A max m is for any initial condition ( ).”
Activity driven modeling of time varying networks (2012, background): “…for the definition of interaction processes based on the actual measurement of the activity of the agents forming the system, a task now made possible by the availability of time-resolved, high-quality data on the instantaneous activity of millions of agents in a wide variety of networks [33–37].”
The effect of network topology on the spread of epidemics (2005, background): “Last, Wang et al. [18] show, through simulation and approximate analysis, that the condition for fast die out relates to the spectral radius of the adjacency matrix of the underlying graph.”
Patterns of Cascading Behavior in Large Blog Graphs (2007, background): “ There is a huge literature on the study of epidemics on full cliques, homogeneous graphs, inﬁnite graphs (see [13] for a survey), with recent studies on power-law networks [7] and arbitrary networks [21]. 3 Preliminaries In this section we introduce terminology and basic concepts regarding the blog”
The stability–complexity relationship at age 40: a random matrix perspective (2015, methodology): “social network (Wang et al. 2003).”