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

给定一个图，比如一个社交/计算机网络，或者一个博客圈，病毒（或谣言或新产品）将如何在其中传播？ 它会接管，造成大流行吗？ 如何选择"k"个最好的节点/边来进行免疫，或者反过来，如何选择最好的"k"个博客来最快地传播一个新想法？ 这些问题的答案对于公共健康、网络安全、市场渗透、博客监控以及更多的应用都是至关重要的。在PI过去的工作中，他们研究了任意图，并表明传播取决于一个单一的数字，即网络邻接矩阵的第一个特征值。 具体来说，他们研究了所谓的“流行病阈值”的流感样传播（“SIS”模型=易感染-传染-易感），在无向，无权重的静态图。 所有早期的工作都集中在完全团，或齐次图，或幂律图的特殊情况-* 所有 * 这些都是PI的特征值结果的特殊情况。第一个是 * 理论 *：对于一个类似腮腺炎的模型（"SIR"=易感-感染-恢复），以及其他模型，病毒什么时候会导致大流行？ 关于加权图我们能说些什么呢？关于时间演化图，比如移动的电话用户的自组织网络？ 第二个重点是 * 算法 *：给定一个图，病毒模型（SIS，SIR等），和一个固定的预算， 我们如何快速找到一个最优或接近最优的解决方案，以最好地遏制病毒？ 当网络随时间变化时，我们如何修改算法？这项工作的技术优点是，它是第一个专注于 * 任意 * 图，从而包括真实的。 相比之下，绝大多数过去的分析工作，使不切实际的假设图的拓扑结构（团，均匀graphsetc。更广泛的影响是高的，因为大规模图的动态在许多设置中出现：博客上的级联;产品渗透和病毒式营销;谣言/信息传播;免疫政策;广告政策等。 web 页号： 网址：www.example.com

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/