III:Small:Influence and Virus Propagation in Large Graphs - Theory and Algorithms
is based upon work supported by the National Science Foundation
under Grant No. IIS-1017415. Any opinions, findings, and
conclusions or recommendations expressed in this material are those
of the author(s) and do not necessarily reflect the views of the
National Science Foundation.
Given a graph, such as a social/computer network, or the blogosphere, how will a virus (or rumor or new product) propagate in
it? Will it take over, creating a pandemic? How to select the
'k' best nodes/edges for immunization, or, conversely, the best
'k' blogs for the fastest dissemination of a new idea? The answer to such questions is vital, for public health, for network
security, for market penetration, for blog monitoring and many
In the PI's past work, they studied arbitrary graphs, and showed
that propagation depends on a single number, namely, the first
eigenvalue of the adjacency matrix of the network. Specifically,
they studied the so-called 'epidemic threshold' for flu-like
propagation (``SIS'' model = susceptible-infectious-susceptible),
on un-directed, un-weighted static graphs. All earlier work focused on full cliques, or homogeneous graphs, or specific cases
of power-law graphs - *all* of which are special cases of the
PI's eigenvalue result.
The major thrusts of the current proposal are two. The first is
*theory*: For a mumps-like model (``SIR'' = susceptible - infected - recovered), and for additional models, when will a virus result in a pandemic? What can we say about weighted graphs? About
time-evolving graphs, like an ad-hoc network of mobile phone
users? The second thrust is on *algorithms*: Given a graph, a
virus model (SIS, SIR, etc), and a fixed budget of 'k'
nodes/edges to immunize, how can we quickly find an optimal or
near-optimal solution, to best contain the virus? How can we
modify the algorithm, when the network changes over time?
The TECHNICAL MERIT of the work is that it is the first to focus
on *arbitrary* graphs, thus including real ones. In contrast,
the vast majority of past analytical work makes unrealistic assumptions about the graph topology (cliques, homogeneous graphs
The BROADER IMPACT is high, as dynamics of large-scale graphs appear in numerous settings: cascades on blogs; product penetration
and viral marketing; rumor/information propagation; immunization
policies; advertisement policies etc.
Data mining, Virus Propagation, Immunization, Viral Marketing.
- NSF, Award Number: IIS-1017415, Duration:
In addition to the PI, the following people work on
There are two motivating questions, one for each proposed thrust: (a) Theory: Given the
virus/influence property and the graph structure, what is the condition that an epidemic will
break out (or a piece of information will survive)? (b) Algorithms: Given the virus/influence
property and the graph structure, which k nodes/edges are the best to immunize so that we can
prevent an epidemic from breaking out to the maximum extent? We give the highlights of each
Theory: The first thrust tries to understand the epidemic threshold of virus propagation. In
our past work, we discovered a general epidemic threshold for SIS model with un-directed static
graphs. First of all, we propose to generalize it to (1) other types of viruses (e.g., SIR), and (2)
more general graphs (e.g., directed graphs). Unlike the existing work
on epidemic threshold, which are designed for
some special graphs; in our proposed work, we aim to address the arbitrary, real graphs. What
is more, we also want to study some important settings, which are barely (if at all) studied by
the existing work. To name a few, we plan to study the epidemic threshold (1) for multiple
competing viruses, (2) on dynamic graphs, etc.
Algorithms: The second thrust involves the development of immunization algorithms. In
our on-going work, we developed a fast near-optimal immunization strategy for SIS model with
un-directed, un-weighted static graphs. We propose to continue this work by generalizing it to
(1) SIR virus propagation model; (2) directed weighted graphs. Unlike the existing immuniza-
tion algorithms which are based on some heuristic and/or designed for some special graphs,
the proposed immunization algorithms will focus on arbitrary, real graphs; and try to (ap-
proximately) maximize the corresponding epidemic threshold. What is more, we also want to
develop immunization algorithms under some important, yet barely (if at all) studied settings
in the existing work, including (1) dynamic immunization, (2) multiple viruses cost-sensitive
immunization. Finally, we want to handle
the scalability issue by implementing our algorithms on map/reduce architecture.
Our main results so far are as follows:
- We are the first to show the generalized threshold theorem - which nicely de-couples the effect of the topology
and the virus model on the epidemic threshold. Our result unifies and includes as
special case older results and shows that the threshold depends
on the first eigenvalue of the connectivity matrix, (a) for
any static graph and (b) for all propagation models in standard
literature (more than 25, including H.I.V.).
- We derived the first closed formula for the epidemic threshold for the flu-like SIS model for a given set of alternating graphs. We showed
that it depends on the first eigenvalue of the so-called 'system' matrix.
- We developed a general framework to analyze epidemic spreading processes on mobile ad hoc networks, and using our framework, we are the first to derive the epidemic threshold
for any mobility model under the SIS model, and (c) we show that the node velocity in mobility models does not affect the epidemic threshold.
- We developed NetShield, a fast, scalable and provably near-optimal (constant-factor of optimal) algorithm to find the best-k nodes to be immunized
in a graph. We outperform all the prominent competitors including 'Accquaintance' immunization, 'PageRank' etc.
- We also developed fast heuristics for immunization under time-varying graphs which again outperformed other baselines like average degree, maximum degree etc.
- We developed Complex Linear Dynamical Systems (CLDS) to automatically find features for multiple time-sequences. We were able to cluster motion capture and BGP instability (which can be
thought of spreading virally) time-sqeuences automatically with CLDS.
- Threshold Conditions for Arbitrary Cascade Models on Arbitrary Networks [PDF] [extended arXiv version]
B. Aditya Prakash, Deepayan Chakrabarti, Michalis Faloutsos, Nicholas Valler, Christos Faloutsos
in IEEE ICDM 2011, Vancouver
- Time Series Clustering: Complex is Simpler! [PDF]
Lei Li, B. Aditya Prakash
in ICML 2011, Bellevue
- Epidemic Spread in Mobile Ad Hoc Networks: Determining the Tipping Point [PDF]
Nicholas Valler, B. Aditya Prakash, Hanghang Tong, Michalis Faloutsos, Christos Faloutsos
in IFIP NETWORKING 2011, Valencia
- On the Vulnerability of Large Graphs [PDF][CODE]
Hanghang Tong, B. Aditya Prakash, Charalampos Tsourakakis, Tina Eliassi-Rad, Christos Faloutsos, Duen Horng Chau
in IEEE ICDM 2010, Sydney
- Virus Propagation on Time-Varying Networks: Theory and Immunization Algorithms [PDF]
B. Aditya Prakash, Hanghang Tong, Nicholas Valler, Michalis Faloutsos, Christos Faloutsos
in ECML-PKDD 2010, Barcelona
- Parsimonious Linear Fingerprinting for Time Series [PDF][CODE]
Lei Li, B. Aditya Prakash, Christos Faloutsos
in VLDB 2010, Singapore
Last updated: September 12,
2011, by B. Aditya Prakash.