Expansionary Institute

Michael Zey
futurist3000@aol.com

First Cells, Then Species, Now the Web

December 26, 2000

By GEORGE JOHNSON, New York Times

As the Internet continues to proliferate, it has become natural to
think of it biologically   as a flourishing ecosystem of computers
or a sprawling brain of Pentium-powered neurons. However you mix
and match metaphors, it is hard to escape the eerie feeling that an
alien presence has fallen to earth, confronting scientists with
something new to prod and understand.

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."

At the Polytechnic University of Catalonia in Barcelona, Dr.
Ricard V. Sol  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. Sol , who also works at the Santa Fe Institute in New
Mexico.

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.
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.

"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."
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.

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.
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. Sol  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.

"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."