Uncovering complex network structures in nature

The global spread of Ebola is due to the complex interactions between individuals, societies, and transportation and trade networks. Understanding and building appropriate statistical and mathematical models of these interactions is vital to responding to the challenges of living in a networked world. There are, of course, many other examples of complex networks—from national power grids and airline networks to social networks, neuronal networks and protein-protein interactions.

In a new study published in the Beijing-headquartered journal National Science Review, scientists based in China and Australia state that in complex systems, to understand the behavior of the system it is becoming necessary first to properly chart the structure of the network.

In an article titled "Random complex networks," Michael Small, based at The University of Western Australia, Lvlin Hou, based at China's National University of Defense Technology, and Linjun Zhang, a PhD candidate at University of Pennsylvania, note that in physics and mathematics, one typically characterizes the structure of complex networks by looking at the connections between individual components, and creating a distribution - the node degree distribution - characterizing the expected number of connections for a random component.

In some systems, they add, individual components have a similar number of neighbors - most traffic intersections are junctions of two, three or four roads. In other systems the numbers vary wildly - some websites have only a few links pointing at them; others have many tens of thousands. Most proteins interact with only one or two others; some form thousands of interactions. Most people have a few friends (or colleagues, or contacts); some have many more. Systems exhibiting this wildly varying degree of connectivity are an extreme challenge for mathematicians and physicists to describe: what does one mean by choosing one of these systems at random? How should those connections be configured?

Co-authors of the paper "Random Complex networks" seek to answer these questions.

Several models have already been proposed to generate networks of interacting individuals with wildly varying connectivity. The most famous of these is known as preferential attachment and follows the social maxim of "the rich get richer". As time progresses, the individuals in the network with the most connections are the ones most likely to acquire new connections. Just as in the real world, wealth attracts still more wealth and societies develop with most people having little and a small minority having most of the resources.

While this is intuitive, it turns out that there is a much richer and more interesting structure of complex networks that is not explored with this approach. Co-authors of the National Science Review paper provide a solution by proposing a simple method to fully explore the mathematical space of all "interesting" networks with a particular node degree distribution. They achieve this aim by randomly exchanging edges on the network.

This simple process (justified with some less simple mathematics) allows scientists to explore the behavior of typical networks. This process can be applied to experimentally obtained networks (from airline transportation networks, to gene interaction, Internet, social connections and so on) to probe which features of the individual networks are the really important defining structures.

While the preferential attachment model is a common approach to construct such networks, the co-authors of the new study show for the first time that features of this model are not typical. In particular, preferential attachment networks are "robust-yet-fragile". That is, by random deleting parts of the network, the overall network structure is largely unaffected (the robustness part). However, deliberately attacking particular nodes in the network can quickly lead to complete collapse (fragility).

It was thought that this is a common property of all networks with such wildly divergent degrees of connection. However, there is mounting evidence that many systems do not have this property. The new study shows that most typical networks are robust to both random and deliberate attacks. This result provides a better explanation of earlier observations of many natural and technological complex systems.