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

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) 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 network 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."