Searching Information Sources in Networks

  • Ying, Lei (PI)

Project: Research project

Project Details


Who leaked classified information or started a rumor on online social networks? Who uploaded contraband materials to the Internet? Where are the sources of epidemics? These questions are of great importance to the worlds safety and security and to the Armys basic research in C4ISR systems, but are difficult to answer when the timestamps of information propagation are unavailable. Our preliminary result, however, suggests that it is possible to detect information sources (i.e., the sources of leaked classified information, rumors or epidemics) accurately by exploiting a sample path based approach. The approach is to identify the most likely sample path and view the source of the the optimal sample path as the information source. The PI has proved that the distance between the source detected by the sample path based approach and the actual source is a constant independent of the network size and the time at which the network is observed given a homogeneous Susceptible-Infected-Recovered (SIR) model and regular tree topologies. The objective of this project is to develop a comprehensive theory of searching information sources in general networks and under a heterogeneous SIR model. The following tasks will be accomplished in this project. Task 1: General networks and a heterogeneous SIR model. In this task, we will quantify the performance of sample path based algorithms in small world networks including the Erdos-Renyi network and Watts-Strogatz network and for a heterogeneous SIR model in which nodes have different infection and recovery probabilities. This task is expected to begin in the first year and be completed in the first half of the third year. Task 2: Detection of multiple information sources. In practice, information may start from multiple sources simultaneously. This multi-source diffusion adds another dimensionality of complexity to the problem, in particular, when the number of sources is unknown. In this task, we will develop theories and algorithms to estimate the number of sources and to identify the set of information sources in general networks and for a heterogeneous SIR model. The task is expected to begin in the first year and be completed in the third year. Task 3: Information source detection with partial observations. It is prohibitive to obtain a complete snapshot when the network size is large. The focus of this task is to identify information sources with partial observations. We will also develop novel techniques to combine multiple snapshots to improve the detection accuracy. The task is expected to begin late in the first year and be completed in the third year. Potential Impact on the Army: This project aims to contribute to Army capabilities by advancing fundamental understanding of network dynamics and information flow in technological and human networks. In particular, this project will establish a common theory for identifying the sources of computer virus on the Internet, the sources of epidemics in human networks, and the sources of leaked classified information or rumors on online social networks. These findings will help the Army scientists and engineers quickly identify the threat sources and increase the Army capabilities in cyber warfare.
Effective start/end date9/1/138/31/16


  • DOD-ARMY-ARL: Army Research Office (ARO): $300,000.00


Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.