Saturday, February 17, 2018

Scale: "Scant Evidence of Power Laws in Real-World Networks"

Wait, what?

From Quanta Magazine:
A new study challenges one of the most celebrated and controversial ideas in network science. 
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.....MUCH MORE