Close reading Wikipedia from Pareto to Network Science, part 4

This is part 4: How network science bridges with statistics

In this part we focus on the relations between the concepts of network science and of statistics, as stated in the articles of my corpus (see part 1). These concepts are essentially:

The power law
Scale-free networks
Preferential attachment

As a post on my research blog, it is honest on what is actually done but at the cost of not-so-relevant material. I also follow the mantra of “release early, release often”, so please forgive the lack of finishing touches.

Findings

Nothing decisive, essentially an account of the conceptual situation.

Power law is, as expected, the articulation between network science and statistics. It belongs to both fields insofar as it is a statistical distribution and a defining characteristic of complex networks.

Beyond that concept, scale invariance is the active principle in both the power law and complex networks. As we will see in the next section, it is where network science bridges with phase transitions and universality.

How Network Science bridges with Statistics

Power Law & Scale-free Networks

In the article on power law we found the most direct link between scale-free networks and the power law, though implicit. It is still a good starting point to understand the situation.

“[…] all power laws with a particular scaling exponent are equivalent up to constant factors, since each is simply a scaled version of the others.”
Power law, in the “Scale invariance” section

The fact that scaling a function’s input only causes a scaling of the function, as tautological as it sounds, is actually remarkable. It is precisely the definition of scale invariance. It turns out that this characterization is strictly equivalent to the formula of a power law. Hence the following conclusion: scale invariance is the power law. Though scale invariance and scale-free networks are not exactly the same thing, the link is still remarkably direct considering that scale-free networks are named after scale invariance. Note however that in Wikipedia we do not find a direct explicit link between scale invariance and scale-free networks.

Scale invariance is important because it is often invoked to frame and interpret the power law, as a consequence of a more fundamental phenomenon:

“The equivalence of power laws with a particular scaling exponent can have a deeper origin in the dynamical processes that generate the power-law relation.”
Power law

Scale invariance is never explicitly linked to scale-free networks. Each page is mentioned in the “see also” section of the other, but no sentence states the relation.

Scale-free networks (SFN) are defined by a distribution of node degrees following a power law. We have seen that there is a controversy about how closely it must follow it, which extends to a general debate about which empirical networks are actually scale-free (or log-normal…). Regardless, Wikipedia is explicit on the relation between SFN and the power law.

“A scale-free network is a network whose degree distribution follows a power law, at least asymptotically.”
Scale-free network

“A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. […] Another general characteristic of scale-free networks is the clustering coefficient distribution, which decreases as the node degree increases. This distribution also follows a power law.”
Social network

Interesting variation, in the following citation we note a reversal of the relation: preferential attachment is not the defining characteristic, but a consequence of SFN.

“Chris Anderson argues that while quantities such as human height or IQ follow a normal distribution, in scale-free networks with preferential attachments, power law distributions are created”
Long tail

Relations between the concepts of power law and scale free networks

The power law is also specifically tied to scale-free networks, and not to small-world networks. As we have seen, these two types of networks are sometimes interchangeable, and subsumed into the more general category of “complex networks”. But concerning the power law, they are not equivalent, since small-world networks are not expected to follow a power law, as in the following excerpt:

“In a small world network with a degree distribution following a power-law, deletion of a random node rarely causes a dramatic increase in mean-shortest path length (or a dramatic decrease in the clustering coefficient).”
Small-world network

Preferential attachment & power law

The power law and scale-free networks also often relate to a third concept: preferential attachment. In network science this concept describes a phenomenon where the most connected nodes tend to attract new connections, but it also has a non-network interpretation. Like the concept of power law, it has a number of variations such as “rich get richer” or “Chinese restaurant process” (see previous parts).

“Similarly, preferential attachment (intuitively, “the rich get richer” or “success breeds success”) that results in the Yule–Simon distribution has been shown to fit word frequency versus rank in language and population versus city rank better than Zipf’s law.”
Zipf’s law

In this excerpt, preferential attachment fits a empirical distributions. Similarly, the article on “Preferential attachment” is not primarily about networks but probabilities.

“A preferential attachment process is a stochastic urn process, meaning a process in which discrete units of wealth, usually called “balls”, are added in a random or partly random fashion to a set of objects or containers, usually called “urns”. A preferential attachment process is an urn process in which additional balls are added continuously to the system and are distributed among the urns as an increasing function of the number of balls the urns already have.”
Preferential attachment

But of course the concept still relates to the power law, as in the citation below, stating that preferential attachment generates a power law. Note the importance of the tail in this correspondence.

“the preferential attachment process generates a “long-tailed” distribution following a Pareto distribution or power law in its tail. This is the primary reason for the historical interest in preferential attachment: the species distribution and many other phenomena are observed empirically to follow power laws and the preferential attachment process is a leading candidate mechanism to explain this behavior.”
Preferential attachment

In another article we find a probabilistic version of the same statement. It explicitly mentions the usefulness of preferential attachment as a “model”.

“In statistics, the phrase “the rich get richer” is often used as an informal description of the behavior of Chinese restaurant processes and other preferential attachment processes, where the probability of the next outcome in a series taking on a particular value is proportional to the number of outcomes already having that particular value. This is useful for modeling many real-world processes that are akin to “popularity contests”, where the popularity of a particular choice causes new participants to adopt the same choice (which can lead to the outsized influence of the first few participants).”
The rich get richer and the poor get poorer

Preferential attachment & scale-free networks

A.-L. Barabási and R. Albert have famously championed preferential attachment as a model for generating (and explaining) scale-free networks. This model is named after them and has its own Wikipedia page.

“The Barabási–Albert model is one of several proposed models that generate scale-free networks. It incorporates two important general concepts: growth and preferential attachment. Both growth and preferential attachment exist widely in real networks.”
Barabási–Albert model

This model is key to network science, and we find other mentions of preferential attachment as a model, with or without the names of Barabási and Albert.

“Many networks have been reported to be scale-free […]. Preferential attachment and the fitness model have been proposed as mechanisms to explain conjectured power law degree distributions in real networks.”
Scale-free network

As we have seen previously, assortativity can have the meaning of preferential attachment. Presumably as such, it is mentioned as a defining feature of complex networks, though the connection is not detailed.

“Complex networks: Most larger social networks display features of social complexity […]. Such complex network features include a heavy tail in the degree distribution, a high clustering coefficient, assortativity or disassortativity among vertices, community structure (see stochastic block model), and hierarchical structure.”
Social network

Relations between the concepts of preferential attachment and scale-free networks

Overview of the bridge

Relations between the key concepts bridging statistics and the power law

OpenEdition suggests that you cite this post as follows:
Mathieu Jacomy (April 22, 2019). Close reading Wikipedia from Pareto to Network Science, part 4. Reticular. Retrieved January 20, 2025 from https://reticular.hypotheses.org/826