Random network connectivity can be delayed, but with explosive results, new study finds

Mar 12, 2009
The points in red represent the formation of a super-connected group or "giant component" within this network. Credit: Raissa D'Souza/UC Davis

In the life of many successful networks, the connections between elements increase over time. As connections are added, there comes a critical moment when the network's overall connectivity rises rapidly with each new link.

Now a trio of mathematicians studying networks in which the formation of connections is governed by , has provided new evidence that super-connectivity can be appreciably delayed. But the delay comes at a cost: when it finally happens, the transition is virtually instantaneous, like a film of water abruptly crystallizing into ice.

The team's findings — described in a paper with an accompanying commentary in the March 13 issue of the journal Science —could be useful in a number of fields: from efforts by epidemiologists to control the spread of disease, to communications experts developing new products.

"We have found that by making a small change in the rules governing the formation of a network, we can greatly manipulate the onset of large-scale connectivity," said Raissa D'Souza, an associate professor of mechanical and aeronautical engineering at UC Davis.

In the classic model of random networks, after a certain number of connections are made, overall connectivity begins to rise in a steep curve (ER). A new model that delays this transition results in overall connectivity occurring almost instantaneously at a critical moment, shown in this graph by the upward turn of the flat red line (PR). Credit: Raissa D'Souza/UC Davis

In the of formation, known as the Erdös-Rényi model, connections are added from among a large collection of one at a time by randomly selecting a pair of points to . Two points are considered to be in the same group if it is possible to go from one to another along a continuous line of connections. A group remains very small until the number of connections reaches at least half the number of points. After that, the growth of the largest group follows a steep upward curve.

D'Souza, along with co-investigators Dimitris Achlioptas at UC Santa Cruz and Joel Spencer at New York University, wanted to explore how a network would change if there were an element of choice injected into its formation. In their mathematical model, they considered two random connections in each step, and selected only one. To make their choice, they multiplied the number of points in the group linked to one end of a connection by the number of points linked to its other end. And in each case, they chose the connection that yielded the lower product.

As they expected, this process delayed the onset of super-connectivity. But the team's analysis provided strong evidence for a new phenomenon: when a system is suppressed like this, it builds up a kind of pressure. "This algorithm yields a very violent transition," Achlioptas said, "reaching a critical moment at which the probability that two points are connected jumps from essentially zero to more than 50 percent instantaneously."

Their calculations for this model have provided important insights that could be broadly applicable to understanding and influencing the behavior of various kinds of networks, D'Souza said, adding that the work should also spark a quest for a mathematical proof to back their findings, an endeavor that may require new mathematics.

"Consider this," she said. "Often we are presented with two alternatives, and must choose one. We have no control over which alternatives are presented, but we certainly can control what we choose."

Source: University of California - Davis

Explore further: US company sells out of Ebola toys

add to favorites email to friend print save as pdf

Related Stories

Why the Rich Get Richer

Apr 02, 2007

A new theory shows how wealth, in different forms, can stick to some but not to others. The findings have implications ranging from the design of the Internet to economics.

New insights into the dynamics of the brain's cortex

May 14, 2008

Using mathematics and a computer model of brain activity, Roberto Fernández Galán, Ph.D., an assistant professor of neurosciences at Case Western Reserve University School of Medicine, has shown a direct link between activity ...

Computer scientists put social network theory to the test

Aug 10, 2006

Ever since 1969, when psychologists Jeffery Travers and Stanley Milgram first explained that everyone was separated by only six connections from anyone else, researchers have created theoretical models of the networks that ...

Digital World Reveals Architecture of Evolution

Aug 07, 2006

The architecture that pervades biological networks gives them an evolutionary edge by allowing them to evolve to perform new functions more rapidly than an alternative network design, according to computer ...

Physicists model how we form opinions

Apr 14, 2008

In large part, a society’s image stems from its overall opinions – its political, religious, and ethical beliefs – and how much diversity it tolerates. For example, how do some areas develop images of ...

Recommended for you

US company sells out of Ebola toys

Oct 17, 2014

They might look tasteless, but satisfied customers dub them cute and adorable. Ebola-themed toys have proved such a hit that one US-based company has sold out.

New progress of the Neogene Suidae research

Oct 17, 2014

Dr. Hou Sukuan and Prof. Deng Tao from the Institute of Vertebrate Paleontology and Paleoanthropology(IVPP), Chinese Academy of Sciences reported a new species of Chleuastochoerus from the Linxia Basin, Gansu ...

Gypsies and travellers on the English Green Belt

Oct 17, 2014

The battle between Gypsies, Travellers and the settled community over how land can be used has moved to the Green Belt, observes Peter Kabachnik of the City University of New York.

Cadavers beat computers for learning anatomy

Oct 16, 2014

Despite the growing popularity of using computer simulation to help teach college anatomy, students learn much better through the traditional use of human cadavers, according to new research that has implications ...

User comments : 2

Adjust slider to filter visible comments by rank

Display comments: newest first

NeilFarbstein
1 / 5 (1) Mar 12, 2009
Sounds a lot like maxwell maltz's psyhocyberneics self help book. If you keep a goal in mind you can get there. Where can i get their report?
hpe
not rated yet Mar 28, 2009
It would be interesting to know if the onset of global connectivity can be delayed even more by making local choices that are yet more biased towards low connectivity.