CHOLERA is spreading through the villages of South Africa. Malicious rumours are proliferating on Facebook. These may be disparate situations in scope and impact, yet an algorithm similar to the one a cellphone uses to find its location can home in on the source of grief in both.
In each case, something is spreading through a network of interconnected nodes - in the first case, villages connected by roads, and in the second, people connected by online friendships - and there is a good reason to find the source, fast.
As checking each village, or friend's Facebook wall, would be slow and costly, computer scientist Pedro Pinto and colleagues at the Swiss Federal Institute of Technology in Lausanne turned to triangulation, a method used by cellphone networks to deduce someone's location.
A cellphone can be located via a process of deduction that combines the arrival time of simultaneous signals from just three cellphone towers. Pinto's team created a triangulation-like algorithm for networks in which the "signal" is whatever is being transmitted, be it disease or rumour. The algorithm uses the time a signal arrives at a number of nodes, together with a map of the network's structure, to deduce the most likely source node. So if two nodes on either side of a network see a signal at roughly the same time, the source must lie in the middle of the network; if one node sees it earlier, the source is likely to one side.
When the team tested their algorithm on data from a cholera outbreak that hit the KwaZulu-Natal province of South Africa in 2000, it homed in on a village within three nodes of the source, using time data from just 20 per cent of the villages (Physical Review Letters, DOI: 10.1103/PhysRevLett.109.068702).
That's close enough to help given that the network contained tens of villages. Pinto hopes the algorithm will reduce the cost of monitoring networks. "You want to deploy as few sensors as possible," he says.
Network researcher Tauhid Zaman of the Massachusetts Institute of Technology agrees that the algorithm would be particularly useful for disease monitoring, where it can be costly to test everyone in the network. But more measurements will be needed if there is more than one source, he adds.
- Subscribe to New Scientist and you'll get:
- New Scientist magazine delivered every week
- Unlimited access to all New Scientist online content -
a benefit only available to subscribers - Great savings from the normal price
- Subscribe now!
If you would like to reuse any content from New Scientist, either in print or online, please contact the syndication department first for permission. New Scientist does not own rights to photos, but there are a variety of licensing options available for use of articles and graphics we own the copyright to.
Have your say
Only subscribers may leave comments on this article. Please log in.
Only personal subscribers may leave comments on this article
All comments should respect the New Scientist House Rules. If you think a particular comment breaks these rules then please use the "Report" link in that comment to report it to us.
If you are having a technical problem posting a comment, please contact technical support.
0 komentar:
Posting Komentar