A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P(k) of nodes in the network having k connections to other nodes goes for large values of k as
P ( k ) ∼ k − γ {\displaystyle P(k)\ \sim \ k^{\boldsymbol {-\gamma }}}
where γ {\displaystyle \gamma } is a parameter whose value is typically in the range 2 < γ < 3 {\textstyle 2<\gamma <3} (wherein the second moment (scale parameter) of k − γ {\displaystyle k^{\boldsymbol {-\gamma }}} is infinite but the first moment is finite), although occasionally it may lie outside these bounds. The name "scale-free" could be explained by the fact that some moments of the degree distribution are not defined, so that the network does not have a characteristic scale or "size". Preferential attachment and the fitness model have been proposed as mechanisms to explain the power law degree distributions in real networks. Alternative models such as super-linear preferential attachment and second-neighbour preferential attachment may appear to generate transient scale-free networks, but the degree distribution deviates from a power law as networks become very large.
History In studies of citations between scientific papers, Derek de Solla Price showed in 1965 that the number of citations a paper receives had a heavy-tailed distribution following a Pareto distribution or power law. 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." However, both treated citations are scalar quantities, rather than a fundamental feature of a new class of networks. The interest in scale-free networks started in 1999 with work by Albert-László Barabási and Réka Albert at the University of Notre Dame who mapped the topology of a portion of the World Wide Web, finding that some nodes, which they called "hubs", had many more connections than others and that the network as a whole had a power-law distribution of the number of links connecting to a node. In a subsequent paper Barabási and Albert showed that the power laws are not a unique property of the WWW, but the feature is present in a few real networks, prompting them to coin the term "scale-free network" to describe the class of networks that exhibit a power-law degree distribution. Barabási and Réka Albert proposed a generative mechanism to explain the appearance of power-law distributions, which they called "preferential attachment". Analytic solutions for this mechanism were presented in 2000 by Dorogovtsev, Mendes and Samukhin and independently by Krapivsky, Redner, and Leyvraz, and later rigorously proved by mathematician Béla Bollobás.
Overview When the concept of "scale-free" was initially introduced in the context of networks, it primarily referred to a specific trait: a power-law distribution for a given variable k {\displaystyle k} , expressed as f ( k ) ∝ k − γ {\displaystyle f(k)\propto k^{-\gamma }} . This property maintains its form when subjected to a continuous scale transformation k → k + ϵ k {\displaystyle k\to k+\epsilon k} , evoking parallels with the renormalization group techniques in statistical field theory. However, there's a key difference. In statistical field theory, the term "scale" often pertains to system size. In the realm of networks, "scale" k {\displaystyle k} is a measure of connectivity, generally quantified by a node's degree—that is, the number of links attached to it. Networks featuring a higher number of high-degree nodes are deemed to have greater connectivity. The power-law degree distribution enables us to make "scale-free" assertions about the prevalence of high-degree nodes. For instance, we can say that "nodes with triple the average connectivity occur half as frequently as nodes with average connectivity". The specific numerical value of what constitutes "average connectivity" becomes irrelevant, whether it's a hundred or a million.
Characteristics
The most notable characteristic in a scale-free network is the relative commonness of vertices with a degree that greatly exceeds the average. The highest-degree nodes are often called "hubs", and are thought to serve specific purposes in their networks, although this depends greatly on the domain. In a random network the maximum degree, or the expected largest hub, scales as kmax~ log N, where N is the network size, a very slow dependence. In contrast, in scale-free networks the largest hub scales as kmax~ ~N1/(γ−1) indicating that the hubs increase polynomically with the size of the network. A key feature of scale-free networks is their high degree heterogeneity, κ= <k2>/<k>, which governs multiple network-based processes, from network robustness to epidemic spreading and network synchronization. While for a random network κ= <k> + 1, i.e. the ration is independent of the network size N, for a scale-free network we have κ~ N(3−γ)/(γ−1), increasing with the network size, indicating that for these networks the degree heterogeneity increases.
… excerpt ends here. Continue reading the full article.
