Popular Network Theory Debunked

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 yeast cells, 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) and Kim Kardashian (60 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 test that trendy theory. 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 network 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 the 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.”

Power law

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

But Scale-free networks are special because the patterns of connections coming into and out of nodes follows a precise mathematical form called a power law distribution.

“If human height followed a power law, you might expect one person to be as tall as the Empire State Building, 10,000 people to be as tall as a giraffe, and more than 150 million to be only about 7-inches-tall,” Clauset said. 

Beginning in the late 1990s, a handful of researchers made a bold claim that all real-world networks follow a universal structure represented by such giraffe- and inch-sized disparities.

There was just one problem: “The original claims were mostly based on analyzing a handful of networks with very rough tools,” Clauset said. “The idea was provocative, but also, in retrospect, quite speculative.”

To take scale-free networks out of the realm of speculation, he 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. By applying a series of statistical tests of increasing severity, the researchers calculated that only about 4 percent of the networks they studied met the strictest criteria for being scale free, meaning the number of connections that each node carried followed a power-law distribution. These special networks included some types of protein networks in cells and certain kinds of technological networks. 

A multitude of shapes

But not all researchers use those exact requirements to decide what makes a scale-free network, Broido said. To account for these alternative definitions, she and Clauset adapted their tests to account for each of the variations.

“Wherever you’re coming from, one of our definitions should be close to what you’re thinking,” Broido said.

Despite the added flexibility, most networks still failed to show evidence even for weakly scale-free structure. Roughly half of all biological networks and all social networks, for example, didn’t look like anything close to a scale-free network, no matter how flexible the definitions were made.

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.”

This article has been republished from materials provided by University of Colorado Boulder. Note: material may have been edited for length and content. For further information, please contact the cited source.

Reference: Broido, A. D., & Clauset, A. (2019). Scale-free networks are rare. Nature Communications, 10(1), 1017. https://doi.org/10.1038/s41467-019-08746-5