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人死亡。 找到流行病可以帮助识别疾病的传播介质。 该项目开发了基本理论和有效算法，用于在大规模网络中快速，准确的扩散源定位以及部分信息。该结果有立即应用在流行病学中识别零的患者，用于跟踪计算机病毒/恶意软件在网络安全方面的传播，用于定位社交网络中泄漏的分类信息或谣言的来源，用于识别人类疾病的输液中心等。现有的社交网络上的现有研究几乎独特地集中在现实的网络上，这些研究几乎是实现现实的，但在数学上可以跟踪的网络模型和Difff。在现实网络中找到扩散源的问题尚未得到充分研究。准确定位扩散源的关键是确定源是唯一“标志”的感染子网络的特征。通过识别和利用唯一的源签名，该项目通过解决以下三个挑战来推进扩散来源本地化的现状：（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

MrMine: Multi-resolution Multi-network Embedding

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

G-Finder: Approximate Attributed Subgraph Matching

• DOI: 10.1109/bigdata47090.2019.9006525
• 发表时间: 2019-12
• 期刊: 2019 IEEE International Conference on Big Data (Big Data)
• 作者: Lihui Liu;Boxin Du;Jiejun Xu;Hanghang Tong