Do all networks obey the scale-free law? Maybe not

March 4, 2019 by Daniel Strain, University of Colorado at Boulder
Credit: CC0 Public Domain

As Benjamin Franklin once joked, death and taxes are universal. Scale-free networks may not be, at least according to a new study from CU Boulder.

The research challenges a popular, two-decade-old theory that networks of all kinds, from Facebook and Twitter to the interactions of genes in , follow a common architecture that mathematicians call "scale-free."

Such networks fit into a larger category of networks that are dominated by a few hubs with many more connections than the vast majority of nodes—think Twitter where for every Justin Bieber (105 million followers) out there, you can find thousands of users with just a handful of fans.

In research published this week in the journal Nature Communications, CU Boulder's Anna Broido and Aaron Clauset set out to put that theory to the test. They used computational tools to analyze a huge dataset of more than 900 networks, with examples from the realms of biology, transportation, technology and more.

Their results suggest that death and taxes may not have much competition, at least in networks. Based on Broido and Clauset's analysis, close to 50 percent of real networks didn't meet even the most liberal definition of what makes a network scale-free.

Those findings matter, Broido said, because the shape of a networks determines a lot about its properties, including how susceptible it is to targeted attacks or disease outbreaks.

"It's important to be careful and precise in defining things like what it means to be a scale-free network," said Broido, a graduate student in the Department of Applied Mathematics.

Clauset, an associate professor in the Department of Computer Science and BioFrontiers Institute, agrees.

"The idea of scale-free networks has been a unifying but controversial theme in network theory for nearly 20 years," he said. "Resolving the controversy has been difficult because we lacked good tools and broad data. What we've found now is that there is little evidence for classically scale-free networks except in a few specific places. Most networks don't look scale-free at all."

Deciding whether or not a is "scale-free," however, can be tricky. Many types of networks look similar from a distance.

In scale-free networks, however, the patterns of connections coming into and out of nodes follows a precise mathematical form called a power law distribution.

To take such networks out of the realm of speculation, Clauset and Broido turned to the Index of Complex Networks (ICON). This archive, which was assembled by Clauset's research group at CU Boulder, lists data on thousands of networks from every scientific domain. They include the social links between Star Wars characters, interactions among yeast proteins, friendships on Facebook and Twitter, airplane travel and more.

Their findings were stark. The researchers calculated that only about 4 percent of the networks they studied met the strictest criteria for being scale free. These special networks included some types of protein networks in cells and certain kinds of technological networks.

Far from being a let-down, Clauset sees these null findings in a positive light: If scale-free isn't the norm, then scientists are free to explore new and more accurate structures for the networks people encounter every day.

"The diversity of real networks presents a mystery," he said. "What are the common shapes of the networks? How do different kinds of networks assemble and maintain their structure over time? I'm excited that our findings open up room to explore new ideas."

Explore further: Scientists describe technique for extracting hierarchical structure of networks

More information: Anna D. Broido et al, Scale-free networks are rare, Nature Communications (2019). DOI: 10.1038/s41467-019-08746-5

Related Stories

Scale-free networking gives humans a competitive edge

June 17, 2015

Humans arrange themselves into scale-free networks to give themselves a competitive edge according to research published this month in Nature's Scientific Reports. The work conducted by University of Sydney researchers expands ...

Unraveling biological networks

March 5, 2012

A new approach to disentangling the complexities of biological networks, such as the way in which proteins interact in our body's cells has been developed by researchers in China. The team's algorithm could allow biologists ...

Recommended for you

Study reveals properties of a Type Ib supernova in NGC 4080

March 25, 2019

A recent study conducted by astronomers has revealed important observational properties of a Type Ib supernova designated MASTER OT J120451.50+265946.6, which exploded in the galaxy NGC 4080. The research, presented in a ...

Catalyst advance removes pollutants at low temperatures

March 25, 2019

Researchers at Washington State University, University of New Mexico, Eindhoven University of Technology, and Pacific Northwest National Laboratory have developed a catalyst that can both withstand high temperatures and convert ...

0 comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.