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

点击翻译按钮获取中文摘要

Given a graph, such as a social/computer network, or the blogo-sphere, how will a virus (or rumor or new product) propagate init? 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 networksecurity, for market penetration, for blog monitoring and manymore applications.In the PI's past work, they studied arbitrary graphs, and showedthat propagation depends on a single number, namely, the firsteigenvalue of the adjacency matrix of the network. Specifically,they studied the so-called 'epidemic threshold' for flu-likepropagation (``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 casesof power-law graphs - *all* of which are special cases of thePI'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? Abouttime-evolving graphs, like an ad-hoc network of mobile phoneusers? The second thrust is on *algorithms*: Given a graph, avirus model (SIS, SIR, etc), and a fixed budget of 'k'nodes/edges to immunize, how can we quickly find an optimal ornear-optimal solution, to best contain the virus? How can wemodify the algorithm, when the network changes over time?The TECHNICAL MERIT of the work is that it is the first to focuson *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 graphsetc.).The BROADER IMPACT is high, as dynamics of large-scale graphs ap-pear in numerous settings: cascades on blogs; product penetrationand viral marketing; rumor/information propagation; immunizationpolicies; advertisement policies etc.For further information see the project web page: URL:http://www.cs.cmu.edu/~christos/NSF-PROJECTS/Immunization/