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

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

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.