New York University Skip to Content Skip to Search Skip to Navigation Skip to Sub Navigation

Connectivity in Random Networks Can Be Suppressed, but with Explosive Consequences

March 12, 2009
N-331, 2008-09

Alternate Contact: Liese Greensfelder | 530.752.6101 lgreensfelder@ucdavis.edu

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 random processes, 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 network formation, known as the Erdos-Renyi model, connections are added from among a large collection of points one at a time by randomly selecting a pair of points to connect. 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’s Courant Institute of Mathematical Sciences, 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 we must choose one. We have no control over which alternatives are presented, but we certainly can control what we choose.”

Spencer, also a consultant for Microsoft Research, noted the computer industry has long been interested in large networks.

“The World Wide Web can be regarded as a network, with web sites as nodes and links as adjacencies,” explained Spencer. “This network is constantly evolving and changing properties. Researchers in IT and related fields want to understand and predict those times when the evolution is rapid and drastic.”

This Press Release is in the following Topics:
Graduate School of Arts and Science, Research

Type: Press Release

The red points represent the formation of a super-connected group or "giant component" within a network. credit: Raissa D'Souza/UC Davis

The red points represent the formation of a super-connected group or "giant component" within a network. credit: Raissa D'Souza/UC Davis


Search News



NYU In the News

CUSP Unveils its “Urban Observatory”

Crain’s New York Business profiled CUSP’s “Urban Observatory” that is continuously photographing lower Manhattan to gather scientific data.

Post-Sandy Upgrades at the Langone Medical Center

NY1 reported on the major post-Sandy upgrades and renovations made at the Medical Center to protect the hospital from future catastrophic storms.

Steinhardt Research Helps Solve Tough Speech Problems.

The Wall Street Journal reported on research at Steinhardt’s Department of Communicative Sciences and Disorders, including an interview with Assistant Professor Tara McAllister Byun, that uses ultrasound to help solve tough speech problems.

Times Column Lauds Professor Stevenson’s New Memoir

New York Times columnist Nicholas Kristof wrote a column about “Just Mercy,” a new memoir by Law Professor Bryan Stevenson, the founder of the Equal Justice Initiative, whom he noted has been called America’s Nelson Mandela.

Entrepreneurship Lab Opens at NYU

Crain’s New York Business covered the opening of the Mark and Debra Leslie Entrepreneurial eLab, which will be the headquarters for NYU’s Entrepreneurial Institute and all of the University’s programs aimed at promoting innovation and startups.

NYU Footer