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
Referenced By
List of mathematical topics (S-U)
|
