Bulletin, February/March 2007


Annual Meeting Coverage


Plenary Address
The Architecture of Complexity: Albert-László BarabásiAlbert-László Barabási

by Steve Hardin

Steve Hardin is associate librarian at Indiana State University and can be reached by email at shardin1<at>isugw.indstate.edu. 
Albert-László Barabási is the Emil T. Hofman Professor and director of the Center for Complex Network Research (CCNR) at the University of Notre Dame, Department of Physics, 225 Nieuwland Science Hall,
Notre Dame, IN 46556-5670.

An expert on networks and their nature revealed some of the surprising laws which govern networks during the opening plenary session of the 2006 Annual Meeting of the American Society for Information Science and Technology in Austin, Texas. Albert-László Barabási directs the Center for Complex Networks Research in the physics department at the University of Notre Dame.

Barabási began by describing the Internet as a network of routers, with nodes and links. It’s becoming a truism that “Earth is developing an electronic skin.” With organizations, nodes are persons, and links are their communication patterns. He showed a map describing an organization’s links. He also showed a map of business ties in the U.S. biotech industry in 1988. Here, nodes are companies and links are collaborations, both financial and R&D. As a network matures, the nodes and links increase. Then Barabási showed another map of the “terrorist network.” In this case, nodes are individuals and links are public communications about then. He showed that some of the key players are connected to many links. 

Barabási described how researchers have thought about networks, beginning with the model proposed in 1960 by Paul Erdős and Alfréd Rényi. This model characterized networks as democratic and random. They said networks are simple – just nodes and links. But they’re complicated because we don’t know how the nodes are connected. The degree of a node corresponds to the number of links a node has. What is the probability that a node will have exactly k links? It’s a Poisson distribution. It has a major peak around the average. The nodes end up being very similar to each other. But real networks, Barabási said, are probably not that random. There are other organizing forces in society. 

To study these organizing forces, Barabási and his colleagues looked at the World Wide Web. Here, nodes are WWW documents; links are URL links. There are more than three billion documents. Where can you go from each document? They sent out a robot to collect all the URLs found in a document and follow them recursively. They discovered that the distribution followed a power law. A random network corresponds to the U.S. highway system, with many similar nodes and links. The scale-free network of the WWW is more like the airline transportation network, Barabási said. There are a few nodes – hubs – with many more links. There are a few major hubs and many smaller hubs with only a few links. “Average” doesn’t have much meaning in this sort of network. 

Barabási also showed maps of a metabolic network and protein interactions. They both resemble the scale-free network of the WWW. He also showed a copy of a network of the Swedish sex web. In this network, nodes are people; links are sexual relationships. This map was created to track the spread of AIDS and other sexually transmitted diseases. It showed that while most people have 1-10 sex partners, a few have thousands. Why do all these networks have similar architecture? 

Barabási and his colleagues found that networks continuously expand by the addition of new nodes. The WWW adds new documents. New nodes prefer to link to highly connected nodes. In the WWW, new pages link to well-known sites. We show a “preferential attachment” toward the more connected pages. There’s a “rich get richer” mechanism at work in the system. 

A big problem with this model, Barabási said, is that it predicts that only the oldest links will be the hubs because they’ve had more time to accrue links. But in the real world we have Google, a late starter which has accumulated many links. So, he added a “fitness” coefficient – in terms of the Web, how interesting is a page? Is someone likely to visit it more than once? It turns out the network grows in accordance with its nodes’ fitness. In real systems, nodes compete for links. We can also have the “condensation” predicted by Satyendranath Bose and Albert Einstein, in which one hub pretty much gets it all. The best example, he said, is Microsoft. 

Barabási also noted that some networks work well even with many malfunctions, while others fail with only a few. If you remove nodes from a random network, there is a critical point at which it fails. But for scale-free networks, the hubs keep things running – if you randomly remove nodes, you’re probably missing the hubs. However, such networks are vulnerable to attacks which remove the hubs. 

Real networks, he said, are fragmented into groups or modules. There are a few nodes that interconnect a lot, with weaker links to other clusters. Hierarchical networks are modular and scale-free. The clustering coefficient tells you how interconnected the friends of a node are. 
Barabási and his co-researchers have also studied how communities evolve over time. Small communities have a long lifetime if their members do not change. But large communities have a long lifetime if members change rapidly. So for large communities, stability means death. 

“Viral marketing” applies this knowledge to marketing. A good example is Hotmail, he said, which spread over the network very quickly. If you watch who talks with whom, you can get an idea of how fast ideas can spread on a network. If you give an idea to random individuals, the spread is rather slow. But if you choose the most active users on the network, the idea spreads very rapidly. 

Barabási concluded by stating he and his colleagues found that apparently unrelated networks behave in similar ways and have similar structures – they’re the result of similar laws. This knowledge allows us to have common thinking about networks. But many questions remain. How are the networks used? What are the dynamics of how they’re being used at the smallest scale? For more information, many of Barabási’s papers are available at www.nd.edu/~networks.