Algorithm Can Track Source Of Facebook Rumors And Terrorist Attacks, Researchers Say

Could mathematics allow us to pinpoint the source of a rumor on Facebook, a cholera outbreak, or a poison gas attack? That's what a trio of researchers from Ecole Polytechnique Fédérale de Lausanne in Switzerland think.

In a paper published Friday in the journal Physical Review Letters, the team of Pedro Pinto, Patrick Thiran and Martin Vetterli outlined an algorithm they've developed that can track something -- information, contaminants, influence -- as it spreads through online and offline networks, back to its original source. The method could allow law enforcement agencies to zero in on the leader of a terrorist organization even if they're only monitoring a couple of members in the group.

Pinto explained in a phone interview that their algorithm is inspired by cell phone triangulation, the technique by which a person's location can be pinpointed based on a phone call. Triangulation works by figuring out the distance between a phone and three or more cell stations. Those three distances form the radii of three different circles, which intersect at the call's origin.

"We took that triangulation technique and applied it to networks," Pinto said.

In a network, instead of cell stations, one can monitor the nodes of a network, also called "sensors." A node can be many things - a Facebook friend, contimination in a small tributary in an interconnected water supply, or an informant in a criminal organization.

In order to be able to use the algorithm, you usually need to be able to monitor 10 to 20 percent of the nodes in the network, according to Pinto. Choosing which nodes to monitor can also make it easier to pinpoint the center of the contamination or rumor, or the leader in a group.

"One good strategy is to choose the best-connected nodes. So with tracking something on Facebook you probably want to monitor the people who have the most friends," Pinto said.

Already there are hypothetical scenarios in which the algorithm could be useful and practical. A city may want to place sensors in its subway system to detect chemical attacks, but might not be able to afford putting them in every single station. Using the algorithm, the city would be able to use just a few sensors to nail down the source of any attack.

In their paper, Pinto and his colleagues tested their method on the network of Al-Qaeda members involved in the hijacking of planes on September 11, 2001. They used two of the suspected Al Qaeda members as nodes and tried to predict the ringleader. Based on the network of messages exchanged, the researchers identified Mohamed Atta, the hijacker of American Airlines Flight 11, as one of the leaders -- aligning with what U.S. officials have claimed.

The algorithm isn't a magic bullet, though. There needs to be a particular thing that is propagating through the network - so some groups, like an assortment of Anonymous hackers, might form a network but wouldn't be passing around a singular meme that could be traced back to an origin point. It's a case by case basis, according to Pinto.

"As long as there's something diffusing, I think we can deal with it," Pinto says.

SOURCE: Pinto et al. "Locating the Source of Diffusion in Large-Scale Networks." Physical Review Letters 109, 068702 (2012).