Featured Research

from universities, journals, and other organizations

Random Network Connectivity Can Be Delayed, But With Explosive Results, New Study Finds

Date:
March 16, 2009
Source:
University of California - Davis
Summary:
A trio of mathematicians studying random networks has provided new evidence that connectivity can be appreciably delayed, but only at a cost. When it finally occurs, the transition is virtually instantaneous, like a film of water abruptly crystallizing into ice.

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.

Related Articles


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 Erdφs-Rιnyi 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, 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."


Story Source:

The above story is based on materials provided by University of California - Davis. Note: Materials may be edited for content and length.


Cite This Page:

University of California - Davis. "Random Network Connectivity Can Be Delayed, But With Explosive Results, New Study Finds." ScienceDaily. ScienceDaily, 16 March 2009. <www.sciencedaily.com/releases/2009/03/090312140844.htm>.
University of California - Davis. (2009, March 16). Random Network Connectivity Can Be Delayed, But With Explosive Results, New Study Finds. ScienceDaily. Retrieved October 25, 2014 from www.sciencedaily.com/releases/2009/03/090312140844.htm
University of California - Davis. "Random Network Connectivity Can Be Delayed, But With Explosive Results, New Study Finds." ScienceDaily. www.sciencedaily.com/releases/2009/03/090312140844.htm (accessed October 25, 2014).

Share This



More Computers & Math News

Saturday, October 25, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Real-Life Transformer Robot Walks, Then Folds Into a Car

Real-Life Transformer Robot Walks, Then Folds Into a Car

Buzz60 (Oct. 24, 2014) — Brave Robotics and Asratec teamed with original Transformers toy company Tomy to create a functional 5-foot-tall humanoid robot that can march and fold itself into a 3-foot-long sports car. Jen Markham has the story. Video provided by Buzz60
Powered by NewsLook.com
Microsoft Riding High On Strong Surface, Cloud Performance

Microsoft Riding High On Strong Surface, Cloud Performance

Newsy (Oct. 24, 2014) — Microsoft's Q3 earnings showed its tablets and cloud services are really hitting their stride. Video provided by Newsy
Powered by NewsLook.com
The Best Apps to Organize Your Life

The Best Apps to Organize Your Life

Buzz60 (Oct. 23, 2014) — Need help organizing your bills, schedules and other things? Ko Im (@konakafe) has the best apps to help you stay on top of it all! Video provided by Buzz60
Powered by NewsLook.com
Nike And Apple Team Up To Create Wearable ... Something

Nike And Apple Team Up To Create Wearable ... Something

Newsy (Oct. 23, 2014) — For those looking for wearable tech that's significantly less nerdy than Google Glass, Nike CEO Mark Parker says don't worry, It's on the way. Video provided by Newsy
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
 
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:  

Breaking News:

Strange & Offbeat Stories

 

Space & Time

Matter & Energy

Computers & Math

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:  

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile iPhone Android Web
Follow Facebook Twitter Google+
Subscribe RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins