| SiteMap |
| To search, type one or more key words below. |
This is a menu of the topics on this page (click on any):
The result has been an eruption of papers scrutinizing this artificial
network and concluding, to many people's surprise, that it may be designed
according to the same rules that nature uses to spin webs of its own. The
networks of molecules in a cell, of species in an ecosystem, and of people in a
social group may be woven on the same mathematical loom as the Internet and the
World Wide Web.
''We are getting to understand the architecture of complexity,'' said Dr.
Albert-Laszlo Barabasi, a physicist at the University of Notre Dame in Indiana
whose research group has recently published papers comparing such seemingly
diverse systems as the Internet and the metabolic networks of life-sustaining
chemical reactions inside cells. The similarities between these and other
complex systems are so striking, he said, ''it's as if the same person would
have designed them.''
In the past, scientists treated networks as though they were strung together
at random, giving rise to a homogeneous web in which nodes tended to have
roughly the same number of links. ''Our work illustrates that in fact the real
networks are far from being random,'' Dr. Barabasi said. ''They display a high
degree of order and universality that has been rather unexpected by any
accounts.''
As they come together, many networks seem to organize themselves so that most
nodes have very few links, and a tiny number of nodes, called hubs, have many
links. The pattern can be described by what scientists call a power law. To
calculate the probability that a node will have a certain number of links, you
raise that number to some power, like 2 or 3, and then take the inverse.
Suppose, for example, that you have a network with 100,000 nodes that obeys a
power law of 2. To find out how many nodes have three links, you raise 3 to the
second power, which is 9, and then take the inverse. Thus one-ninth of the
nodes, or about 11,111, will be triple linked. How many will have 100 links?
Raise 100 to the second power, and take the inverse: one ten-thousandth of the
100,000 nodes -- a total of 10 -- will be so richly connected. As the number of
connections rises, the probability rapidly falls.
This kind of structure may help explain why networks ranging from metabolisms
to ecosystems to the Internet are generally very stable and resilient, yet prone
to occasional catastrophic collapse. Since most nodes (molecules, species,
computer servers) are sparsely connected, little depends on them: a large
fraction can be plucked away and the network will endure. But if just a few of
the highly connected nodes are eliminated, the whole system could crash.
''The important point is that the networks are very different from our
familiar model systems,'' said Dr. Mark Newman, a mathematician at the Santa Fe
Institute. ''This means that all our previous theories have to be thrown out.''
The phenomenon has been popularized by a Web site, the Oracle of Bacon, at
the University of Virginia's computer science department
(www.cs.virginia.edu/oracle/) that calculates how closely an actor is linked to
the film star Kevin Bacon. Patrick Stewart of Star Trek fame, for example, has a
''Bacon number'' of 2: he was in ''The Prince of Egypt'' with Steve Martin, who
was in ''Novocaine'' with Kevin Bacon.
''The real point is not to establish that everything is a power law,'' he
said, ''but to start modeling complex networks in a way that is informed by the
data.''
At the Polytechnic University of Catalonia in Barcelona, Dr. Ricard V.
Sole and Jose M. Montoya, theoretical biologists in the Complex Systems Research
Group, have recently found the same kind of patterns by studying computer models
of three ecosystems: a freshwater lake, an estuary and a woods. ''These results
suggest that nature has some universal organizational principles that might
finally allow us to formulate a general theory of complex systems,'' said Dr.
Sole, who also works at the Santa Fe Institute in New Mexico.
Not everyone believes that a universal law is at hand. A recent paper by
Boston University physicists found deviations from the power-law pattern in a
number of different networks, suggesting a more complicated story. But even so,
the study found hidden orders that were far more interesting than the purely
random patterns scientists have long used to analyze networks.
It has only been in recent years that computer power has grown enough to
gather and analyze data on such intricate systems. In a highly publicized paper
in 1998, Dr. Duncan Watts, a sociologist at Columbia University, and Dr. Steven
Strogatz, an applied mathematician at Cornell University, found that many
networks exhibited what they called the small-world phenomenon, popularized in
John Guare's play ''Six Degrees of Separation.''
Just as any two people can be linked by a chain of no more than about six
acquaintances, so can any node in a small-world network be reached from any
other node with just a few hops. The two scientists found this hidden order in
three networks that could hardly seem more different: the web of neurons forming
the simple nervous system of the worm Caenorhabditis elegans, the web of power
stations forming the electrical grid of the Western United States and (the
finding that attracted the most attention) the web of actors who have appeared
together in films.
More recently Dr. Barabasi, working with a graduate student, Reka Albert,
and a post-doctoral researcher, Dr. Hawoong Jeong, found that the World Wide Web
is a small world -- a phenomenon also noticed by two researchers at the Xerox
Palo Alto Research Center in California, Dr. Bernardo A. Huberman and his
student Lada A. Adamic. Any two documents or sites on the Web are separated by
only a small number of mouse clicks.
The two teams also noted that the Web was structured according to a power
law, with a handful of highly connected hubs and a steadily increasing number of
less connected nodes -- a fact noticed by other groups as well.
Reaching further, Dr. Barabasi and Ms. Albert found, in a paper last fall
in Science, that a variety of networks may be organized this way. Included in
their list were the small worlds of Dr. Watts and Dr. Strogatz as well as the
connections on a computer chip and a network of citations in scientific
publications.
The question is how this kind of order arises. In the same paper, the
Barabasi group proposed a ''rich get richer'' effect: as new nodes are added to
a network, they tend to form links with ones that are already well connected.
New actors are more likely to be cast in films with well-known actors. New
scientific papers are more likely to cite well-established ones. The result,
according to their model, is a power-law distribution.
Their most recent sighting of the pattern was described in the Oct. 5
issue of Nature. Dr. Barabasi and his team worked with two members of the
Northwestern University Medical School department of pathology to study the
shape of metabolisms, the networks of chemical reactions inside living cells.
Small molecules are linked to form large molecules, which are in turn broken
back down into small molecules. But complex as these networks can be, they seem
to obey a power law. In a paper recently submitted to the Journal of Theoretical
Biology, Dr. Sole and Dr. Montoya found a similar pattern in the ecosystems they
studied.
The implication is that all these networks are extremely robust,
shrugging off most disturbances, but vulnerable to a well-planned assault. ''A
random knockout of even a high fraction of nodes will not damage the network,''
Dr. Barabasi said. ''But malicious attacks can.''
Suggestive as the new theory is, other scientists are finding that the
picture may not be so simple. In a paper published in October in the Proceedings
of the National Academy of Sciences, Dr. Luis A. Nunes Amaral and his colleagues
at Boston University analyzed a number of networks, including some of those
studied by the Barabasi group. The list also included the hubs and spokes of the
world airport system and two small friendship networks formed by a group of
Mormons and by junior high school students. They concluded that while some
networks obey power laws, in many others the pattern is distorted or
nonexistent.
The deviations arise, the study proposed, because it is not always easy
to add new nodes to a net: actors with more movie credits will attract more and
more collaborators -- until they get too old to act at all. Airports can only
support so many new flights a day. Because of such complications, a network may
fall somewhere on a spectrum between the extremes of randomness and order.
Researchers are optimistic that they will sort out the details of a
discipline that is still in its infancy. More important than any particular
study, Dr. Watts said, is that scientists finally have the computer power to
study real networks instead of just speculating about idealized ones.
Related Terms: