III: Small: Influence and Virus Propagation in Large Graphs - Theory and Algorithms

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

Given a graph, such as a social/computer network, or the blogo- sphere, 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 an- swer to such questions is vital, for public health, for network security, for market penetration, for blog monitoring and many more applications. 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 fo- cused 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 - infect- ed - recovered), and for additional models, when will a virus re- sult 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 as- sumptions about the graph topology (cliques, homogeneous graphs etc.). The BROADER IMPACT is high, as dynamics of large-scale graphs ap- pear in numerous settings: cascades on blogs; product penetration and viral marketing; rumor/information propagation; immunization policies; advertisement policies etc. For further information see the project web page: URL: http://www.cs.cmu.edu/~christos/NSF-PROJECTS/Immunization/