Featured Research

from universities, journals, and other organizations

Rooting out rumors, epidemics, and crime -- with math

Date:
August 10, 2012
Source:
Ecole Polytechnique Fédérale de Lausanne
Summary:
Scientists have 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.

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.

Related Articles


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 hierarchical structures more or less resembled predictable family trees.

In the Internet age, however, the networks used by organized criminals 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 algorithm 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 Physical Review Letters.

Finding the source of a Facebook rumor

"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-20 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.

Trace the propagation of an epidemic

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.

Identifying the brains behind a terrorist attack

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 epidemic," 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.


Story Source:

The above story is based on materials provided by Ecole Polytechnique Fédérale de Lausanne. Note: Materials may be edited for content and length.


Journal Reference:

  1. Pedro C. Pinto, Patrick Thiran, and Martin Vetterli. Locating the Source of Diffusion in Large-Scale Networks. Phys. Rev. Lett., 10 August 2012 DOI: 10.1103/PhysRevLett.109.068702

Cite This Page:

Ecole Polytechnique Fédérale de Lausanne. "Rooting out rumors, epidemics, and crime -- with math." ScienceDaily. ScienceDaily, 10 August 2012. <www.sciencedaily.com/releases/2012/08/120810133151.htm>.
Ecole Polytechnique Fédérale de Lausanne. (2012, August 10). Rooting out rumors, epidemics, and crime -- with math. ScienceDaily. Retrieved April 19, 2015 from www.sciencedaily.com/releases/2012/08/120810133151.htm
Ecole Polytechnique Fédérale de Lausanne. "Rooting out rumors, epidemics, and crime -- with math." ScienceDaily. www.sciencedaily.com/releases/2012/08/120810133151.htm (accessed April 19, 2015).

Share This


More From ScienceDaily



More Computers & Math News

Sunday, April 19, 2015

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

WikiLeaks Refuses To Let Sony Hack Die, Posts Database

WikiLeaks Refuses To Let Sony Hack Die, Posts Database

Newsy (Apr. 17, 2015) — WikiLeaks&apos; Julian Assange says the hacked emails and documents "belong in the public domain." Video provided by Newsy
Powered by NewsLook.com
Scientists Create Self-Powering Camera

Scientists Create Self-Powering Camera

Reuters - Innovations Video Online (Apr. 17, 2015) — American scientists build a self-powering camera that captures images without using an external power source, allowing it to operate indefinitely in a well-lit environment. Elly Park reports. Video provided by Reuters
Powered by NewsLook.com
The State Of Virtual Reality

The State Of Virtual Reality

Newsy (Apr. 17, 2015) — Virtual Reality is still a young industry. What’s on offer and what should we expect from our immersive new future? Video provided by Newsy
Powered by NewsLook.com
Cybercrime Could Cost $400 Bln

Cybercrime Could Cost $400 Bln

Reuters - Business Video Online (Apr. 16, 2015) — Representatives from around 160 countries gather at the Hague to discuss cyber space and cyber security, including the dilemmas and challenges regarding the evolution of the internet. Ciara Lee reports. Video provided by Reuters
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
 
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:  

Breaking News:

Strange & Offbeat Stories

 

Space & Time

Matter & Energy

Computers & Math

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:  

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile iPhone Android Web
Follow Facebook Twitter Google+
Subscribe RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins