Locating the source of diffusion in complex networks by time-reversal backward spreading

Abstract

Locating the source that triggers a dynamical process is a fundamental but challenging problem in complex networks, ranging from epidemic spreading in society and on the Internet to cancer metastasis in the human body. An accurate localization of the source is inherently limited by our ability to simultaneously access the information of all nodes in a large-scale complex network. This thus raises two critical questions: how do we locate the source from incomplete information and can we achieve full localization of sources at any possible location from a given set of observable nodes. Here we develop a time-reversal backward spreading algorithm to locate the source of a diffusion-like process efficiently and propose a general locatability condition. We test the algorithm by employing epidemic spreading and consensus dynamics as typical dynamical processes and apply it to the H1N1 pandemic in China. We find that the sources can be precisely located in arbitrary networks insofar as the locatability condition is assured. Our tools greatly improve our ability to locate the source of diffusion in complex networks based on limited accessibility of nodal information. Moreover, they have implications for controlling a variety of dynamical processes taking place on complex networks, such as inhibiting epidemics, slowing the spread of rumors, pollution control and environmental protection.

16 pages, 5 figures, 2 tables

References in corpus (6)

• Mitigation of Malicious Attacks on Networks
• Searching for superspreaders of information in real-world social media
• Invasion threshold in heterogeneous metapopulation networks
• On the universality of the scaling of fluctuations in traffic on complex networks
• Identification of Patient Zero in Static and Temporal Networks - Robustness and Limitations
• Congestion diffusion and decongestion strategy in networked traffic

Cited by in corpus (14)

• Computational Socioeconomics
• Optimizing sensors placement in complex networks for localization of hidden signal source: A review
• Suppressing epidemic spreading by risk-averse migration in dynamical networks
• A generalized linear threshold model for an improved description of the spreading dynamics
• On the Properties of Gromov Matrices and their Applications in Network Inference
• Multiple propagation paths enhance locating the source of diffusion in complex networks
• Inferring Spatial Source of Disease Outbreaks using Maximum Entropy
• Information Evolution in Complex Networks
• Estimating Infection Sources in Networks Using Partial Timestamps
• The big bang of an epidemic
• Multiple predator based capture process on complex networks
• RSSI-based Secure Localization in the Presence of Malicious Nodes in Sensor Networks
• Reconstruction of Worm Propagation Path Using a Trace-back Approach
• Optimal Localization of Diffusion Sources in Complex Networks