Locating the source of spreading in complex networks

Locating the source that triggers a dynamical process is a fundamental but challenging problem in complex networks, ranging from epidemic spreading in the society and on the internet to the cancer metastasis in human bodies. An accurate localization of the source is inherently limited by our ability to simultaneously access the states of all nodes in large-scale complex networks, such as the time of being infected of each individual in a large population. This thus raise two invaluable questions: how to locate the source from limited observers and whether the given set of observer nodes can achieve full localization of the source at any possible location. Here we develop an efficient algorithm to locate the source of diffusion-like processes and offer a general locatability condition. We apply our framework to message forwarding in micro-blog, epidemic spreading and consensus dynamics, finding that by using our tools, the source can be precisely located in arbitrary networks insofar as the locatability condition is assured. Our tools considerably improve our ability to find the source in complex networks based on limited accessibility of nodal information and have implications in controlling a variety of dynamical processes taking place on complex networks, such as inhibiting epidemic and rumor spreading and eliminating the seed cell of cancer in bodies.