杏吧原创

ALL researchers dream of making a discovery that will transform their field. Albert-L谩szl贸 Barab谩si can go one better. In just three years, his discovery has started making waves in fields as diverse as ecology, molecular biology, computer science and quantum physics.

It all began when he found that sites on the Web form a network with unique mathematical properties. In itself, this may not seem very profound, but it soon emerged that these properties were not unique to the Web. We are surrounded by networks: social, sexual and professional. Ecosystems are networks, and even our bodies鈥攁nd the pathogens that lay us low鈥攁re kept alive by networks of chemicals. Barab谩si and others have found that many of these networks have the same architecture as the Web. They grow in much the same way and have the same strengths and weaknesses: understand one and you start to understand them all. Universal mathematical laws are rare in biology but, without meaning to, Barab谩si seems to have uncovered one.

Born in Romania and educated in Hungary, Barab谩si is now a professor of physics at the University of Notre Dame in Indiana. Until a few years ago, he was preoccupied with arcane fields such as the fractal nature of surfaces and the dynamics of granular materials such as sand. To understand all these fields needs a heavy dose of statistics, which is Barab谩si鈥檚 forte. He also had a long interest in complex networks, but information about them was sparse. By 1998, however, the tools for interrogating the Web had reached a level of sophistication that enabled Barab谩si to go exploring.

For theoreticians, the established way to model complex networks is with a random network. Make some dots on a page and start drawing lines between them at random. You end up with a network in which, on average, all the dots鈥攐r 鈥渘odes鈥濃�攈ave the same number of links. Now count the number of nodes with one link, two links and so on, and plot these numbers on a graph. You end up with a well-known distribution鈥攁 bell curve (see Graph).

This is what Barab谩si expected to find when he and his colleagues R茅ka Albert and Hawoong Jeong started studying the Web. They sent a software robot crawling around the Web to analyse the links between websites. But when they looked at the architecture of the Web and plotted the distribution of sites and the numbers of links to them, something strange happened. 鈥淚t became clear we were looking at a more complex situation than that described by random networks,鈥� Barab谩si says.

There was no bell curve. Instead, the Web had lots of sites with a few links, a few sites with a medium number of links and a very few sites with loads of connections. This produced an ever-decreasing curve characteristic of what physicists call a power law (New 杏吧原创, 8 November 1997, p30). Gone was the average number of links鈥攐r scale鈥攐f the bell curve. Instead, announced Barab谩si, the Web was a 鈥渟cale-free鈥� network.

鈥淭his distribution,鈥� says Barab谩si, 鈥減oints to the fact that the Web鈥檚 structure is dominated by a few, highly connected sites.鈥� He calls these sites 鈥渉ubs鈥濃�攃lassic examples are Yahoo and Napster鈥攚hich have developed because they offer short cuts to the information we want.

A curious property of this architecture is that it takes only a few clicks to get from one site to any other on the Web. 鈥淥n average, the journey from one Web page to any other can be made in just 19 clicks,鈥� he says. This shows that the Web is a type of 鈥渟mall world鈥�, a concept made popular by John Guare in his play Six Degrees of Separation.

In turn, Guare based his work on the idea that a message between any two individuals on the planet would only need to pass through an average of six intermediaries (New 杏吧原创, 4 December 1999, p 24). This small-world property is essential to future growth because it means that as more sites come online, the Web will stay easy to navigate. Even if it grows by 1000 per cent, Barab谩si calculates that websites would still be separated by an average of only 21 clicks.

At first, Barab谩si thought his scale-free structure was unique to the Web. But he soon discovered the same pattern in other networks, such as the Kevin Bacon game (). Picture all the world鈥檚 actors as nodes with links between them when they鈥檝e appeared together in a movie. The aim is to link an actor to Bacon through the smallest number of other actors. Barab谩si found that the actors鈥� network is dominated by a few, usually famous actors, such as Bacon, who appear as hubs because they鈥檝e made so many films.

Since then, numerous other networks have been added to the list of the scale-free, not least the network of computers that underlies the Web itself鈥攖he Internet. In biology, the grids of interacting proteins and chemicals that keep cells in good working order are scale-free. Food webs鈥攖he networks of who eats whom in various ecosystems鈥攁re built around 鈥渉ub species鈥� that eat large numbers of different prey species (New 杏吧原创, 18 August 2001, p 30). And in human society, the network of scientists who鈥檝e worked together is scale-free, as is the way they cite each other鈥檚 research. Even the web of human sexual contacts turns out to be scale-free.

So Barab谩si鈥檚 work has begun to expose a pattern of organisation that crops up time and again in natural and artificial worlds. Somehow, the collective actions of individual agents鈥攂e they websites or proteins鈥攇enerate networks that conform to a single, well-defined mathematical formula. And every agent in all these systems seems to share the same behaviours.

It didn鈥檛 take Barab谩si and his team long to pin down these shared features. They found two vital ingredients. First, a scale-free network must be growing鈥攕o the Web needs new pages to be added every day, and the actors鈥� network needs a constant supply of raw talent. Second, these new recruits must show some form of preference as they attach to the network. So, for example, new websites want to be picked up by popular sites, such as Yahoo, to increase their traffic. And ambitious actors want to appear in films with established stars, rather than unknown B-movie actors. In general, then, the highly connected tend to become even more connected or, if you like, 鈥渢he rich get richer鈥�.

For some scale-free networks, the preferences at work are not clear. It鈥檚 absurd, for example, to think that prey species choose to be eaten by a predator with a particularly varied diet. Nonetheless, solving this puzzle will undoubtedly improve our understanding of how ecosystems evolve. With proteins, one candidate for this 鈥減reference鈥� mechanism is gene duplication鈥攁 rare occurrence during cell division when genes are copied twice. Every time this happens, all the proteins that interact with the duplicated protein gain another link.

Robust yet vulnerable

If the discovery that scale-free networks are everywhere is presenting us with new answers and questions about the world, so too are their properties. These networks are robust and vulnerable at the same time. Barab谩si, Albert and Jeong subjected a scale-free network to two types of attack. In one, they hit individual nodes at random, while in the other they only took out the hubs鈥攖he highly connected nodes in the network.

Random networks are highly susceptible to indiscriminate attacks. As more and more nodes are destroyed, the number of steps needed to get from one node to another increases steadily. By contrast, scale-free networks are robust in the face of such attacks. Even with 5 per cent of the nodes obliterated, the performance of the network is unaffected.

With highly targeted attacks, random networks decay in the same way as with indiscriminate attacks, but scale-free networks fare much worse. Once 5 per cent of the hubs have been removed, the number of steps needed to cross the network doubles. 鈥淭his shows that scale-free networks, in general, are highly vulnerable to intelligent attack,鈥� says Barab谩si. It exposes the Internet鈥檚 Achilles鈥檚 heel鈥攖he hubs. 鈥淚f hackers wanted to, they could probably bring down the Internet very easily,鈥� he adds.

The same vulnerability may also show up in protein networks鈥攚ith disastrous results. In 1979, p53 was the first gene to be identified as suppressing the development of tumours. To do this, it codes for a protein that controls the activity of a large number of other proteins. 鈥淚t seems p53 is a hub,鈥� says Bert Vogelstein of Johns Hopkins University in Baltimore. 鈥淚t is one of the few genes whose failure causes such cata-strophic results in the cell.鈥� In a paper in Nature (vol 408, p 307), Vogelstein, David Lane of the University of Dundee and Arnold Levine from Rockefeller University in New York likened the failure of p53 in a cell鈥攁nd the development of cancer鈥攖o the collapse of a hub on the Web and the subsequent crash.

Viewing protein networks as scale-free could help develop more realistic approaches to treatment for cancer, says Vogelstein. But he stresses it鈥檚 still early days. 鈥淲e鈥檙e far away from understanding all the biochemical interactions in a cell,鈥� he says.

For any disease, seeing proteins as actors within a larger play will help drug designers to aim their chemicals in such a way that they don鈥檛 disrupt the whole performance. Blocking a hub protein, for example, would be very risky because of the large number of potential side effects it could cause, not to mention the possibility of destroying cells. Conversely, there may be times when you want to wipe out cells. Barab谩si and his colleagues have shown that the protein network in Helicobacter pylori, the bacterium thought to cause peptic ulcers, is scale-free. Knocking out hub proteins in this bug could be a good way to disable or even kill it.

At the evolutionary level, scale-free networks may have succeeded not only because they are robust in the face of random errors, but also because they allow variation to take place. Proteins with only a few connections could mutate or be lost entirely without damaging the health of the organism. Some of these mutations could give it an advantage, allowing it to outcompete its rivals.

Perhaps the most surprising property of scale-free networks emerged last year and is changing our understanding of the way diseases spread among humans. Once again the story begins with the Net, when Alessandro Vespignani of the International Centre for Theoretical Physics in Trieste and Romualdo Pastor-Satorras of the Technical University of Catalonia in Barcelona decided to look at how computer viruses spread across the Net.

According to epidemiologists, a virus must reach a certain level of virulence for an outbreak to occur. Below this 鈥渆pidemic threshold鈥�, the virus is not infectious enough to spread quickly and dies out. The higher above the threshold it is, the faster it will spread. But when Vespingnani charted the movement of his software virus across the Internet, he got a shock. 鈥淭here is no such threshold for an outbreak to occur,鈥� he says. 鈥淭he hubs propagate viruses so efficiently that even a weak virus will spread rapidly through these nodes.鈥� This discovery has profound implications not only for the Net, but also for human disease. 鈥淚t is a breakthrough in the understanding of a certain class of epidemics,鈥� Vespignani says (Physical Review Letters, vol 86, p 3200).

This discovery gave Fredrik Liljeros, a sociologist at the University of Stockholm, the impetus to look at how human diseases spread. Studies by Vespignani and Barab谩si had concluded that the way HIV spreads through populations is similar to the spread of viruses on the Net. So Liljeros chose to look at sexually transmitted diseases.

Sexual networking

He and his colleagues studied the sexual habits of 2900 Swedes. It came as no surprise that a few 鈥渉ubs鈥� had lots more sexual partners than the rest. But Liljeros also recognised this distribution of partners as a mark of a scale-free network. 鈥淢aybe people become more attractive the more partners they get,鈥� he says. If so, it looks strangely like the preference mechanism needed to create a scale-free network.

Normally with a new vaccine, public health officials aim for blanket immunisation of at-risk people, setting a target for the percentage to be immunised. That percentage depends on the epidemic threshold of the disease-causing microbe. Liljeros鈥檚 findings suggest that this approach could have little or no impact. 鈥淚n diseases such as AIDS, targeting the most promiscuous individuals is the crucial factor,鈥� says Liljeros. 鈥淲e can attempt to stop the spread of a virus by blindly vaccinating huge groups, but without treating these key individuals we may never bring it under control.鈥�

It鈥檚 common sense that a programme of vaccination against sexually transmitted diseases should try to reach the most promiscuous individuals first. But the idea that health campaigns may be utterly worthless if they miss these people is a shock. For Vespignani, this mixture of the obvious and the unexpected shows the real value of the scale-free revolution. It gives a mathematical form to common-sense concepts鈥攚hich means theories can be tested and results understood. And it leads to important, non-obvious results. 鈥淣obody would have thought that there is no immunisation threshold in such networks,鈥� he says.

We can expect more surprises like this in future. How significant those surprises will be is hard to say: the concept of scale-free networks is only three years old, after all. Yet it鈥檚 difficult to conceive that a theory which predicts the behaviours of both a collection of inanimate chemicals and a group of thinking humans is not telling us something profound about nature.

The idea has already been jumped upon by AIDS researchers, computer network designers and ecologists. For Barab谩si it鈥檚 this pervasiveness that gives scale-free networks their significance. 鈥淚t is not that they are creating a revolution in any single field,鈥� he says. 鈥淩ather, they prompt us to use the same tools, methods and approach to study very disparate systems.They allow us to see in a new and very similar perspective all the nodes and links around us.鈥�

If there is one way that scale-free networks are destined to make their mark, it could be in helping us to understanding emergence: the idea that many interacting agents following simple rules can collectively produce complex behaviours. So thousands of ants can produce a thriving colony that behaves like a single organism.

The challenge facing scientists now is to work out how the rules governing individual agents relate to large-scale behaviours. Scale-free networks give us the beginnings of a mathematical way to study that relationship. They are unlikely to be the whole answer, but they are at least a start.

REAL-WORLD problems have a habit of tripping up mathematical models, and scale-free networks are no exception.

Take the network of airports and flight routes. Newcomers to the airline business will want to connect to a hub鈥攁n airport with a huge number of connecting flights. But what happens when a hub is so busy it becomes saturated, as it has in the US? The newcomer must then choose a less well-connected airport. 鈥淢any real-world situations that at first seem to be scale-free networks in fact turn out not to be,鈥� says Lu鈥檚 Amaral of Boston University. This is because constraints on their behaviour restrict how they can evolve (Physical Review Letters, vol 88, p 138,701).

There are other imperfections. When a new site connects to the Web, its owners must convince the best 鈥渉ub鈥� sites to link to it. But because they cannot see the whole Web they may not choose the most popular hubs. Or an actor may not crop up in the Kevin Bacon game because of a personal preference for low-budget films rather than blockbusters. These kinds of events inevitably upset the perfect 鈥減reference mechanism鈥� that is assumed for creating the ideal scale-free network. 鈥淭he ramifications of this could change our understanding of scale-free networks,鈥� Amaral says.

Barab谩si says these issues do not detract from the importance of his ideas. 鈥淥f course you can destroy the scale-free state if you impose systematic limitations on the nodes,鈥� he says. 鈥淓ach system has to be treated separately. It is not anybody鈥檚 goal to show that all networks are scale-free.鈥�

One limitation that Barab谩si has already addressed is competition between nodes. If the accumulation of links over time is the only important factor as networks grow, then the oldest nodes would always have the most links. But we know from the Web that some latecomers鈥攕uch as Yahoo鈥攈ave become much bigger hubs than some older sites. In biological parlance, they appear to be 鈥渇itter鈥� than other sites at making new links. So Barab谩si added a variable to his formulae to represent that fitness.

At this point, Barab谩si鈥檚 colleague Ginestra Bianconi made an extraordinary leap. She imagined nodes as energy levels, the links between them as particles in a gas moving between energy levels. Fitness determined the absolute energy of each node鈥攖he fitter a node, the lower its energy.

When she allowed the model to evolve, most of the particles connected to the fittest node鈥攖hey fell into the lowest energy level (Physical Review Letters, vol 86, p 5632). This, to a physicist, is precisely what happens during the formation of a Bose-Einstein condensate, a bizarre quantum state of matter that forms when atoms are cooled to within a whisker of absolute zero. It鈥檚 ironic that correcting the scale-free model to make it agree with the everyday should reveal the rarest of quantum phenomena.