Wednesday, March 29, 2006

The Power of Weak Links

Nexus: Small Worlds and the Groundbreaking Theory of NetworksExcerpt from: Nexus: Small Worlds and the Groundbreaking Theory of Networks

Paul Erdos, one of the greatest mathematicians of our era, discovered that no matter how many points there might be [in a network], a small percentage of randomly placed links [weak links] is always enough to tie the network together into a more or less completely connected whole. More suprisingly the percentage required dwindles as the network gets bigger.

For a network of 300 points, there are nearly 50,000 possible links that could run between them. But if no more than about 2 percent of these are in place, the network will be completely connected. For 1,000 points, the crucial fraction is less than 1 percent. For 10 million points, it is only 0.0000016.

No comments:

Post a Comment