Math algorithm tracks crime, rumours, epidemics to source

Aug 10, 2012
© Photos.com

(Phys.org) -- A team of EPFL scientists has developed an algorithm that can identify the source of an epidemic or information circulating within a network, a method that could also be used to help with criminal investigations.

Investigators are well aware of how difficult it is to trace an unlawful act to its source. The job was arguably easier with old, Mafia-style criminal organizations, as their more or less resembled predictable family trees.

In the Internet age, however, the networks used by organized have changed. Innumerable nodes and connections escalate the complexity of these networks, making it ever more difficult to root out the guilty party. EPFL researcher Pedro Pinto of the Audiovisual Communications Laboratory and his colleagues have developed an that could become a valuable ally for investigators, criminal or otherwise, as long as a network is involved. The team's research was published August 10, 2012, in the journal .

"Using our method, we can find the source of all kinds of things circulating in a network just by 'listening' to a limited number of members of that network," explains Pinto. Suppose you come across a rumor about yourself that has spread on Facebook and been sent to 500 people – your friends, or even friends of your friends. How do you find the person who started the rumor? "By looking at the messages received by just 15󈞀 of your friends, and taking into account the time factor, our algorithm can trace the path of that information back and find the source," Pinto adds. This method can also be used to identify the origin of a spam message or a computer virus using only a limited number of sensors within the network.

Out in the real world, the algorithm can be employed to find the primary source of an infectious disease, such as cholera. "We tested our method with data on an epidemic in South Africa provided by EPFL professor Andrea Rinaldo's Ecohydrology Laboratory," says Pinto. "By modeling water networks, river networks, and human transport networks, we were able to find the spot where the first cases of infection appeared by monitoring only a small fraction of the villages."

The method would also be useful in responding to terrorist attacks, such as the 1995 sarin gas attack in the Tokyo subway, in which poisonous gas released in the city's subterranean tunnels killed 13 people and injured nearly 1,000 more. "Using this algorithm, it wouldn't be necessary to equip every station with detectors. A sample would be sufficient to rapidly identify the origin of the attack, and action could be taken before it spreads too far," says Pinto.

Computer simulations of the telephone conversations that could have occurred during the terrorist attacks on September 11, 2001, were used to test Pinto's system. "By reconstructing the message exchange inside the 9/11 terrorist network extracted from publicly released news, our system spit out the names of three potential suspects – one of whom was found to be the mastermind of the attacks, according to the official enquiry."

The validity of this method thus has been proven a posteriori. But according to Pinto, it could also be used preventatively – for example, to understand an outbreak before it gets out of control. "By carefully selecting points in the network to test, we could more rapidly detect the spread of an ," he points out. It could also be a valuable tool for advertisers who use viral marketing strategies by leveraging the Internet and social networks to reach customers. For example, this algorithm would allow them to identify the specific Internet blogs that are the most influential for their target audience and to understand how in these articles spread throughout the online community.

Explore further: 'Moral victories' might spare you from losing again

More information: Locating the Source of Diffusion in Large-Scale Networks, by P. Pinto, P. Thiran, and M. Vetterli, Physical Review Letters, Aug. 2012.

Related Stories

Unraveling biological networks

Mar 05, 2012

A new approach to disentangling the complexities of biological networks, such as the way in which proteins interact in our body's cells has been developed by researchers in China. The team's algorithm could allow biologists ...

Spot a bot to stop a botnet

May 01, 2012

Computer scientists in India have developed a two-pronged algorithm that can detect the presence of a botnet on a computer network and block its malicious activities before it causes too much harm. The team ...

Researchers improve fast-moving mobile networks

May 21, 2012

Mobile ad hoc networks (MANETs) allow people in multiple, rapidly-moving vehicles to communicate with each other – such as in military or emergency-response situations. Researchers from North Carolina State University ...

Social networking for terrorists

May 04, 2009

A new approach to analyzing social networks, reported in the current issue of the International Journal of Services Sciences, could help homeland security find the covert connections between the people behind terrorist attack ...

How quickly things spread

Feb 21, 2012

Understanding the spread of infectious diseases in populations is the key to controlling them. If we were facing a flu pandemic, how could we measure where the greatest spreading risk comes from? This information ...

Recommended for you

Narcissistic CEOs and financial performance

51 minutes ago

Narcissism, considered by some as the "dark side of the executive personality," may actually be a good thing when it comes to certain financial measures, with companies led by narcissistic CEOs outperforming those helmed ...

Election surprises tend to erode trust in government

54 minutes ago

When asked who is going to win an election, people tend to predict their own candidate will come out on top. When that doesn't happen, according to a new study from the University of Georgia, these "surprised losers" often ...

User comments : 2

Adjust slider to filter visible comments by rank

Display comments: newest first

gmurphy
not rated yet Aug 11, 2012
'The validity of this method thus has been proven a posteriori', I very much doubt that, the method was 'proven' by analysing *simulated* networks. Whilst I don't doubt that the mathematical foundations upon which the method is based are sound, real-life data is so treacherously noisy that isolating a useful signal for feeding into the algorithm is actually the real problem that needs to be solved.
surbhijoshi31
not rated yet Aug 16, 2012
what are the device used to make abacus and the year that it occur in use before the invention of computer

mastermindabacus.com