A day or two ago Anna Broido and Aaron Clauset arxived a paper about how rare scale-free networks really are. If network science was invented today, I think such a paper would not raise many eyebrows. Now it already got much attention, and I think it looks like a methodologically solid and important contribution. To someone new to network science, this attention might seem strange, but it is a consequence of the history of our field. This post is an account of my own relationship with power-laws, and maybe can give some context to why the Broido and Clauset paper will reboot old discussions among me and my colleagues.
I started as a Ph.D. student 1999 and the non-network interest in things scale-free was probably already on the decline. My thesis topic was phase transitions in disordered super-conductors. The name of that game was not really hunting power-laws, but rather phase transitions by a computational method called finite-sized scaling. This method itself is not really proving the existence of phase transitions, but finds points where the behavior of your simulated superconductor is consistent with a phase transition. Technically, you measure something in your simulations that form curves of a parameter representing e.g. temperature. At the right choice of another parameter (a critical exponent) curves for different systems sizes cross each other at a unique parameter value (the phase transition point). Finding the critical exponents was something we did by hand by trying different numbers, not by maximizing a goodness-of-fit function or similar. Although I heard about statistical methods, and occasionally used it—in this paper we used the jackknife method to find the error bars of the critical exponents—the main statistical method was to eyeball a curve. There was a saying that statistical physicists neither know statistics nor physics—to be self-critical, that almost became a self-fulfilling prophecy.
Some years into my Ph.D. program, I became interested in networks through Barabási et al.’s work on scale-free networks (i.e. networks with a power-law degree distribution). The way we would check if a network is scale-free was—no surprise—by eyeballing histograms on log-log plots. The plots could bend in both sides—for small degrees bends didn’t matter “because the tail is the characteristic of a power law”, for very large degrees bends didn’t matter “because of finite-size effects”. According to this thinking, if the networks were only larger, the lines would be straighter. If a line was straight over a couple of decades (decimal orders of magnitudes), then we would be safe to call the network scale free. The straightness was once again judged visually—we would even squint at the computer screen from an angle to get a better idea if a curve was straight or not.
This was at a time when the hype around self-organized criticality (SOC) was still fresh in memory. My abstract-length summary of SOC would be as follows: 1. Many systems in nature and society have power-law distributions of some important quantities. 2. Phase-transitions in physics have power-law distributions with parameter values (the critical exponents) that are independent of the details of your experiment or your model. The fact that you see rather few exponents (still probably many hundreds have been reported in the literature), justifies the epithet “universal exponents”. 3. Maybe universal exponents can explain the many power-laws in nature and society. 4. Phase transitions happen at only one point (in a one-dimensional parameter space). Thus the system need a way to tune itself to the transition, and SOC proposes models where this arguably happens, and extends this to an explanation of reality. The spirit of the day is captured in the late Per Bak’s book “How nature works” and these fascinating radio interviews with him.
Already at the time, people were aware of the problems with the claim that SOC is a universal phenomenon. The original paper proposed a model of avalanches in sand piles—a phenomenon that was hard to confirm in real experiments with sand. Rice on the other hand seemed to work, but not all rice was equal (according to rumors, take this with a grain of salt)—some kinds of rice were more power-lawy than others. So where is the universality? To me, SOC is a beautiful thought, and “How a few phenomena in nature perhaps works”. (When I am writing this, I am not sure there is any phenomenon of which there is a broad consensus that SOC is the most accurate explanation.) It is definitively worth teaching in a class on complex systems, but as one of many ideas floating around.
When scale-free networks became a hot topic, it probably borrowed some heat from self-organized criticality. At least in my immediate surrounding. However, I think scale-free networks is a much more important concept than SOC ever was. Even though, in the different senses Broido and Clauset discuss, they are rare.
I think the problem with the sketchy, blunt methods that we used back in the day are not so much their sketchiness and bluntness as that we claimed it to imply statistically exact relationships. If we could rewrite history and redefine power-laws as “something that follows a straight line in a log-log histogram if you squint from the side of a computer screen”, then they would, for sure, be abundant, and most implications about the function of a networked system would still be true.
If network science would be developed from scratch today—with the math and data sets we have now, but without the legacy of the 1990’s power-law hype—then the fact that networks with skewed, fat-tailed degree distributions are common would still be a center piece of the theory. Probably power-law network models would still be C. elegans for network theorists. However, nobody would believe that real-world networks typically have power-law degree distributions.