Nets mimic quantum physics

By Kimberly Patch, Technology Research News

Researchers from the University of Notre Dame have discovered a surprising parallel between the dynamics of large, complicated networks like the World Wide Web and the mathematics that predict the behavior of bosons, which are quantum particles like atoms or photons that transmit force.

They found that as a network matures, its nodes exhibit behavior that corresponds to the quantum behavior of gas atoms as they cool.

The researchers discovered the parallel unexpectedly when they were looking into the role of fitness in the growth of large, scale-free networks like the Internet, business markets and social relationships. These scale-free, or power-law networks naturally mature toward a small number of Web sites, companies or people with many connections, or links to other nodes, and a large number of nodes with only a few connections.

In many networks, the way nodes acquire connections depends on their fitness, or ability to compete for links, said Ginestra Bianconi, a graduate student at the University of Notre Dame. "For example, in social networks some individuals acquire more social links than others, or on the [Web], some Web pages attract considerably more links than others," she said.

The researchers found that in a particular condition of fitness distribution -- the winner-takes-all phase -- the most fit node was getting a certain fraction of all the links, a relationship that could be described mathematically. And as it turned out, the mathematics was familiar. "Our... equation had the same problems that appear in a Bose gas when there's a Bose[-Einstein] condensation," said Bianconi.

Bose-Einstein condensation occurs when a gas like rubidium is cooled almost to absolute zero. In this state a specific fraction of the gases' atoms are in their lowest energy state, where they snap into lockstep with each other, matching attributes and behaving like a single entity.

The mathematical similarities showed that the topological activity of the network in its mature, winner-takes-all phase acts like a Bose gas undergoing condensation, with nodes corresponding to energy levels and links to particles, said Bianconi. "The node of the network that has the highest fitness... corresponds to the lowest energy state occupied by a finite fraction of all the particles of the gas," she said.

When the researchers compared the two other distinct phases of a network -- the first-mover-advantage and the fit-get-rich phase -- with the thermodynamic phases of Bose gases, they found more mathematical similarities, this time with non-condensed Bose gases, said Bianconi.

The way the network acts depends on the distribution of fitness of the network, just as the behavior of a gas depends on its temperature, or the distribution of heat.

In the first-mover-advantage phase of a network, all the nodes have the same fitness, making seniority a big advantage. The first nodes arriving in the networks have more links than equally fit nodes that arrived later. "Thus, in order to overcome the connectivity of all the others a new node [requires more] fitness," said Bianconi. This corresponds to gas behavior at very high temperatures.

In a network’s fit-get-rich phase there is fair competition for links without a clear winner. Nodes that are more fit acquire links at higher rate than less fit ones, but each node has an infinitesimal fraction of the total number of links. This corresponds to gas behavior at intermediate temperatures.

Discovering connections like these should help in understanding the role of attributes like fitness in network structures like the Internet, said Bianconi. Although the complexity of many systems can be described by the underlying structure of their networks, the geometry of the structures is not well understood, she said. The scale-free nature of the Web, for example, was only recently described mathematically.

The work is somewhat unusual because it makes a rather surprising mathematical connection between quantum statistics and networks, said Mark Newman, a research professor of physics at Santa Fe Institute.

It is also useful, Newman said. "It makes a connection between something of great current interest, but about which our knowledge is at a rather early stage -- networks -- and something which we know a lot about -- Boson statistics. Thus it allows us to make use of a number of well-known and well understood results about Bosons to say things about networks, too."

The most important implications of the model concern how one competitor gets most of the business in certain circumstances, said Newman. The model shows that the amount of business -- like the number of links to a page or people using a product -- a given node gets depends on how much business it already has, and on its fitness, or how good its product is. "In some regimes, this results in one competitor cornering the market, a behavior very similar to what we see both in actual businesses, and network phenomenon such as links to Web sites," he said.

Although the business problem of preferential attachment, which concerns competitors getting business in proportion to how much they already have, has been well studied, the Notre Dame researchers' work brings the concept of fitness into the equation, Newman said.

The researchers are currently studying real-world networks in order to try to determine what phase those networks are in, said Bianconi. This is difficult because direct information about the fitness of nodes, which determines how well they compete, is hard to come by and can only be measured indirectly, she added.

The work on parallel network and gas phases could be used to better control networks within two years, Bianconi said.

Bianconi's research colleague was Albert-Lázló Barabási. They published the research in the June 11, 2001, 2001 issue of Physical Review Letters. The research was funded by Notre Dame University.

Timeline:   < 2 years
Funding:   University
TRN Categories:  Applied Computing; Networking
Story Type:   News
Related Elements:  Technical paper, "Bose-Einstein Condensation in Complex Networks," Physical Review Letters, June 11, 2001.


August 22/29, 2001

Page One

Nets mimic quantum physics

Teamed filters catch more spam

Software eases remote robot control

Ion beams mold tiny holes

Unusual calms tell of coming storms


Research News Roundup
Research Watch blog

View from the High Ground Q&A
How It Works

RSS Feeds:
News  | Blog  | Books 

Ad links:
Buy an ad link


Ad links: Clear History

Buy an ad link

Home     Archive     Resources    Feeds     Offline Publications     Glossary
TRN Finder     Research Dir.    Events Dir.      Researchers     Bookshelf
   Contribute      Under Development     T-shirts etc.     Classifieds
Forum    Comments    Feedback     About TRN

© Copyright Technology Research News, LLC 2000-2006. All rights reserved.