An algorithm to trace the source of crimes, epidemics or rumors


Up one source is often a difficult job, which could be facilitated by a new discovery. A Portuguese researcher at the Ecole Polytechnique Federale de Lausanne (EPFL) has developed a mathematical system to identify the source of information circulating on a network, an epidemic or a terrorist attack, announced Friday, August 10 EPFL. His research is published in the journal Physical Review Letters.

The researcher Petro Pinto, who works for the Audiovisual Communications Laboratory at EPFL, has developed a system "that could prove a valuable ally" for those who must conduct criminal investigations or seeking the origin of information on the Web. "With our method, we can trace the source of all types of information flowing through a network and that by not listening to a small number of members," said Pedro Pinto.


For example, it says to be able to find the author of a rumor circulating among five hundred members of the same network, like Facebook, by observing the messages from fifteen to twenty contacts only. "Our algorithm is able to repeat in reverse the path taken by the information, and trace the source," he said. The researcher also tested the system to trace the origin of an infectious disease in South Africa. "By modeling the network traffic, rivers or human transport, we were able to find the place where the first cases are reported," he said.

The researcher has also experienced its system of telephone calls related to preparation of the attacks of September 11, 2001. "By rebuilding the network of terrorists solely on the basis of reports in the press, our system has given us three possible suspects, one of which was the proven leader of these attacks, according to the official investigation." The details of this algorithm are published on Friday.

From Locating the Source of Diffusion in Large-Scale Networks publication:

How can we localize the source of diffusion in a complex network? Due to the tremendous size of many real networks—such
as the Internet or the human social graph—it is usually infeasible to observe the state of all nodes in a network. We show that
it is fundamentally possible to estimate the location of the source from measurements collected by sparsely-placed observers.
We present a strategy that is optimal for arbitrary trees, achieving maximum probability of correct localization. We describe
efficient implementations with complexity O(N ), where = 1 for arbitrary trees, and = 3 for arbitrary graphs. In the
context of several case studies, we determine how localization accuracy is affected by various system parameters, including
the structure of the network, the density of observers, and the number of observed cascades.

Pedro Pinto page »