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

给出一个图表，比如一个社交/计算机网络，或者是一个blogo领域，一个病毒(或谣言或新产品)将如何在其中传播？它会接手，制造一场大流行吗？如何选择‘k’个最好的节点/边来进行免疫，或者反过来，选择最好的‘k’个博客来最快地传播新思想？对这些问题的回答对公众健康、网络安全、市场渗透、博客监控和许多应用都是至关重要的。在PI过去的工作中，他们研究了任意图，并证明了传播依赖于单个数字，即网络邻接矩阵的第一特征值。具体地说，他们在无向、未加权的静态图上研究了流行性感冒传播(`‘SIS’‘模型=易感-易传染-易感)的所谓’流行阈值‘。所有早期的工作都集中在全团、齐次图或特殊情况下的幂函数图上--所有这些都是PI特征值结果的特例。目前的建议主要有两个要点。第一个是*理论*：对于类似腮腺炎的模型(‘先生’=易感-感染-康复)，以及对于其他模型，病毒将在什么时候在大流行中重新爆发？关于加权图，我们能说什么呢？关于时间演变的图表，就像移动电话用户的临时网络？第二个重点是*算法*：给定一个图、病毒模型(SIS、SIR等)和固定的k个节点/边的免疫预算，我们如何快速找到最优或接近最优的解决方案，以最好地遏制病毒？当网络随时间变化时，我们如何修改算法？这项工作的技术优点是它是第一个关注*任意*图的，因此包括了真实的图。相比之下，过去的绝大多数分析工作对图形拓扑(集团、同质图形集)做出了不切实际的假设。更广泛的影响是高的，因为大规模图形的动态在许多环境中出现：博客上的级联；产品渗透和病毒营销；谣言/信息传播；免疫策略；广告策略等。有关更多信息，请参阅项目网页：URL:http://www.cs.cmu.edu/~christos/NSF-PROJECTS/Immunization/

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/