This is part 2: Concepts of complex network and preferential attachment
As we mentioned in the part 1 of this work, just defining the concepts we need to understand the field requires an effort. Before we move on to analysis, we will clarify two families of concepts, one centered on the complex network, and the other one on preferential attachment.
As this is a post on my research blog, it tends to expose more than a typical paper would. I follow the open source software mantra “release early, release often”.
Scale-free networks and small-world networks have a different origin and characterization, but it turns out that they are quite the same thing and their differences do not seem so important now that we have studied them further. The more general term of complex network seems appropriate to refer to this family of networks.
Preferential attachment has many names but is precisely defined. The term of “Matthew effect” is not a strict equivalent, though. There is an ambiguity about assortativity, which is an equivalent of preferential attachment only in a specific case, despite how some authors refer to the concept.
Scale-free, small world, and complex networks
Those three types of networks are sometimes presented as the same, sometimes not. Fortunately, a simple distinction makes it possible to define a ground where most articles agree:
- The characterizations are not the same. Scale-freeness is not small-worldness is not complexity.
- In practice, those three networks might be the same kinds of networks.
Note that the question of the differences the three types, beyond their characterization, is still open. Some articles claim that it is not useful to separate them, while others enforce the demarcations. However all articles seem to agree that the relevant features for this family of networks are richer than just scale-freeness and small-worldness. In that sense, these categories are more historical than an accurate typology of networks.
In the side template on network science present on many articles, all three types of networks appear on an equal foot.
On the topic of typologies, the article on social networks has a one worthy of Borges, where criteria of widely different sorts seem equally relevant at defining their own kind of networks. It is organized in different levels of analysis, and scale-free networks and complex networks appear as items in different levels:
• Micro level:Social network
o Dyadic level
o Triadic level
o Actor level
o Subset level
• Meso level:
o Randomly distributed networks
o Scale-free networks
• Macro level:
o Large-scale networks
o Complex networks
This article also details these two types of networks, and though the characterization differs, both acknowledge a certain amount of variability in the definition. We also see that the heavy-tail distribution of node degrees is mentioned as a feature of complex networks, which as we have seen is an other way to name the power-law, and thus poses an unnamed equivalence with the characterization of scale-free networks.
“Scale-free networks: A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. […] Specific characteristics of scale-free networks vary with the theories and analytical tools used to create them, however, in general, scale-free networks have some common characteristics. One notable characteristic in a scale-free network is the relative commonness of vertices with a degree that greatly exceeds the average. 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. The Barabási model of network evolution shown above is an example of a scale-free network.”Social network
“Complex networks: Most larger social networks display features of social complexity, which involves substantial non-trivial features of network topology, with patterns of complex connections between elements that are neither purely regular nor purely random […]. 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
Despite their article, social networks are not a specific kind of network but rather an area of application. The three kinds that interest us have each a specific page where the can state their relations to each other.
The small-world network, does not mention the other kinds, but declares a feature of “fat-tailed distribution” which is an equivalent of the power law, and thus an unnamed link to scale-free networks.
“Networks with a greater than expected number of hubs will have a greater fraction of nodes with high degree, and consequently the degree distribution will be enriched at high degree values. This is known colloquially as a fat-tailed distribution.”Small-world network
The scale-free network page starts with the characterization by power-law distribution of node degrees. It also mentions “the small world network model” as a sub-category, and makes several confusing references to the concept of “complex network”, like for instance the caption of this image:
Other example, the mention of “scale-free complex networks” in a paragraph marked as requiring “attention from an expert in Mathematics”.
The complex network article states explicitly its relations with the two other kinds: it is generalizing them, arguing that the original demarcations have lost relevance:
“Two well-known and much studied classes of complex networks are scale-free networks and small-world networks, whose discovery and definition are canonical case-studies in the field. Both are characterized by specific structural features—power-law degree distributions for the former and short path lengths and high clustering for the latter. However, as the study of complex networks has continued to grow in importance and popularity, many other aspects of network structure have attracted attention as well.”Complex network
In that spirit, it assumes an explicitly vague definition. It compensates the drawback of not being a mathematical object by declaring itself as an area of research. It then states a form of correspondance with networks defined by their origin rather than their properties, notably “social networks”.
“In the context of network theory, a complex network is a graph (network) with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in graphs modelling of real systems. The study of complex networks is a young and active area of scientific research (since 2000) inspired largely by the empirical study of real-world networks such as computer networks, technological networks, brain networks and social networks”Complex network
It is interesting to remark that the article on social networks, symmetrically, states an equivalence with complex networks (and as we have seen, with them only).
“Together with other complex networks, it forms part of the nascent field of network science.”Social network
Preferential attachment, cumulative advantage, rich get richer, Yule process, assortativity, and the Matthew effect
The primary definition of preferential attachment is probabilistic even if we will often find it associated with scale-free networks (in our corpus at least).
“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
The following definition (under the name of “the rich get richer”) is similar but more explicit on the implications.
“In statistics, the phrase “the rich get richer” is often used […] 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
This time the equivalence between the different notions is pretty explicit, and the article on preferential attachment explains it. Only the Matthew effect is a little special, and as we have seen it is also considered equivalent to the Pareto distribution. Assortativity is also a special case, as we will see, because it is an equivalent of preferential attachment only in certain cases. Anyway the connection with the power law is central and explicit.
“”Preferential attachment” is only the most recent of many names that have been given to such processes. They are also referred to under the names “Yule process”, “cumulative advantage”, “the rich get richer”, and, less correctly, the “Matthew effect”. They are also related to Gibrat’s law. The principal reason for scientific interest in preferential attachment is that it can, under suitable circumstances, generate power law distributions.”Preferential attachment
Cumulative advantage is another name of preferential attachment, but it seems it is not much employed anymore.
“In a later paper in 1976, Price also proposed a mechanism to explain the occurrence of power laws in citation networks, which he called “cumulative advantage” but which is today more commonly known under the name preferential attachment. […] Barabási and Albert proposed a generative mechanism to explain the appearance of power-law distributions, which they called “preferential attachment” and which is essentially the same as that proposed by Price.”Scale-free network
There is also quite a long explanation about the distinction with the Matthew effect, quoted below for reference.
“Preferential attachment is sometimes referred to as the Matthew effect, but the two are not precisely equivalent. The Matthew effect, first discussed by Robert K. Merton, is named for a passage in the biblical Gospel of Matthew: “For everyone who has will be given more, and he will have an abundance. Whoever does not have, even what he has will be taken from him.” (Matthew 25:29, New International Version.) The preferential attachment process does not incorporate the taking away part. This point may be moot, however, since the scientific insight behind the Matthew effect is in any case entirely different. Qualitatively it is intended to describe not a mechanical multiplicative effect like preferential attachment but a specific human behavior in which people are more likely to give credit to the famous than to the little known. The classic example of the Matthew effect is a scientific discovery made simultaneously by two different people, one well known and the other little known. It is claimed that under these circumstances people tend more often to credit the discovery to the well-known scientist. Thus the real-world phenomenon the Matthew effect is intended to describe is quite distinct from (though certainly related to) preferential attachment.”Preferential attachment
The article on the Matthew effect focuses more on the similitudes than the differences.
“In network science, the Matthew effect is used to describe the preferential attachment of earlier nodes in a network, which explains that these nodes tend to attract more links early on. […] “Because of preferential attachment, a node that acquires more connections than another one will increase its connectivity at a higher rate, and thus an initial difference in the connectivity between two nodes will increase further as the network grows, while the degree of individual nodes will grow proportional with the square root of time.” The Matthew Effect therefore explains the growth of some nodes in vast networks such as the Internet.”Matthew effect
Preferential attachment is also mentioned on the statistical side of the studied articles, as for instance in the article on Zipf’s law.
“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
As a clue on the cultural side of these notions, the article on “The rich get richer and the poor get poorer” is specifically about the aphorism and not the phenomenon itself, which refers to either “wealth concentration” or “economic inequality”.
“This article is about the catchphrase. For the theoretical process, see wealth concentration. […] 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.”The rich get richer and the poor get poorer
Assortativity and homophily
A misunderstanding must be clarified about assortativity, also called homophily.
- Assortativity, or homophily, generally means that in a network the probability that two nodes are connected is higher when those nodes have something in common. This is not specifically related to preferential attachment.
- However when the point in common is the degree (number of neighbors) then assortativity/homophily becomes an avatar of preferential attachment. Unfortunately, it seems that some authors employ a synecdoche where that specific case is named by the more generic concept, causing some confusion.
“Assortativity, or assortative mixing is a preference for a network’s nodes to attach to others that are similar in some way. Though the specific measure of similarity may vary, network theorists often examine assortativity in terms of a node’s degree.”Assortativity
On the use of the term “homophily”, we can cite the article on social network analysis: “Homophily (assortativity)”.
The article on social networks is not specific but mentions “assortativity or disassortativity among vertices” as a feature of complex networks.
Note that awkwardly, “Assortative mixing” seems to be the same thing as assortativity but each has its own page, and each refers to the other.