III: Small: Towards a Theoretical Foundation for Diffusion Source Localization

III：小：迈向扩散源定位的理论基础

• 批准号: 1715385
• 负责人: Lei Ying
• 金额: $ 50万
• 依托单位: Arizona State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1715385&HistoricalAwards=false
• 关键词: III; Small; Towards; Theoretical; Foundation

Diffusion processes have been used to model many real-world phenomena, including rumor spreading on the Internet, epidemics in human beings, emotional contagion through social networks, and even gene regulatory processes. Diffusion source localization is to identify the source(s) of a diffusion process based on observations such as the states of the nodes and a subset of timestamps at which the diffusion process reaches the nodes. The solutions to this problem can answer a wide range of important questions and have significant societal and economic impacts. For example, epidemic diseases are great threats to global health. The 2009 H1N1 virus alone resulted in 151,700 to 575,400 deaths globally. Locating an epidemic source can help identify the transmission media of the disease. This project develops fundamental theories and effective algorithms for fast and accurate diffusion source localization in large-scale networks and with partial information. The results have immediate applications for identifying patient zero in epidemiology, for tracking the spreading of computer viruses/malware in cyber security, for locating the sources of leaked classified information or rumors in social networks, for identifying infusion hubs of human diseases, etc. Existing research on social networks almost exclusively focuses on deriving realistic but mathematically trackable network models and diffusion models. The problem of locating diffusion sources in realistic networks has not been well studied. The key to accurately locating the diffusion source is to identify characteristics of infection subnetworks that are unique "signatures" of the source. By identifying and leveraging unique source signatures, this project advances the state of the art of diffusion source localization by addressing the following three challenges: (1) On the theory side, this project establishes the fundamental limits of source localization for realistic networks. (2) On the algorithm side, this project develops a suite of effective and scalable diffusion source detection algorithms whose theoretical properties are well-understood. (3) From the evaluation perspective, this project comprehensively evaluates the proposed source detection algorithms using both simulation studies and real application scenarios.

扩散过程已经被用来模拟许多现实世界的现象，包括互联网上的谣言传播，人类中的流行病，通过社交网络的情绪传染，甚至基因调控过程。扩散源定位是基于诸如节点的状态和扩散过程到达节点的时间戳的子集之类的观测来识别扩散过程的源。这个问题的解决方案可以回答广泛的重要问题，并产生重大的社会和经济影响。例如，流行性疾病是对全球健康的巨大威胁。仅2009年H1N1病毒就导致全球151，700至575，400人死亡。 确定传染源有助于确定疾病的传播媒介。 本项目主要研究在大规模网络和部分信息条件下快速、准确地定位扩散源的基本理论和有效算法。结果有直接的应用程序，用于识别零号病人的流行病学，跟踪计算机病毒/恶意软件的传播网络安全，用于定位泄漏的机密信息或谣言的来源在社交网络，用于识别输液枢纽的人类疾病等现有的研究社交网络几乎完全集中在获得现实的，但数学上可跟踪的网络模型和扩散模型。在现实网络中，扩散源的定位问题还没有得到很好的研究。准确定位扩散源的关键是识别感染子网络的特征，这些特征是源的唯一“签名”。通过识别和利用独特的源签名，该项目通过解决以下三个挑战来推进扩散源定位的最新技术：（1）在理论方面，该项目建立了现实网络源定位的基本限制。(2)在算法方面，该项目开发了一套有效且可扩展的扩散源检测算法，其理论属性已得到充分理解。(3)从评估的角度来看，该项目使用模拟研究和真实的应用场景来全面评估所提出的源检测算法。

项目成果

Adaptive Feature Redundancy Minimization

• DOI: 10.1145/3357384.3358112
• 发表时间: 2019-11
• 期刊: Proceedings of the 28th ACM International Conference on Information and Knowledge Management
• 作者: Rui Zhang;Hanghang Tong;Yifan Hu

Discerning Edge Influence for Network Embedding

• DOI: 10.1145/3357384.3358044
• 发表时间: 2019-11
• 期刊: Proceedings of the 28th ACM International Conference on Information and Knowledge Management
• 作者: Yaojing Wang;Yuan Yao;Hanghang Tong;F. Xu;Jian Lu

Multi-Layered Network Embedding

• DOI: 10.1137/1.9781611975321.77
• 发表时间: 2018
• 作者: Jundong Li; Chen-Chen-Chen;Hanghang Tong;Huan Liu

Rapid Analysis of Network Connectivity

• DOI: 10.1145/3132847.3133170
• 发表时间: 2017-11
• 期刊: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management
• 作者: Scott Freitas;Hanghang Tong;Nan Cao;Yinglong Xia

Cross-Dependency Inference in Multi-Layered Networks: A Collaborative Filtering Perspective

• DOI: 10.1145/3056562
• 发表时间: 2017-08-01
• 期刊: ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA
• 影响因子: 3.6
• 作者: Chen, Chen;Tong, Hanghang;He, Qing
• 通讯作者: He, Qing