Towards a Theoretical Foundation for Diffusion Source Localization
NSF Award 1715385 - III: Small: Towards a Theoretical Foundation for Diffusion Source Localization
PIs: Lei Ying (UMich) and Hanghang Tong (UIUC)
Students: Zhen Chen (ASU), Chen Chen (ASU), Honghao Wei (UMich)
Duration: 09/01/2017 - 08/31/2020
Project Objectives:
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.
Key Publications:
- Z. Chen, H. Tong, L. Ying: Inferring Full Diffusion History from Partial Timestamps. IEEE Transactions on Knowledge and Data Engineering, March 2019.
- H. Wei, X. Kang, W. Wang, and L. Ying: QuickStop: A Markov Optimal Stopping Approach for Quickest Misinformation Detection. Proc. SIGMETRICS, June 2019.
- Y. Huang, L. Shi, Y. Su, Y. Hu, H. Tong, C. Wang, T. Yang, D. Wang, S. Liang: Eiffel: Evolutionary Flow Map for Influence Graph Visualization. TVCG 2019
- Y. Wang, Y. Yao, H. Tong, X. Huo, M. Li, F. Xu, J. Lu: Bug Localization via Supervised Topic Modeling. ICDM 2018: 607-616.
- C. Chen, R. Peng, L. Ying and H. Tong: Network Connectivity Optimization: Fundamental Limits and Effective Algorithms. KDD 2018 [accepted]
Software
- The source code of software bug localization has been made publicly available at at github: https://github.com/SoftWiser-group/STMLocator
- The source code of netrin is available at http://tonghanghang.org/netrin.html
Datasets
- Forthcoming
Educational/Broader Impact Activities:
- Tong co-organized a workshop on graph techniques for adversarial activities at IEEE BigData 2018.
- PIs also gave an invited talk at several universities (e.g., Syracuse, Notre Dame, University of Michigan, Cornell and Princeton), and SIGMETRICS CINS Workshop 2019.
- Tong and graduate student Liangyue Li gave a tutorial on network science of teams at KDD 2018.
* Acknowledgement: This material is based upon work supported by the National Science Foundation under Grant No. 1715385.
* Disclaimer: Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.