Scale-free networks are rare
In January of this year, Anna Broido and Aaron Clauset published an article titled “Scale-free networks are rare” [1], in which they analyzed nearly 1000 different types of networks and found that only 4% strongly follow the power law model, generally considered to be the determining factor for a scale-free network. For some background, Albert László Barabási, a now widely recognized network scientist, published a study in 1999 that found that webpage links on the World Wide Web followed a power law, and from there, the idea of networks following power laws took off, with Barabási’s original paper now having over 30,000 citations. (Interestingly, the network of network science paper citations could potentially be modeled by a power law, with Barabási’s original paper as one of the central hubs.) A power law is one that describes the probability of a node having k degrees as proportional to 1/k^n where generally, 2<n<3. (Remember that the degree of a node is its number of connections to other nodes.) One mechanism proposed to explain the power law is “preferential attachment”, where more connected nodes are more likely to connect to other nodes than less connected nodes, allowing for some nodes to have extremely high degree while the majority have low degree. (The power law to model networks is a fundamental concept in current network theory that we will cover more in Unit 5, specifically, Ch 18.)
However, the newly published paper appears to refute the past couple decades of supposed evidence towards networks following the power law. As discussed by Erica Klarreich in Quanta Magazine [2], these new findings bring up many questions, disputes, and challenged perceptions. As Steven Strogatz (Cornell math professor and Quanta advisory board member) discusses, throughout the late 20th century, power laws took on a large role in statistical physics as a key part of many universal laws describing various physical systems. When Barabási and other physicists-turned-network-scientists arrived on the scene, they brought the wave of power law enthusiasm with them. Unsurprisingly, then, the statistical vigor of many works demonstrating that certain networks can be described with the power law has been brought to question. Yet, at the same time, there is some lack of clarity regarding what qualifies as a “scale-free” network. How closely must a network follow a power law to be considered scale-free? Does a network simply have to exhibit preferential attachment, and due to noise and other mechanisms not really follow a power law, to be considered scale-free?
That last question spurs perhaps the biggest debate on the topic. As a relatively new field, network science is primarily dominated by statisticians and physicists, the latter group undoubtedly the staunchest defenders of the power law. Many physicists and other supporters of the persistence of the power law in real-world networks argue that preferential attachment is only one of the major mechanisms that exist in networks, and the other mechanisms as well as noise contribute to cause the power law to simply be a very general approximation. Considering physicists’ streak of approximation and determined searching for universal laws, this is hardly surprising. Altogether, it brings up a rather interesting question of what the network of network scientists looks like, whether there indeed exist distinct camps of the “physicists” vs. the “statisticians”, and if ideas might potentially resound within one camp.
Sources:
[1] “Scale free networks are rare” by Anna Broido & Aaron Clauset (Jan. 2018) https://arxiv.org/abs/1801.03400
[2] “Scant evidence of power laws found in real-world networks” by Erica Klarreich (Feb. 2018) https://www.quantamagazine.org/scant-evidence-of-power-laws-found-in-real-world-networks-20180215/