New technique minimizes observers for determining sources of outbreaks

In an epidemic, being able to identify the source that initiated a diffusion process can help mitigate outbreaks and reduce damage. However, incomplete and noisy data—such as not knowing the starting time of the process—makes this challenging. Currently, there is no method for determining the minimum number of observers necessary for locating the source of a process in a cyber-physical system. Existing studies randomly select the observers or select them according to network centrality measures or community structure.

With the goal of minimizing the number of observers necessary to locate the source, Hu et al. developed a new algorithm that only requires a small fraction of the nodes in a system to act as observers—about 10-20%. This is significantly less than using a random selection, which often requires more than 30% of the nodes to be observers.

The researchers’ new technique utilizes a greedy optimization algorithm to analyze the propagation delay difference between each pair of observers. By tapping into this difference, the researchers can trace back the diffusion chain using the smallest number of observers possible, leading them ultimately to the source node.

Locating a harmful diffusion source is important to maintaining security, and this method of observer minimization has the potential to improve the efficiency of maintaining cyber-security, detecting the spread of rumors, and regulating disease outbreaks. The researchers’ technique only focuses on locating a single source for now but could be generalized with more computational resources.

Source: “Locating the source node of diffusion process in cyber-physical networks via minimum observers,” by Z. L. Hu, L. Wang, and C. B. Tang, Chaos: An Interdisciplinary Journal of Nonlinear Science (2019). The article can be accessed at https://doi.org/10.1063/1.5092772 .