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

扩散过程已经被用来模拟许多真实世界的现象，包括互联网上的谣言传播、人类的流行病、通过社交网络的情感传染，甚至是基因调控过程。扩散源定位是基于节点的状态和扩散过程到达节点的时间戳的子集等观测来识别扩散过程的源(S)。这一问题的解决办法可以回答广泛的重要问题，并产生重大的社会和经济影响。例如，流行病是对全球健康的巨大威胁。仅2009年H1N1病毒就导致全球151,700至575,400人死亡。找到疫源有助于确定疾病的传播媒介。该项目为大规模网络和部分信息下快速准确的扩散源定位提供了基础理论和有效的算法。这些结果在流行病学中识别患者零，在网络安全中跟踪计算机病毒/恶意软件的传播，在社交网络中定位泄露的机密信息或谣言的来源，在识别人类疾病的输液中心等方面具有直接的应用。现有的关于社交网络的研究几乎完全集中于推导现实但数学上可跟踪的网络模型和扩散模型。现实网络中扩散源的定位问题一直没有得到很好的研究。准确定位传播源的关键是识别感染子网络的特征，这些特征是传播源的唯一“特征”。通过识别和利用唯一的信源签名，本项目通过解决以下三个挑战来提高扩散源定位的技术水平：(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.