Quantifying network vulnerability, and the best way to find hidden items


Research news from the American Physical Society

1) How much do you need to know to take down the Mafia or destroy a computer network?

L. K. Gallos et al.
Phys. Rev. Lett. 94, 188701 (2005), 13 May 2005

Disrupting certain networks, such as the Internet or a Mafia ring, is very difficult without accurate information about the important network members. But, as you might imagine, knowing the identity of a few powerful mob Dons or critical network servers can make taking down a network much easier. Researchers at the University of Thessaloniki (Greece), Bar-Ilan University (Israel), and Justus-Liebig-Universitat Giessen (Germany) have quantified just how much easier it would be, given different levels of information.

In order to destroy a common type of network that scientists call "scale free", it may be necessary to disrupt (or arrest) essentially every member, if we know nothing about the relative importance of each of the members. Having reliable information about the top 1% of the most important nodes in a network means that the system could be destroyed by attacking as few as one fourth of the network members. Knowing the relative importance of all the members will allow you to destroy a network by taking out about 7% of the nodes.

It should come as no surprise that crime rings and terrorist networks go to great trouble to keep their most powerful and highly connected members secret. The bottom line: secrecy is the best defense for networks under attack, and good intelligence is vital for taking networks down. The researchers note that their analysis is also applicable to controlling the spread of contagious disease through vaccinations in populations connected by social networks.

2) Want to know the best way to find your lost sock? Ask an animal.

O. Benichou et al.
Physical Review Letters, upcoming article

What is the fastest way to locate a randomly hidden object? Animals searching for food may instinctively be following the best strategy. In this paper, the authors model a search as alternating between two phases - a slow, systematic search phase during which a forager scans an area, and a fast phase in which the searcher darts to another area before beginning another slow search phase. To minimize the time needed to find the object, the researchers calculate that the average time spent in "motion" phases should vary as either the 3/5 or 2/3 power of the average duration of the "search" phases. Comparing their model with experimental data from 18 different foraging species, including fish, birds, and lizards, the authors find that the animals actually do follow this optimal strategy. The authors believe the model could also apply to many other situations, including human searching behaviors. So you might want keep it in mind next time you lose your keys.

Source: Eurekalert & others

Last reviewed: By John M. Grohol, Psy.D. on 21 Feb 2009
    Published on PsychCentral.com. All rights reserved.



Excess on occasion is exhilirating. It prevents moderation from acquiring the deadening effect of a habit.
-- William Somerset Maugham