Scale-free network

A scale-free network is a specific kind of network in which the distribution of connectivity is extremely uneven. Instead, in scale-free networks, some nodes act as "very connected" hubs using a power-law distribution (described more formally below).

This kind of connectedness dramatically influences the way the network operates, including how it responds to catastrophic events. The Internet, World Wide Web and many other large-scale networks have been shown to be scale-free networks.

The term "scale-free" was first coined by physicist Albert-Laszlo Barabasi[?] and his colleagues at the University of Notre Dame in Indiana. In 1998, they mapped the connectedness of the World Wide Web and found, to their surprise, that the web did not have an even distribution of connectivity (so-called "random connectivity"). Instead, a very few network nodes (called "hubs") were connected to other nodes far more than other nodes. In general, they found that the probability P(k) that a node in the network connects with k was, in a given network, proportional to k^−γ. They named this kind of network connectivity "scale-free".

They also argued that there is a simple explanation for this behavior. Many networks expand through the addition of nodes to an existing network, and those nodes attach preferentially to nodes already well-connected. When this is the case, a scale-free network naturally arises.

Since that time, it has been found that many networks (including those describing interrelationships of objects) are, in fact, scale-free. Thus, scale-free networks have been identified in the dispersal of sexually transmitted diseases, power grid[?] design, and many different kinds of computer networks.

Many have studied collaboration networks; in collaboration networks, nodes represent people, and the links between nodes represent some kind of collaboration between them. Many of these have also been found to be scale-free networks. These studies are not limited to collaboration of real people; one study of Marvel comic book characters (where the nodes were comic characters, and links were simultaneous appearance in the same comic book) found that their interrelationships were also scale-free.

Computer networks that are also scale-free networks are significantly different from random connectivity networks in the presence of failure. If nodes fail randomly, scale-free networks behave even better than random connectivity networks, because random failures are unlikely to harm an important hub. However, if the failure of nodes is not random, scale-free networks can fail catastrophically. For example, an intelligent attacker can essentially destroy an entire scale-free network by intelligently identifying and attacking the key hubs of a scale-free network. Thus, the realization that certain networks are scale-free is important to security.

References

• Alberich, R., J. Miro-Julia, and F. Rossello. "Marvel Universe looks almost like a real social network" (http://arxiv.org/pdf/cond-mat/0202174).
• Barabasi, Albert-Laszlo and Reka Albert. "Emergence of scaling in random networks" (http://www.nd.edu/~networks/Papers/science.pdf). Science, 286:509-512, October 15, 1999.
• Matlis, Jan. Scale-Free Networks (http://www.computerworld.com/networkingtopics/networking/story/0,10801,75539,00). ComputerWorld. November 4, 2002.