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

III：小：大图中的影响和病毒传播 - 理论和算法

• 批准号: 1017415
• 负责人: Christos Faloutsos
• 金额: $ 49.97万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1017415&HistoricalAwards=false
• 关键词: III; Small; Influence; Virus; Propagation

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/

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