Beating the competition: Scientists discover how the size of networks can skyrocket

Jan 17, 2011
Competition between possible new links: If several new connections are possible (here indicated by the solid red line and the dotted red line), only the link that creates the smaller network is actually added (solid red line). Credit: Max Planck Institute for Dynamics and Self-Organization

(PhysOrg.com) -- A single new connection can dramatically enhance the size of a network – no matter whether this connection represents an additional link in the Internet, a new acquaintance within a circle of friends or a connection between two nerve cells in the brain. The results, which are published in Nature Physics, were part of a theoretical study carried out researchers from the Max Planck Institute for Dynamics and Self-Organization (MPIDS), the Bernstein Center for Computational Neuroscience Gottingen and the University Gottingen. This study mathematically describes for the first time the influence of single additional links in a network.

Imagine the following scenario: In your sports team you get to know a new player and arrange to go out and see a movie on the next weekend. The new team member brings along three friends - and suddenly by adding one new contact, your own circle of friends has grown by four people. Growth processes of this sort occur in many networks: Neurons in the brain constantly establish new connections, websites link to each other and a person travelling infected with influenza creates a network of infected places with each intermediate stop. From a scientist's point of view, such growth processes are still poorly understood: How does a network change when single links are added? How quickly does a network grow in this way?

To answer these questions, the scientists from Göttingen tracked the growth of networks link by link. A new connection, however, can not only add one new element. It can also merge two networks (as in the example in the sports team above). The researchers focused on a special form of network growth that introduces a form of competition between possible links: If several new connections are possible, only the one connection is created: the one that results in the smallest new network (see Figure 1). "There is evidence, that growing networks of neurons at first prefer forming small groups and thus roughly follow the growth process we discuss", says Jan Nagler, staff researcher at the University of Göttingen and the MPIDS.

The growth process of the networks described in the study. Left: In the beginning, only few elements joint to form many small networks. Middle: In the intermediate phase several mid-sized networks have been created. Right: In the end almost all elements are connected in one large network. Credit: Max Planck Institute for Dynamics and Self-Organization

The situation can be compared to the social contacts established in a summer camp for children, whose participants all don’t know each other at the beginning of their vacation. Most likely, the children will at first team up in small groups and pairs. If such a pair wants to expand its social circle, it typically proceeds cautiously, approaching another pair or a small group rather than a large clique. At the beginning of the vacation, the social networks within the camp therefore grow slowly. At the end, all children will have become acquainted: The network has then reached its largest possible size and connects all elements of the system.

“In our study we zoomed in on an intermediate growth phase. This phase arises after the elements have begun to sporadically connect into small groups, but before the entire system is linked”, explains Marc Timme, head of the Network Dynamics Group at MPIDS. How do the many small networks link to form a whole? Are several large networks created at the same time or does one dominant network develop that towers above the others? In addition to performing computer simulations, the Göttingen researchers were for the first time able to derive mathematical expressions that describe this growth phase link by link.

The scientists found that after a certain number of new links, a sudden growth spurt occurs: The size of the largest network within the system is enhanced dramatically. “With respect to the size of the system, this jump is more dramatic in small systems than in large ones”, says Nagler. However even in systems that consist of a huge number of elements – comparable for example to the number of neurons in the brain – the size of the largest network can double. “At first, many networks of moderate size develop in this way”, says Timme. Thus, a dominant spanning emerges only at a late stage in the growth process.

In a next step, the researchers now want to identify which forms of competition in natural systems from biology and physics imply this rapid growth and study the consequences of these growth spurts.

Explore further: Adding uncertainty to improve mathematical models

More information: Nagler, Anna, Marc Timme, "Impact of Single Links in Competitive Percolation." Nature Physics online, 16. January 2011

Related Stories

Understanding the social butterfly effect

Dec 02, 2010

(PhysOrg.com) -- A team of scientists from the University of Southampton, in collaboration with Royal Holloway, University of London and the Institute of Zoology at London Zoo, have been researching the social butterfly effect ...

Quantum Communication in Random Networks

May 26, 2010

Internet, networks of connections between Hollywood actors, etc, are examples of complex networks, whose properties have been intensively studied in recent times. The small-world property (that everyone has ...

Physics rules network dynamics

Dec 11, 2009

(PhysOrg.com) -- When it comes to the workings of the Web, the brain, or a social network, physics finds universal truths.

Location determines social network influence, study finds

Aug 29, 2010

A team of researchers led by Dr. Hernan Makse, professor of physics at The City College of New York (CCNY), has shed new light on the way that information and infectious diseases proliferate across complex networks. Writing ...

Recommended for you

Putting children first, when media sets its own rules

4 hours ago

In an age when a significant number of parents won't let their child walk down the street to post a letter because of "stranger danger", it's ironic that many pay little attention while media organisations ...

Self-made billionaires more likely to give than inheritors

6 hours ago

A study by economists at the University of Southampton suggests that billionaires who have built their own fortunes are more likely to pledge to donate a large portion of their wealth to charities, than those who are heirs ...

User comments : 2

Adjust slider to filter visible comments by rank

Display comments: newest first

electrodynamic
not rated yet Jan 18, 2011
Networks change, and evolve all the time. I don't think it's so cut, and dry. For one thing there will always be networks within networks, the "in" crowd for example. Cool people like me! All things everywhere, are already a part of a network, and have been for a very long time. It's called the universe.
kevp
not rated yet Jan 19, 2011
This article seems to miss out a lot of the details. Is a short connection selected favourably over a long connection? For each potential connection, is one node selected and paired with a neighbouring node or can it be connected to a randomly selected node far away? In a natural process, cannot pairs of connections be constructed in parallel, when we are not constrained by the limitations of a serial computer algorithm? Would it not be natural for each node to seek outs its nearest neighbours to connect with, thus minimising use of resources? How is a node aware of the "connectedness" of a potential node when it has not yet made the connection and constructed a communication path? Is the final network the most efficient in terms of resources used to construct the network, and is the most efficient in terms of speed of communications across the network?