Scant Evidence of Power Laws Found in Real-World Networks
Meredith Miotke for Quanta Magazine
Introduction
A paper posted online last month has reignited a debate about one of the oldest, most startling claims in the modern era of network science: the proposition that most complex networks in the real world — from the World Wide Web to interacting proteins in a cell — are “scale-free.” Roughly speaking, that means that a few of their nodes should have many more connections than others, following a mathematical formula called a power law, so that there’s no one scale that characterizes the network.
Purely random networks do not obey power laws, so when the early proponents of the scale-free paradigm started seeing power laws in real-world networks in the late 1990s, they viewed them as evidence of a universal organizing principle underlying the formation of these diverse networks. The architecture of scale-freeness, researchers argued, could provide insight into fundamental questions such as how likely a virus is to cause an epidemic, or how easily hackers can disable a network.
Over the past two decades, an avalanche of papers has asserted the scale-freeness of hundreds of real-world networks. In 2002, Albert-László Barabási — a physicist-turned-network scientist who pioneered the scale-free networks paradigm — wrote a book for a general audience, Linked, in which he asserted that power laws are ubiquitous in complex networks.
“Amazingly simple and far-reaching natural laws govern the structure and evolution of all the complex networks that surround us,” wrote Barabási (who is now at Northeastern University in Boston) in Linked. He later added: “Uncovering and explaining these laws has been a fascinating roller coaster ride during which we have learned more about our complex, interconnected world than was known in the last hundred years.”
But over the years, other researchers have questioned both the pervasiveness of scale-freeness and the extent to which the paradigm illuminates the structure of specific networks. Now, the new paper reports that few real-world networks show convincing evidence of scale-freeness.
In a statistical analysis of nearly 1,000 networks drawn from biology, the social sciences, technology and other domains, researchers found that only about 4 percent of the networks (such as certain metabolic networks in cells) passed the paper’s strongest tests. And for 67 percent of the networks, including Facebook friendship networks, food webs and water distribution networks, the statistical tests rejected a power law as a plausible description of the network’s structure.
“These results undermine the universality of scale-free networks and reveal that real-world networks exhibit a rich structural diversity that will likely require new ideas and mechanisms to explain,” wrote the study’s authors, Anna Broido and Aaron Clauset of the University of Colorado, Boulder.
Network scientists agree, by and large, that the paper’s analysis is statistically sound. But when it comes to interpreting its findings, the paper seems to be functioning like a Rorschach test, in which both proponents and critics of the scale-free paradigm see what they already believed to be true. Much of the discussion has played out in vigorous Twitter debates.
Supporters of the scale-free viewpoint, many of whom came to network science by way of physics, argue that scale-freeness is intended as an idealized model, not something that precisely captures the behavior of real-world networks. Many of the most important properties of scale-free networks, they say, also hold for a broader class called “heavy-tailed networks” to which many real-world networks may belong (these are networks that have significantly more highly connected hubs than a random network has, but don’t necessarily obey a strict power law).
Critics object that terms like “scale-free” and “heavy-tailed” are bandied about in the network science literature in such vague and inconsistent ways as to make the subject’s central claims unfalsifiable.
The new paper “was an attempt to take a data-driven approach to sort of clean up this question,” Clauset said.
Network science is a young discipline — most of its papers date to the last 20 years — and the contentiousness surrounding the paper and the very vocabulary of scale-freeness stems from the field’s immaturity, said Mason Porter, a mathematician and network scientist at the University of California, Los Angeles. Network science, he said, is “still kind of in the Wild West.”
A Universal Law?
Many networks, from perfectly ordered lattices to purely random networks, do have a characteristic scale. In a two-dimensional square lattice, for instance, every node is connected to exactly four other nodes (so mathematicians say the node’s “degree” is four). In a random network, in which each pair of nodes has some constant probability of being connected to each other, different nodes can have different degrees, but these degrees nevertheless cluster fairly close to the average. The distribution of degrees is shaped roughly like a bell curve, and nodes with a disproportionately large number of links essentially never occur, just as the distribution of people’s heights is clustered in the 5- to 6-foot range and no one is a million (or even 10) feet tall.
But when a team led by Barabási examined a sample of the World Wide Web in 1998, it saw something very different: some web pages, such as the Google and Yahoo home pages, were linked to vastly more often than others. When the researchers plotted a histogram of the nodes’ degrees, it appeared to follow the shape of a power law, meaning that the probability that a given node had degree k was proportional to 1/k raised to a power. (In the case of incoming links in the World Wide Web, this power was approximately 2, the team reported.)
Lucy Reading-Ikkanda/Quanta Magazine
In a power law distribution, there is no characteristic scale (thus the name “scale-free”). A power law has no peak — it simply decreases for higher degrees, but relatively slowly, and if you zoom in on different sections of its graph, they look self-similar. As a result, while most nodes still have low degree, hubs with an enormous number of links do appear in small quantities, at every scale.
The scale-free paradigm in networks emerged at a historical moment when power laws had taken on an outsize role in statistical physics. In the 1960s and 1970s they had played a key part in universal laws that underlie phase transitions in a wide range of physical systems, a finding that earned Kenneth Wilson the 1982 Nobel Prize in physics. Soon after, power laws formed the core of two other paradigms that swept across the statistical physics world: fractals, and a theory about organization in nature called self-organized criticality.
By the time Barabási was turning his attention to networks in the mid-1990s, statistical physicists were primed to see power laws everywhere, said Steven Strogatz, a mathematician at Cornell University (and a member of Quanta’s advisory board). In physics, he said, there’s a “power law religion.”
Barabási’s team published its findings in Nature in 1999; a month later, Barabási and his then-graduate student Réka Albert (now a network scientist at Pennsylvania State University) wrote in Science, in a paper that has since been cited more than 30,000 times, that power laws describe the structure not just of the World Wide Web but also of many other networks, including the collaboration network of movie actors, the electrical power grid of the Western United States, and the citation network of scientific papers. Most complex networks, Barabási asserted a few years later in Linked, obey a power law, whose exponent is usually between 2 and 3.
A simple mechanism called “preferential attachment,” Albert and Barabási argued, explains why these power laws appear: When a new node joins a network, it is more likely to connect to a conspicuous, high-degree node than an obscure, low-degree node. In other words, the rich get richer and the hubs get hubbier.
Scale-free networks, Barabási’s team wrote in the July 27, 2000, issue of Nature, have some key properties that distinguish them from other networks: They are simultaneously robust against failure of most of the nodes and vulnerable to targeted attacks against the hubs. The cover of Nature trumpeted this last property as the “Achilles’ heel of the internet” (a characterization that has since been roundly disputed by internet experts).
Barabási’s work electrified many mathematicians, physicists and other scientists, and was instrumental in launching the modern field of network science. It unleashed a torrent of papers asserting that one real-world network after another was scale-free — a sort of preferential attachment in which Barabási’s early papers became the hubs. “There was a bandwagon effect in which people were doing stuff rather indiscriminately,” Porter said. The excitement spilled over into the popular press, with talk of universal laws of nature and cover stories in Science, New Scientist and other magazines.
From the beginning, though, the scale-free paradigm also attracted pushback. Critics pointed out that preferential attachment is far from the only mechanism that can give rise to power laws, and that networks with the same power law can have very different topologies. Some network scientists and domain experts cast doubt on the scale-freeness of specific networks such as power grids, metabolic networks and the physical internet.
Others objected to a lack of statistical rigor. When a power law is graphed on a “log-log plot” (in which the x– and y-axes have logarithmic scales) it becomes a straight line. So to decide whether a network was scale-free, many early researchers simply eyeballed a log-log plot of the network’s degrees. “We would even squint at the computer screen from an angle to get a better idea if a curve was straight or not,” recalled the network scientist Petter Holme of Tokyo Institute of Technology in a blog post.
“There must be a thousand papers,” Clauset said, “in which people plot the degree distribution, put a line through it and say it’s scale-free without really doing the careful statistical work.”
In response to these criticisms, over the years some of the physicists studying scale-freeness shifted their focus to the broader class of heavy-tailed networks. Even so, a steady stream of papers continued to assert scale-freeness for a growing array of networks.
And the discussion was muddied by a lack of consistency, from one paper to another, about what “scale-free” actually meant. Was a scale-free network one that obeys a power law with an exponent between 2 and 3, or one in which this power law arises out of preferential attachment? Or was it just a network that obeys some power law, or follows a power law on some scales, or something even more impressionistic?
“The lack of precision of language is a constant frustration,” Porter said.
Clauset, who is active in outreach efforts, has found that many of the students he interacts with still think that the ubiquity of power laws is settled science. “I was struck by how much confusion there was in the upcoming generation of scientists about scale-free networks,” he said.
The evidence against scale-freeness was scattered across the literature, with most papers examining just a few networks at a time. Clauset was well-positioned to do something much more ambitious: His research group has spent the past few years curating a giant online compendium, the Colorado Index of Complex Networks (ICON), comprising more than 4,000 networks drawn from economics, biology, transportation and other domains.
“We wanted to treat the hypothesis as falsifiable, and then assess the evidence across all domains,” he said.
Sweeping Up the Dirt and Dust
To test the scale-free paradigm, Clauset and Broido, his graduate student, subjected nearly a thousand of the ICON networks to a series of increasingly strict statistical tests, designed to measure which (if any) of the definitions of scale-freeness could plausibly explain the network’s degree distribution. They also compared the power law to several other candidates, including an exponential distribution (which has a relatively thin tail) and a “log-normal” distribution (which has a heavier tail than an exponential distribution, but a lighter tail than a power law).
Broido and Clauset found that for about two-thirds of the networks, no power law fit well enough to plausibly explain the degree distribution. (That doesn’t mean the remaining one-third necessarily obey a power law — just that a power law was not ruled out.) And each of the other candidate distributions outperformed the power law on many networks, with the log normal beating the power law on 45 percent of the networks and essentially tying with it on another 43 percent.
Only about 4 percent of the networks satisfied Broido and Clauset’s strongest test, which requires, roughly speaking, that the power law should survive their goodness-of-fit test, have an exponent between 2 and 3, and beat the other four distributions.
For Barabási, these findings do not undermine the idea that scale-freeness underlies many or most complex networks. After all, he said, in real-world networks, a mechanism like preferential attachment won’t be the only thing going on — other processes will often nudge the network away from pure scale-freeness, making the network fail Broido and Clauset’s tests. Network scientists have already figured out how to correct for these other processes in dozens of networks, Barabási said.
“In the real world, there is dirt and dust, and this dirt and dust will be on your data,” said Alessandro Vespignani of Northeastern, another physicist-turned-network scientist. “You will never see the perfect power law.”
As an analogy, Barabási noted, a rock and a feather fall at very different speeds even though the law of gravitation says they should fall at the same speed. If you didn’t know about the effect of air resistance, he said, “you would conclude that gravitation is wrong.”
Clauset doesn’t find this analogy convincing. “I think it’s pretty common for physicists who are trained in statistical mechanics … to use these kinds of analogies for why their model shouldn’t be held to a very high standard.”
If you were to observe 1,000 falling objects instead of just a rock and a feather, Clauset said, a clear picture would emerge of how both gravity and air resistance work. But his and Broido’s analysis of nearly 1,000 networks has yielded no similar clarity. “It is reasonable to believe a fundamental phenomenon would require less customized detective work” than Barabási is calling for, Clauset wrote on Twitter.
“The tacit and common assumption that all networks are scale-free and it’s up to us to figure out how to see them that way — that sounds like a nonfalsifiable hypothesis,” he said.
If some of the networks rejected by the tests do involve a scale-free mechanism overlaid by other forces, then those forces must be quite strong, Clauset and Strogatz said. “Contrary to what we see in the case of gravity … where the dominant effects really are dominant and the smaller effects really are small perturbations, it looks like what’s going on with networks is that there isn’t a single dominant effect,” Strogatz said.
For Vespignani, the debate illustrates a gulf between the mindsets of physicists and statisticians, both of whom have valuable perspectives. Physicists are trying to be “the artists of approximation,” he said. “What we want to find is some organizing principle.”
The scale-free paradigm, Vespignani said, provides valuable intuition for how the broader class of heavy-tailed networks should behave. Many traits of scale-free networks, including their combination of robustness and vulnerability, are shared by heavy-tailed networks, he said, and so the important question is not whether a network is precisely scale-free but whether it has a heavy tail. “I thought the community was agreeing on that,” he said.
But Duncan Watts, a network scientist at Microsoft Research in New York City, objected on Twitter that this point of view “is really shifting the goal posts.” As with “scale-freeness,” he said, the term “heavy-tailed” is used in several different ways in the literature, and the two terms are sometimes conflated, making it hard to assess the various claims and evidence. The version of “heavy-tailed” that is close enough to “scale-free” for many properties to transfer over is not an especially broad class of networks, he said.
Scale-freeness “actually did mean something very clear once, and almost certainly that definition does not apply to very many things,” Watts said. But instead of network scientists going back and retracting the early claims, he said, “the claim just sort of slowly morphs to conform to all the evidence, while still maintaining its brand label surprise factor. That’s bad for science.”
Porter likes to joke that if people want to discuss something contentious, they should set aside U.S. politics and talk about power laws. But, he said, there’s a good reason these discussions are so fraught. “We have these arguments because the problems are hard and interesting.”
Clauset sees his work with Broido not as an attack but as a call to action to network scientists, to examine a more diverse set of possible mechanisms and degree distributions than they have been doing. “Perhaps we should consider new ideas, as opposed to trying to force old ideas to fit,” he said.
Vespignani agrees that there is work to be done. “If you ask me, ‘Do you all agree what is the truth of the field?’ Well, there is no truth yet,” he said. “There is no general theory of networks.”
This article was reprinted on TheAtlantic.com.
