Scale-free network

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 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 where γ {displaystyle gamma } is a parameter whose value is typically in the range 2 < γ {displaystyle gamma } < 3 (wherein the second moment of k − γ {displaystyle k^{oldsymbol {-gamma }}} is infinite but the first moment is finite), although occasionally it may lie outside these bounds. Many networks have been reported to be scale-free, although statistical analysis has refuted many of these claims and seriously questioned others. Preferential attachment and the fitness model have been proposed as mechanisms to explain conjectured power law degree distributions in real networks. In studies of the networks of citations between scientific papers, Derek de Solla Price showed in 1965 that the number of links to papers—i.e., the number of citations they receive—had a heavy-tailed distribution following a Pareto distribution or power law, and thus that the citation network is scale-free. He did not however use the term 'scale-free network', which was not coined until some decades later. 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. Recent interest in scale-free networks started in 1999 with work by Albert-László Barabási and colleagues 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. After finding that a few other networks, including some social and biological networks, also had heavy-tailed degree distributions, Barabási and collaborators coined the term 'scale-free network' to describe the class of networks that exhibit a power-law degree distribution. However, studying seven examples of networks in social, economic, technological, biological, and physical systems, Amaral et al were not able to find a scale-free network among these seven examples. Only one of these examples, the movie-actor network, had degree distribution P(k) following a power law regime for moderate k, though eventually this power law regime was followed by a sharp cutoff showing exponential decay for large k. 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. Analytic solutions for this mechanism (also similar to the solution of Price) 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. Notably, however, this mechanism only produces a specific subset of networks in the scale-free class, and many alternative mechanisms have been discovered since. The history of scale-free networks also includes some disagreement. On an empirical level, the scale-free nature of several networks has been called into question. For instance, the three brothers Faloutsos believed that the Internet had a power law degree distribution on the basis of traceroute data; however, it has been suggested that this is a layer 3 illusion created by routers, which appear as high-degree nodes while concealing the internal layer 2 structure of the ASes they interconnect. On a theoretical level, refinements to the abstract definition of scale-free have been proposed. For example, Li et al. (2005) recently offered a potentially more precise 'scale-free metric'. Briefly, let G be a graph with edge set E, and denote the degree of a vertex v {displaystyle v} (that is, the number of edges incident to v {displaystyle v} ) by deg ⁡ ( v ) {displaystyle deg(v)} . Define