SCN: Architecture of complexity

[Steve]

x-no-archive: yes

========================

(George Johnson, NY 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. 
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.  

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

Copyright 2000 The New York Times Company





* * * * * * * * * * * * * *  From the Listowner  * * * * * * * * * * * *
.	To unsubscribe from this list, send a message to:
majordomo at scn.org		In the body of the message, type:
unsubscribe scn
==== Messages posted on this list are also available on the web at: ====
* * * * * * *     http://www.scn.org/volunteers/scn-l/     * * * * * * *