Editing Scale-free network

{{short description|Network whose degree distribution follows a power law}}
[[File:Degree distribution for a network with 150000 vertices and mean degree = 6 created using the Barabasi-Albert model..png|thumb|Degree distribution for a network with 150000 vertices and mean degree = 6 created using the [[Barabási–Albert model]] (blue dots). The distribution follows an analytical form given by the ratio of two [[gamma function]]s (black line) which approximates as a power-law.]]
{{Network Science}}
A '''scale-free network''' is a [[complex network|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

:<math>
P(k) \ \sim \ k^\boldsymbol{-\gamma}
</math>

where <math>\gamma</math> is a parameter whose value is typically in the range <math display=inline>2<\gamma<3</math> (wherein the second moment ([[scale parameter]]) of <math>k^\boldsymbol{-\gamma}</math> is infinite but the first moment is finite), although occasionally it may lie outside these bounds.<ref>{{Cite journal | last1 = Onnela | first1 = J.-P. | last2 = Saramaki | first2 = J. | last3 = Hyvonen | first3 = J. | last4 = Szabo | first4 = G. | last5 = Lazer | first5 = D. | last6 = Kaski | first6 = K. | last7 = Kertesz | first7 = J. | last8 = Barabasi | first8 = A. -L. | doi = 10.1073/pnas.0610245104 | title = Structure and tie strengths in mobile communication networks | journal = Proceedings of the National Academy of Sciences | volume = 104 | issue = 18 | pages = 7332–7336 | year = 2007 | pmid =  17456605| pmc = 1863470|arxiv = physics/0610104 |bibcode = 2007PNAS..104.7332O | doi-access = free }}</ref><ref>{{Cite journal | last1 = Choromański | first1 = K. | last2 = Matuszak | first2 = M. | last3 = MiȩKisz | first3 = J. | doi = 10.1007/s10955-013-0749-1 | title = Scale-Free Graph with Preferential Attachment and Evolving Internal Vertex Structure | journal = Journal of Statistical Physics | volume = 151 | issue = 6 | pages = 1175–1183 | year = 2013 |bibcode = 2013JSP...151.1175C | doi-access = free }}</ref> 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 (network theory)|fitness model]] have been proposed as mechanisms to explain the power law degree distributions in real networks. Alternative models such as [[Non-linear preferential attachment|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.<ref name="Scale-free networks as preasymptoti">{{cite journal |last1=Krapivsky |first1=Paul |last2=Krioukov |first2=Dmitri |title=Scale-free networks as preasymptotic regimes of superlinear preferential attachment |journal=Physical Review E |date=21 August 2008 |volume=78 |issue=2 |pages=026114 |doi=10.1103/PhysRevE.78.026114|pmid=18850904 |arxiv=0804.1366 |bibcode=2008PhRvE..78b6114K |s2cid=14292535 }}</ref><ref name="Transient">{{cite journal |last1=Falkenberg |first1=Max |last2=Lee |first2=Jong-Hyeok |last3=Amano |first3=Shun-ichi |last4=Ogawa |first4=Ken-ichiro |last5=Yano |first5=Kazuo |last6=Miyake |first6=Yoshihiro |last7=Evans |first7=Tim S. |last8=Christensen |first8=Kim |title=Identifying time dependence in network growth |journal=Physical Review Research |date=18 June 2020 |volume=2 |issue=2 |pages=023352 |doi=10.1103/PhysRevResearch.2.023352 | arxiv=2001.09118|bibcode=2020PhRvR...2b3352F |doi-access=free }}</ref>

==History==
In studies of citations between scientific papers, [[Derek J. de Solla Price|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,<ref>{{Cite journal |last=Albert |first=Réka |last2=Jeong |first2=Hawoong |last3=Barabási |first3=Albert-László |date=9 September 1999 |title=Diameter of the World-Wide Web |url=https://www.nature.com/articles/43601 |journal=Nature |language=en |volume=401 |issue=6749 |pages=130–131 |doi=10.1038/43601 |issn=1476-4687|arxiv=cond-mat/9907038 }}</ref> 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<ref name="Emergence of scaling in random netw">{{cite journal |last1=Barabási |first1=Albert-László |author-link1=Albert-László Barabási |last2=Albert |first2=Réka. |date=15 October 1999 |title=Emergence of scaling in random networks |journal=[[Science (journal)|Science]] |volume=286 |issue=5439 |pages=509–512 |arxiv=cond-mat/9910332 |bibcode=1999Sci...286..509B |doi=10.1126/science.286.5439.509 |mr=2091634 |pmid=10521342 |s2cid=524106}}</ref> [[Albert-László Barabási|Barabási]] and [[Réka Albert|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<ref name="Emergence of scaling in random netw" /> to explain the appearance of power-law distributions, which they called "[[preferential attachment]]". Analytic solutions for this mechanism were presented in 2000 by Dorogovtsev, [[José Fernando Ferreira Mendes|Mendes]] and Samukhin<ref>{{Cite journal | last1 = Dorogovtsev | first1 = S. | last2 = Mendes | first2 = J. | last3 = Samukhin | first3 = A. | doi = 10.1103/PhysRevLett.85.4633 | title = Structure of Growing Networks with Preferential Linking | journal = Physical Review Letters | volume = 85 | issue = 21 | pages = 4633–4636 | year = 2000 | pmid =  11082614|arxiv = cond-mat/0004434 |bibcode = 2000PhRvL..85.4633D | s2cid = 118876189 }}</ref> and independently by Krapivsky, [[Sidney Redner|Redner]], and Leyvraz, and later rigorously proved by mathematician [[Béla Bollobás]].<ref>{{Cite journal | last1 = Bollobás | first1 = B. |author-link1 = Béla Bollobás| last2 = Riordan | first2 = O. | last3 = Spencer | first3 = J. | last4 = Tusnády | first4 = G.| title = The degree sequence of a scale-free random graph process | journal = Random Structures and Algorithms | volume = 18 | issue = 3| pages = 279–290| year = 2001 | doi = 10.1002/rsa.1009 | mr = 1824277| s2cid = 1486779 }}</ref> 

==Overview==
When the concept of "scale-free" was initially introduced in the context of networks,<ref name="Emergence of scaling in random netw"/> it primarily referred to a specific trait: a power-law distribution for a given variable <math>k</math>, expressed as <math>f(k)\propto k^{-\gamma}</math>. This property maintains its form when subjected to a continuous scale transformation <math>k\to k+\epsilon k</math>, evoking parallels with the renormalization group techniques in statistical field theory.<ref name="stat-field-theor-1">{{Cite book
 | last1 = Itzykson
 | first1 = Claude
 | last2 = Drouffe
 | first2 = Jean-Michel
 | title = Statistical Field Theory: Volume 1, From Brownian Motion to Renormalization and Lattice Gauge Theory
 | year = 1989
 | edition = 1st
 | publisher = Cambridge University Press
 | location = New York
 | isbn = 978-0-521-34058-8
 | language = English
}}
</ref><ref name="stat-field-theor-2">{{Cite book
 | last1 = Itzykson
 | first1 = Claude
 | last2 = Drouffe
 | first2 = Jean-Michel
 | title = Statistical Field Theory: Volume 2, Strong Coupling, Monte Carlo Methods, Conformal Field Theory and Random Systems
 | year = 1989
 | edition = 1st
 | publisher = Cambridge University Press
 | location = New York
 | isbn = 978-0-521-37012-7
 | language = English
}}
</ref>

However, there's a key difference. In statistical field theory, the term "scale" often pertains to system size. In the realm of networks, "scale" <math>k</math> 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.<ref name="scale-free_mz23">{{Cite journal
 | last1 = Meng
 | first1 = Xiangyi
 | last2 = Zhou
 | first2 = Bin
 | title = Scale-Free Networks beyond Power-Law Degree Distribution
 | year = 2023
 | journal = Chaos, Solitons & Fractals
 | volume = 176
 | pages = 114173
 | doi = 10.1016/j.chaos.2023.114173
| arxiv = 2310.08110
 | bibcode = 2023CSF...17614173M
 | s2cid = 263909425
 }}</ref> 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.<ref name="scale-free_t05">{{Cite journal
 | last = Tanaka
 | first = Reiko
 | title = Scale-Rich Metabolic Networks
 | year = 2005
 | journal = Phys. Rev. Lett.
 | volume = 94
 | issue = 16
 | pages = 168101
| doi = 10.1103/PhysRevLett.94.168101
 | pmid = 15904266
 | bibcode = 2005PhRvL..94p8101T
 }}
</ref>

==Characteristics==
[[Image:Scale-free network sample.svg|thumb|right|Random network (a) and scale-free network (b)]]
[[File:Complex network degree distribution of random and scale-free.png|thumb|Complex network degree distribution of random and scale-free]]

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 ''k<sub>max</sub>~ log N'', where ''N'' is the network size, a very slow dependence. In contrast, in scale-free networks the largest hub scales as ''k<sub>max</sub>~ ~N<sup>1/(γ−1)</sup>'' indicating that the hubs increase polynomically with the size of the network. 

A key  feature of scale-free networks is their high degree heterogeneity,  κ= ''<k<sup>2</sup>>/<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<sup>(3−γ)/(γ−1)</sup>'', increasing with the network size, indicating that for these networks the degree heterogeneity increases.

===Clustering===
Another important characteristic of scale-free networks is the [[clustering coefficient]] distribution, which decreases as the node degree increases. This distribution also follows a power law. This implies that the low-degree nodes belong to very dense sub-graphs and those sub-graphs are connected to each other through hubs. Consider a social network in which nodes are people and links are acquaintance relationships between people. It is easy to see that people tend to form communities, i.e., small groups in which everyone knows everyone (one can think of such community as a [[complete graph]]). In addition, the members of a community also have a few acquaintance relationships to people outside that community. Some people, however, are connected to a large number of communities (e.g., celebrities, politicians). Those people may be considered the hubs responsible for the [[small-world phenomenon]].

At present, the more specific characteristics of scale-free networks vary with the generative mechanism used to create them. For instance, networks generated by preferential attachment typically place the high-degree vertices in the middle of the network, connecting them together to form a core, with progressively lower-degree nodes making up the regions between the core and the periphery. The random removal of even a large fraction of vertices impacts the overall connectedness of the network very little, suggesting that such topologies could be useful for [[network security|security]], while targeted attacks destroys the connectedness very quickly. Other scale-free networks, which place the high-degree vertices at the periphery, do not exhibit these properties. Similarly, the clustering coefficient of scale-free networks can vary significantly depending on other topological details.

===Immunization===
The question of how to immunize efficiently scale free networks which represent realistic networks such as the Internet and social networks has been studied extensively. One such strategy is to immunize the largest degree nodes, i.e., targeted (intentional) attacks since for this case p<math>c</math> is relatively high and less nodes are needed to be immunized. 
However, in many realistic cases the global structure is not available and the largest degree nodes are not known.

Properties of random graph may change or remain invariant under graph transformations. [[Alireza Mashaghi|Mashaghi A.]] et al., for example, demonstrated that a transformation which converts random graphs to their edge-dual graphs (or line graphs) produces an ensemble of graphs with nearly the same degree distribution, but with degree correlations and a significantly higher clustering coefficient. Scale free graphs, as such, remain scale free under such transformations.<ref name="journals.aps.org">{{cite journal | last1 = Ramezanpour | first1 = A. | last2 = Karimipour | first2 = V. | last3 = Mashaghi | first3 = A. | year = 2003 | title = Generating correlated networks from uncorrelated ones | journal = Phys. Rev. E | volume = 67 | issue = 4| page = 046107 | doi=10.1103/PhysRevE.67.046107| arxiv = cond-mat/0212469 | bibcode = 2003PhRvE..67d6107R | pmid=12786436| s2cid = 33054818 }}</ref>

==Examples==
Examples of networks found to be scale-free include:

* Some [[Social network]]s, including collaboration networks. Two examples that have been studied extensively are [[Six Degrees of Kevin Bacon|the collaboration of movie actors in films]] and [[Erdős number|the co-authorship by mathematicians of papers]].
* Many kinds of [[computer network]]s, including the [[internet]] and the [[webgraph]] of the [[World Wide Web]].
* Some financial networks such as interbank payment networks <ref>{{cite journal|title=Fitness model for the Italian interbank money market|journal=Physical Review E|year=2006|first=Giulia|last=De Masi |display-authors=etal |volume=74|issue=6|pages=066112|doi= 10.1103/PhysRevE.74.066112|pmid=17280126|arxiv=physics/0610108|bibcode=2006PhRvE..74f6112D|s2cid=30814484}}</ref><ref>{{cite journal|title=The topology of interbank payment flows|journal=Physica A: Statistical Mechanics and Its Applications|year=2007|first=Kimmo|last=Soramäki |display-authors=etal |volume=379|issue=1|pages=317–333|doi= 10.1016/j.physa.2006.11.093|bibcode = 2007PhyA..379..317S |hdl=10419/60649|hdl-access=free}}</ref>
* [[Protein–protein interaction]] networks.
* [[Semantic network]]s.<ref>{{cite journal|title=The Large-Scale Structure of Semantic Networks: Statistical Analyses and a Model of Semantic Growth|journal=Cognitive Science|year=2005|first=Mark|last=Steyvers|author2=Joshua B. Tenenbaum |volume=29|issue=1|pages=41–78|doi= 10.1207/s15516709cog2901_3|pmid=21702767|arxiv=cond-mat/0110012|s2cid=6000627}}</ref>
* Airline networks.

Scale free topology has been also found in high temperature superconductors.<ref>{{cite journal |doi=10.1038/nature09260 |last1=Fratini |first1=Michela |last2=Poccia |first2=Nicola |last3=Ricci |first3=Alessandro |last4=Campi |first4=Gaetano |last5=Burghammer |first5=Manfred |last6=Aeppli |first6=Gabriel |last7=Bianconi |first7=Antonio |title=Scale-free structural organization of oxygen interstitials in La2CuO4+y |journal=Nature |volume=466 |issue=7308 |pages=841–4 |year=2010 |pmid=20703301|arxiv = 1008.2015 |bibcode = 2010Natur.466..841F |s2cid=4405620 }}</ref> The qualities of a high-temperature superconductor — a compound in which electrons obey the laws of quantum physics, and flow in perfect synchrony, without friction — appear linked to the fractal arrangements of seemingly random oxygen atoms and lattice distortion.<ref>{{cite journal |doi=10.1073/pnas.1208492109 |last1=Poccia |first1=Nicola |last2=Ricci |first2=Alessandro |last3=Campi |first3=Gaetano |last4=Fratini |first4=Michela |last5=Puri |first5=Alessandro |last6=Di Gioacchino |first6=Daniele |last7=Marcelli |first7=Augusto |last8=Reynolds |first8=Michael |last9=Burghammer |first9=Manfred |last10=Saini |first10=Naurang L. |last11=Aeppli |first11=Gabriel |last12=Bianconi |first12=Antonio |title=Optimum inhomogeneity of local lattice distortions in La2CuO4+y |journal=PNAS |volume=109 |issue=39 |pages=15685–15690 |year=2012 |pmid=22961255|pmc=3465392 |arxiv = 1208.0101 |bibcode =2012PNAS..10915685P  |doi-access=free }}</ref>

==Generative models==
Scale-free networks do not arise by chance alone. [[Paul Erdős|Erdős]] and Rényi (1960) studied a model of growth for graphs in which, at each step, two nodes are chosen uniformly at random and a link is inserted between them. The properties of these [[random graph]]s are different from the properties found in scale-free networks, and therefore a model for this growth process is needed.

The most widely known generative model for a subset of scale-free networks is Barabási and Albert's (1999) [[rich get richer]] generative model in which each new Web page creates links to existing Web pages with a probability distribution which is not uniform, but
proportional to the current in-degree of Web pages.  According to this process, a page with many in-links will attract more in-links than a regular page. This generates a power-law but the resulting graph differs from the actual Web graph in other properties such as the presence of small tightly connected communities. More general models and network characteristics have been proposed and studied. For example, Pachon et al. (2018) proposed a variant of the [[rich get richer]] generative model which takes into account two different attachment rules: a preferential attachment mechanism and a uniform choice only for the most recent nodes.<ref name="PSY"/> For a review see the book by Dorogovtsev and [[José Fernando Ferreira Mendes|Mendes]].{{Citation needed|date=December 2020}} Some mechanisms such as [[Non-linear preferential attachment|super-linear preferential attachment]] and second neighbour attachment generate networks which are transiently scale-free, but deviate from a power law as networks grow large.<ref name="Scale-free networks as preasymptoti"/><ref name="Transient"/>

A somewhat different generative model for Web links has been suggested by Pennock et al. (2002). They examined communities with interests in a specific topic such as the home pages of universities, public companies, newspapers or scientists, and discarded the major hubs of the Web. In this case, the distribution of links was no longer a power law but resembled a [[normal distribution]]. Based on these observations, the authors proposed a generative model that mixes preferential attachment with a baseline probability of gaining a link.

Another generative model is the '''copy''' model studied by Kumar et al.<ref>{{cite conference |last1=Kumar |first1=Ravi |last2=Raghavan |first2=Prabhakar |title=Stochastic Models for the Web Graph |year=2000 |conference=Foundations of Computer Science, 41st Annual Symposium on |pages=57–65 |url=http://cs.brown.edu/research/webagent/focs-2000.pdf |doi=10.1109/SFCS.2000.892065 |access-date=2016-02-10 |archive-date=2016-03-03 |archive-url=https://web.archive.org/web/20160303181517/http://cs.brown.edu/research/webagent/focs-2000.pdf |url-status=live }}</ref> (2000),
in which new nodes choose an existent node at random and copy a fraction of the links of the existent node. This also generates a power law.

There are two major components that explain the emergence of the power-law distribution in the [[Barabási–Albert model]]: the growth and the preferential attachment.<ref name="NETWORK BIOLOGY: UNDERSTANDING THE">{{cite journal
 |last1=Barabási |first1=Albert-László |author-link1=Albert-László Barabási
 |last2=Zoltán N. |first2= Oltvai.
 |title=Network biology: understanding the cell's functional organization
 |doi=10.1038/nrg1272
 |volume=5
 |year=2004
 |journal=Nature Reviews Genetics
 |issue=2 |pages=101–113
 |pmid=14735121
 |s2cid=10950726 }}</ref> 
By "growth" is meant a growth process where, over an extended period of time, new nodes join an already existing system, a network (like the World Wide Web which has grown by billions of web pages over 10 years). Finally, by "preferential attachment" is meant that new nodes prefer to connect to nodes that already have a high number of links with others. Thus, there is a higher probability that more and more nodes will link themselves to that one which has already many links, leading this node to a hub ''in-fine''.<ref name="Emergence of scaling in random netw"/>
Depending on the network, the hubs might either be assortative or disassortative. Assortativity would be found in social networks in which well-connected/famous people would tend to know better each other. Disassortativity would be found in technological (Internet, World Wide Web) and biological (protein interaction, metabolism) networks.<ref name="NETWORK BIOLOGY: UNDERSTANDING THE"/>

However, the ''growth'' of the networks (adding new nodes) is not a necessary condition for creating a scale-free network (see 
Dangalchev<ref name = "CAD">{{cite journal |last1=Dangalchev |first1=Chavdar |title=Generation models for scale-free networks |journal=Physica A: Statistical Mechanics and Its Applications |date=July 2004 |volume=338 |issue=3–4 |pages=659–671 |doi=10.1016/j.physa.2004.01.056|bibcode=2004PhyA..338..659D |url=https://zenodo.org/record/1259307 }}</ref>). One possibility (Caldarelli et al. 2002) is to consider the structure as static and draw a link between vertices according to a particular property of the two vertices involved. Once specified the statistical distribution for these vertex properties (fitnesses), it turns out that in some circumstances also static networks develop scale-free properties.

==Generalized scale-free model==
There has been a burst of activity in the modeling of [[Scale-free networks|scale-free complex networks]]. The recipe of Barabási and Albert<ref name=BA>Barabási, A.-L. and R. Albert, Science '''286''', 509 (1999).</ref> has been followed by several variations and generalizations<ref name=AB>R. Albert, and A.L. Barabási, Phys. Rev. Lett. '''85''', 5234(2000).</ref><ref name=Doro>S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhim, cond-mat/0011115.</ref><ref name=Krap>P.L. Krapivsky, S. Redner, and F. Leyvraz, Phys. Rev. Lett. '''85''', 4629 (2000).</ref><ref name=Tadic>B. Tadic, Physica A '''293''', 273(2001).</ref><ref name=PSY>{{cite journal|title=Scale-free behavior of networks with the copresence of preferential and uniform attachment rules|journal=Physica D: Nonlinear Phenomena|volume=371|pages=1–12|year=2018|first1=Angelica |last1=Pachon |first2=Laura |last2=Sacerdote |first3=Shuyi |last3=Yang |doi=10.1016/j.physd.2018.01.005|arxiv=1704.08597|bibcode=2018PhyD..371....1P|s2cid=119320331}}</ref> and the revamping of previous mathematical works.<ref name=Bom>S. Bomholdt and H. Ebel, cond-mat/0008465; H.A. Simon, Bimetrika '''42''', 425(1955).</ref> 

In today's terms, if a complex network has a power-law distribution of any of its metrics, it's generally considered a scale-free network. Similarly, any model with this feature is called a scale-free model.<ref name="scale-free_mz23">{{Cite journal
 | last1 = Meng
 | first1 = Xiangyi
 | last2 = Zhou
 | first2 = Bin
 | title = Scale-Free Networks beyond Power-Law Degree Distribution
 | year = 2023
 | journal = Chaos, Solitons & Fractals
 | volume = 176
 | pages = 114173
 | doi = 10.1016/j.chaos.2023.114173
| arxiv = 2310.08110
 | bibcode = 2023CSF...17614173M
 | s2cid = 263909425
 }}</ref>

===Features===
Many real networks are (approximately) scale-free and hence require scale-free models to describe them. In Price's scheme, there are two ingredients needed to build up a scale-free model:

1. Adding or removing [[Node (networking)|nodes]]. Usually we concentrate on growing the network, i.e. adding nodes.

2. [[Preferential attachment]]: The probability <math>\Pi</math> that new nodes will be connected to the "old" node.

Note that some models (see 
Dangalchev<ref name = "CAD" /> and
Fitness model below) can work also statically, without changing the number of nodes. It should also be kept in mind that the fact that "preferential attachment" models give rise to scale-free networks does not prove that this is the mechanism underlying the evolution of real-world scale-free networks, as there might exist different mechanisms at work in real-world systems that nevertheless give rise to scaling.

===Examples===
There have been several attempts to generate scale-free network properties. Here are some examples:

====The Barabási–Albert model====
The [[Barabási–Albert model]], an undirected version of [[Price's model]] has a linear preferential attachment <math>\Pi(k_i)=\frac{k_i}{\sum_j k_j}</math> and adds one new node at every time step.

(Note, another general feature of <math>\Pi(k)</math> in real networks is that <math>\Pi(0)\neq 0</math>, i.e. there is a nonzero probability that a
new node attaches to an isolated node. Thus in general <math>\Pi(k)</math> has the form <math>\Pi(k)=A +k^\alpha</math>, where <math>A</math> is the initial attractiveness of the node.)

====Two-level network model====

Dangalchev (see <ref name = "CAD" />) builds a 2-L model by considering the importance of each of the neighbours of a target node in preferential attachment. The attractiveness of a node in the 2-L model depends not only on the number of nodes linked to it but also on the number of links in each of these nodes.

: <math>\Pi(k_i)=\frac{k_i + C \sum_{(i,j)} k_j}{\sum_j k_j + C \sum_j k_j^2},</math>

where ''C'' is a coefficient between 0 and&nbsp;1.

A variant of the 2-L model, the k2 model, where first and second neighbour nodes contribute equally to a target node's attractiveness, demonstrates the emergence of transient scale-free networks.<ref name="Transient"/> In the k2 model, the degree distribution appears approximately scale-free as long as the network is relatively small, but significant deviations from the scale-free regime emerge as the network grows larger. This results in the relative attractiveness of nodes with different degrees changing over time, a feature also observed in real networks.

====Mediation-driven attachment (MDA) model====

In the [[mediation-driven attachment model|mediation-driven attachment (MDA) model]], a new node coming with <math>m</math> edges picks an existing connected node at random and then connects itself, not with that one, but with <math>m</math> of its neighbors, also chosen at random. The probability <math>\Pi(i)</math> that the node <math>i</math> of the existing node picked is

: <math> \Pi(i) = \frac{k_i} N \frac{\sum_{j=1}^{k_i} \frac 1 {k_j} }{k_i}.</math>

The factor <math>\frac{\sum_{j=1}^{k_i} \frac 1 {k_j} }{k_i}</math> is the inverse of the harmonic mean
(IHM) of degrees of the <math>k_i</math> neighbors of a node <math>i</math>. Extensive numerical investigation suggest that for approximately <math>m> 14</math> the mean IHM value in the large <math>N</math> limit becomes a constant which means <math>\Pi(i) \propto k_i</math>. It implies that the higher the
links (degree) a node has, the higher its chance of gaining more links since they can be
reached in a larger number of ways through mediators which essentially embodies the intuitive
idea of rich get richer mechanism (or the preferential attachment rule of the Barabasi–Albert model). Therefore, the MDA network can be seen to follow
the PA rule but in disguise.<ref>{{cite journal | last1 = Hassan | first1 = M. K. | last2 = Islam | first2 = Liana | last3 = Arefinul Haque | first3 = Syed | year = 2017 | title = Degree distribution, rank-size distribution, and leadership persistence in mediation-driven attachment networks | doi = 10.1016/j.physa.2016.11.001 | journal = Physica A | volume = 469 | pages = 23–30 | arxiv = 1411.3444 | bibcode = 2017PhyA..469...23H | s2cid = 51976352 }}</ref>

However, for <math>m=1</math> it describes the winner takes it all mechanism as we find that almost <math>99\%</math> of the total nodes has degree one and one is super-rich in degree. As <math>m</math> value increases the disparity between the super rich and poor decreases and as <math>m>14</math> we find a transition from rich get super richer to rich get richer mechanism.

====Non-linear preferential attachment====
{{See also|Non-linear preferential attachment}}
The Barabási–Albert model assumes that the probability <math>\Pi(k)</math> that a node attaches to node <math>i</math> is proportional to the [[degree (graph theory)|degree]] <math>k</math> of node <math>i</math>. This assumption involves two hypotheses: first, that <math>\Pi(k)</math> depends on <math>k</math>, in contrast to random graphs in which <math>\Pi(k) = p </math>, and second, that the functional form of <math>\Pi(k)</math> is linear in <math>k</math>.

In non-linear preferential attachment, the form of <math>\Pi(k)</math> is not linear, and recent studies have demonstrated that the degree distribution depends strongly on the shape of the function <math>\Pi(k)</math>

Krapivsky, Redner, and Leyvraz<ref name="Krap"/> demonstrate that the scale-free nature of the network is destroyed for nonlinear preferential attachment. The only case in which the topology of the network is scale free is that in which the preferential attachment is [[asymptotically]] linear, i.e. <math>\Pi(k_i)  \sim a_\infty k_i</math> as <math>k_i \to \infty</math>. In this case the rate equation leads to

: <math> P(k) \sim k^{-\gamma}\text{ with }\gamma = 1 + \frac \mu {a_\infty}.</math>

This way the exponent of the degree distribution can be tuned to any value between 2 and <math>\infty</math>.{{clarify|reason=What is mu?|date=November 2021}}

====Hierarchical network model====
[[Hierarchical network model]]s are, by design, scale free and have high clustering of nodes.<ref name=Rav>{{cite journal | last1 = Ravasz | first1 = E. | last2 = Barabási | year = 2003 | title =  Hierarchical organization in complex networks| journal = Phys. Rev. E | volume = 67 | issue = 2| page = 026112 | doi=10.1103/physreve.67.026112| pmid = 12636753 | arxiv = cond-mat/0206130| bibcode = 2003PhRvE..67b6112R| s2cid = 17777155 }}</ref>

The [[Iterative hierarchy|iterative]] construction leads to a hierarchical network. Starting from a fully connected cluster of five nodes, we create four identical replicas connecting the peripheral nodes of each cluster to the central node of the original cluster. From this, we get a network of 25 nodes (''N''&nbsp;=&nbsp;25).
Repeating the same process, we can create four more replicas of the original cluster – the four peripheral nodes of each one connect to the central node of the nodes created in the first step. This gives ''N''&nbsp;=&nbsp;125, and the process can continue indefinitely.

====Fitness model====
The idea is that the link between two vertices is assigned not randomly with a probability ''p'' equal for all the couple of vertices. Rather, for 
every vertex ''j'' there is an intrinsic ''fitness'' ''x''<sub>''j''</sub> and a link between vertex ''i'' and ''j'' is created with a probability 
<math> p(x_i,x_j)</math>.<ref name=Cal>{{cite journal | last1 = Caldarelli | first1 = G. | display-authors = etal | year = 2002 | title =  Scale-free networks from varying vertex intrinsic fitness| doi = 10.1103/physrevlett.89.258702 | journal = Phys. Rev. Lett. | volume = 89 | issue = 25| page = 258702 | pmid=12484927| bibcode = 2002PhRvL..89y8702C | url = http://eprints.imtlucca.it/1137/1/PhysRevLett_Caldarelli_02.pdf }}</ref> 
In the case of World Trade Web it is possible to reconstruct all the properties by using as fitnesses of the country their GDP, and taking

: <math> p(x_i,x_j)=\frac {\delta x_ix_j}{1+\delta x_ix_j}. </math><ref name=Gar>{{cite journal | last1 = Garlaschelli | first1 = D. | display-authors = etal | year = 2004 | title =  Fitness-Dependent Topological Properties of the World Trade Web| doi =10.1103/physrevlett.93.188701 | journal = Phys. Rev. Lett. | volume = 93 | issue = 18| page = 188701 | pmid = 15525215 | bibcode=2004PhRvL..93r8701G| arxiv = cond-mat/0403051 | s2cid = 16367275 }}</ref>

====Hyperbolic geometric graphs====
{{Main|Hyperbolic geometric graph}}
Assuming that a network has an underlying hyperbolic geometry, one can use the framework of [[spatial network]]s to generate scale-free degree distributions. This heterogeneous degree distribution then simply reflects the negative curvature and metric properties of the underlying hyperbolic geometry.<ref name=RefDimaPre>{{cite journal|last1=Krioukov|first1=Dmitri|last2=Papadopoulos|first2=Fragkiskos|last3=Kitsak|first3=Maksim|last4=Vahdat|first4=Amin|last5=Boguñá|first5=Marián|title=Hyperbolic geometry of complex networks|journal=Physical Review E|volume=82|issue=3|doi=10.1103/PhysRevE.82.036106|year=2010|arxiv=1006.5169|bibcode=2010PhRvE..82c6106K|pmid=21230138|page=036106|s2cid=6451908}}</ref>

====Edge dual transformation to generate scale free graphs with desired properties====

Starting with scale free graphs with low degree correlation and clustering coefficient, one can generate new graphs with much higher degree correlations and clustering coefficients by applying edge-dual transformation.<ref name="journals.aps.org"/>

====Uniform-preferential-attachment model (UPA model)====

[[UPA model]] is a variant of the preferential attachment model (proposed by Pachon et al.) which takes into account two different attachment rules: a preferential attachment mechanism (with probability 1−p) that stresses the rich get richer system, and a uniform choice (with probability p) for the most recent nodes. This modification is interesting to study the robustness of the scale-free behavior of the degree distribution. It is proved analytically that the asymptotically power-law degree distribution is preserved.<ref name=PSY />

==Scale-free ideal networks==
In the context of [[network theory]] a '''scale-free ideal network''' is a [[random network]] with a [[degree distribution]] following the [[Scale-Free Ideal Gas|scale-free ideal gas]] [[Probability density function|density distribution]]. These networks are able to reproduce city-size distributions and electoral results by unraveling the size distribution of social groups with information theory on complex networks when a competitive cluster growth process is applied to the network.<ref>{{cite arXiv |author1=A. Hernando |author2=D. Villuendas |author3=C. Vesperinas |author4=M. Abad |author5=A. Plastino |eprint=0905.3704 |class=physics.soc-ph |title=Unravelling the size distribution of social groups with information theory on complex networks |year=2009 }}, submitted to ''European Physical Journal B''</ref><ref>
{{cite journal |author1=André A. Moreira |author2=Demétrius R. Paula |author3=Raimundo N. Costa Filho |author4=José S. Andrade, Jr. |arxiv=cond-mat/0603272 |title=Competitive cluster growth in complex networks |year=2006 |doi=10.1103/PhysRevE.73.065101 |volume=73 |issue=6 |journal=Physical Review E|bibcode=2006PhRvE..73f5101M |pmid=16906890 |page=065101|s2cid=45651735 }}</ref> In models of scale-free ideal networks it is possible to demonstrate that [[Dunbar's number]] is the cause of the phenomenon known as the '[[six degrees of separation]]'.

==Novel characteristics==
For a scale-free network with <math>n</math> nodes and power-law exponent <math>\gamma>3</math>, the induced subgraph constructed by vertices with degrees larger than <math>\log{n}\times \log^{*}{n}</math> is a scale-free network with <math>\gamma'=2</math>, [[almost surely]].<ref>{{cite arXiv |author=Heydari, H. |author2=Taheri, S.M. |author3=Kaveh, K. |title=Distributed Maximal Independent Set on Scale-Free Networks | year=2018 |eprint=1804.02513 |class=cs.DC }}</ref>

== The scale-free metric ==
On a theoretical level, refinements to the abstract definition of scale-free have been proposed. For example, Li et al. (2005) 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 <math>v</math> (that is, the number of edges incident to <math>v</math>) by <math>\deg(v)</math>. Define
: <math>s(G) = \sum_{(u,v) \in E} \deg(u) \cdot \deg(v).</math>

This is maximized when high-degree nodes are connected to other high-degree nodes. Now define

: <math>S(G) = \frac{s(G)}{s_\max},</math>

where ''s''<sub>max</sub> is the maximum value of ''s''(''H'') for ''H'' in the set of all graphs with degree distribution identical to that of&nbsp;''G''. This gives a metric between 0 and 1, where a graph ''G'' with small ''S''(''G'') is "scale-rich", and a graph ''G'' with ''S''(''G'') close to 1 is "scale-free". This definition captures the notion of [[self-similarity]] implied in the name "scale-free".

==Estimating the power law exponent==
Estimating the power-law exponent <math>\gamma</math> of a scale-free network is typically done by using the [[Power law#Estimating the exponent from empirical data|maximum likelihood estimation]] with the degrees of a few uniformly sampled nodes.<ref name="Clauset">{{Cite journal |last=Clauset |first=Aaron |author2=Cosma Rohilla Shalizi |author3=M. E. J Newman |year=2009 |title=Power-law distributions in empirical data |journal=SIAM Review |volume=51 |issue=4 |pages=661–703 |arxiv=0706.1062 |bibcode=2009SIAMR..51..661C |doi=10.1137/070710111 |s2cid=9155618}}</ref> However, since uniform sampling does not obtain enough samples from the important heavy-tail of the power law degree distribution, this method can yield a large bias and a variance. It has been recently proposed to sample random friends (i.e., random ends of random links) who are more likely come from the tail of the degree distribution as a result of the [[friendship paradox]].<ref>{{Cite journal |last1=Eom |first1=Young-Ho |last2=Jo |first2=Hang-Hyun |date=2015-05-11 |title=Tail-scope: Using friends to estimate heavy tails of degree distributions in large-scale complex networks |journal=Scientific Reports |volume=5 |issue=1 |page=9752 |doi=10.1038/srep09752 |pmid=25959097 |pmc=4426729 |arxiv=1411.6871 |bibcode=2015NatSR...5.9752E |issn=2045-2322|doi-access=free }}</ref><ref name=":0">{{Cite journal |last1=Nettasinghe |first1=Buddhika |last2=Krishnamurthy |first2=Vikram |date=2021-05-19 |title=Maximum Likelihood Estimation of Power-law Degree Distributions via Friendship Paradox-based Sampling |journal=ACM Transactions on Knowledge Discovery from Data |volume=15 |issue=6 |pages=1–28 |doi=10.1145/3451166 |issn=1556-4681|doi-access=free |arxiv=1908.00310 }}</ref> Theoretically, maximum likelihood estimation with random friends lead to a smaller bias and a smaller variance compared to classical approach based on uniform sampling.<ref name=":0" />

==See also==
* {{annotated link|Random graph}}
* {{annotated link|Erdős–Rényi model}}
* {{annotated link|Non-linear preferential attachment}}
* {{annotated link|Bose–Einstein condensation (network theory)}}
* {{annotated link|Scale invariance}}
* {{annotated link|Complex network}}
* {{annotated link|Webgraph}}
* {{annotated link|Barabási–Albert model}}
* {{annotated link|Bianconi–Barabási model}}

==References==
{{reflist}}

==Further reading==
*{{cite journal |doi=10.1103/RevModPhys.74.47 |author1=Albert R. |author2=Barabási A.-L. |title=Statistical mechanics of complex networks |journal=Rev. Mod. Phys. |volume=74 |pages=47–97 |year=2002 |issue=1 |url=http://www.nd.edu/~networks/Publication%20Categories/publications.htm#anchor-allpub0001 |bibcode=2002RvMP...74...47A|arxiv = cond-mat/0106096 |s2cid=60545 }}
*{{cite journal |doi=10.1073/pnas.200327197 |vauthors=((Amaral LAN)), Scala A, Barthelemy M, Stanley HE |title=Classes of small-world networks |journal=PNAS |volume=97 |issue=21 |pages=11149–52 |year=2000 |pmid=11005838 |pmc=17168 |arxiv=cond-mat/0001458 |bibcode = 2000PNAS...9711149A |doi-access=free }}
*{{cite book |author=Barabási, Albert-László |title=Linked: How Everything is Connected to Everything Else |year=2004 |publisher=Perseus Pub. |isbn=0-452-28439-2 |url-access=registration |url=https://archive.org/details/linkedhoweveryth00bara }}
*{{cite journal |doi=10.1038/scientificamerican0503-60 |author=Barabási, Albert-László |last2=Bonabeau |first2=Eric |title=Scale-Free Networks |journal=Scientific American |volume=288 |pages=50–9 |date=May 2003 |url=http://www.nd.edu/~networks/Publication%20Categories/01%20Review%20Articles/ScaleFree_Scientific%20Ameri%20288,%2060-69%20(2003).pdf |issue=5|pmid=12701331 |bibcode=2003SciAm.288e..60B }}
*{{cite journal |doi=10.1103/PhysRevE.69.016113 |author1=Dan Braha |author2=Yaneer Bar-Yam |title=Topology of Large-Scale Engineering Problem-Solving Networks |journal=Phys. Rev. E |volume=69 |pages=016113  |year=2004 |issue=1 |pmid=14995673 |url=http://necsi.edu/affiliates/braha/Topology--of--Large--Scale--Design--PRE69.pdf |bibcode = 2004PhRvE..69a6113B |s2cid=1001176 }}
* Caldarelli G. "[http://www.oup.com/us/catalog/general/subject/Physics/Mathematicalphysics/~~/dmlldz11c2EmY2k9OTc4MDE5OTIxMTUxNw==  Scale-Free Networks"] Oxford University Press, Oxford (2007).
*{{cite journal |doi=10.1103/PhysRevLett.89.258702 |author1=Caldarelli G. |author2=Capocci A. |author3=De Los Rios P. |author4=Muñoz M.A. |title=Scale-free networks from varying vertex intrinsic fitness |journal=Physical Review Letters |volume=89 |issue=25 |pages=258702  |year=2002 |pmid=12484927 |arxiv=cond-mat/0207366 |bibcode=2002PhRvL..89y8702C}}
*{{cite journal |author=Dangalchev, Ch. |title=Generation models for scale-free networks |journal=Physica A |volume=338 |issue=3–4 |year=2004 |doi=10.1016/j.physa.2004.01.056 |pages=659–671|bibcode=2004PhyA..338..659D |url=https://zenodo.org/record/1259307 }}
*{{cite journal |author=Dorogovtsev, S.N. |author2=Mendes, J.F.F. |author3=Samukhin, A.N. |title=Structure of Growing Networks: Exact Solution of the Barabási—Albert's Model |journal=Phys. Rev. Lett. |volume=85 |issue=21 |pages=4633–6 |year=2000 |pmid=11082614 |doi=10.1103/PhysRevLett.85.4633 |bibcode=2000PhRvL..85.4633D|arxiv = cond-mat/0004434 |s2cid=118876189 }}
*{{cite book |author=Dorogovtsev, S.N. |author2=Mendes, J.F.F. |title=Evolution of Networks: from biological networks to the Internet and WWW |publisher=Oxford University Press |year=2003 |isbn=0-19-851590-1 }}
*{{cite journal |author=Dorogovtsev, S.N. |author2=Goltsev A.V. |author3=Mendes, J.F.F. |title= Critical phenomena in complex networks |journal= Rev. Mod. Phys. |volume=80 |issue= 4 |pages=1275–1335 |year=2008 | doi = 10.1103/RevModPhys.80.1275 |bibcode=2008RvMP...80.1275D|arxiv = 0705.0010 |s2cid=3174463 }}
*{{cite journal |doi=10.1080/00018730110112519 |author=Dorogovtsev, S.N. |author2=Mendes, J.F.F. |title=Evolution of networks |journal=Advances in Physics |volume=51 |issue=4 |pages=1079–1187 |year=2002 |arxiv = cond-mat/0106144 |bibcode = 2002AdPhy..51.1079D |s2cid=429546 }}
*{{cite book |last1=Erdős |first1=P. |author-link1=Paul Erdős |last2=Rényi |first2=A. |author-link2=Alfréd Rényi |title=On the Evolution of Random Graphs |publisher=Publication of the Mathematical Institute of the Hungarian Academy of Science |year=1960 |volume=5 |pages=17–61 |url=http://www.math-inst.hu/~p_erdos/1960-10.pdf }}
*{{cite journal |doi=10.1145/316194.316229 |author=Faloutsos, M. |author2=Faloutsos, P. |author3=Faloutsos, C. |title=On power-law relationships of the internet topology |journal=Comp. Comm. Rev. |volume=29 |issue=4 |pages=251–262 |year=1999 }}
*{{cite arXiv |author=Li, L. |author2=Alderson, D. |author3=Tanaka, R. |author4=Doyle, J.C. |author5=Willinger, W. |eprint=cond-mat/0501169 |title=Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version) |year=2005 }}
*{{cite conference |url=http://www.cs.brown.edu/research/webagent/focs-2000.pdf |title=Stochastic models for the web graph |author=Kumar, R. |author2=Raghavan, P. |author3=Rajagopalan, S. |author4=Sivakumar, D. |author5=Tomkins, A. |author6=Upfal, E. |year=2000 |publisher=IEEE CS Press |book-title=Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS) |pages=57–65 |location=Redondo Beach, CA }}
*{{cite news |author=Matlis, Jan |title=Scale-Free Networks |url=http://www.computerworld.com/networkingtopics/networking/story/0,10801,75539,00.html |date=November 4, 2002 }}
*{{cite journal |author=Newman, Mark E.J. |arxiv=cond-mat/0303516 |title=The structure and function of complex networks |year=2003 |doi=10.1137/S003614450342480 |bibcode=2003SIAMR..45..167N |volume=45 |issue=2 |journal=SIAM Review |pages=167–256|s2cid=221278130 }}
*{{cite book |author=Pastor-Satorras, R. |author2=Vespignani, A. |title=Evolution and Structure of the Internet: A Statistical Physics Approach |publisher=Cambridge University Press |year=2004 |isbn=0-521-82698-5 }}
*{{cite journal |doi=10.1073/pnas.032085699 |author=Pennock, D.M. |author2=Flake, G.W. |author3=Lawrence, S. |author4=Glover, E.J. |author5=Giles, C.L. |title=Winners don't take all: Characterizing the competition for links on the web |journal=PNAS |volume=99 |issue=8 |pages=5207–11 |year=2002 |url=http://www.modelingtheweb.com/ |pmid=16578867 |pmc=122747|bibcode = 2002PNAS...99.5207P |doi-access=free }}
* Robb, John. [http://globalguerrillas.typepad.com/globalguerrillas/2004/05/scalefree_terro.html Scale-Free Networks and Terrorism], 2004.
*{{cite journal |doi=10.1002/bies.20294 |author=Keller, E.F. |title=Revisiting "scale-free" networks |journal=BioEssays |volume=27 |issue=10 |pages=1060–8 |year=2005 |url=http://www3.interscience.wiley.com/cgi-bin/abstract/112092785/ABSTRACT |archive-url=https://archive.today/20110813005225/http://www3.interscience.wiley.com/cgi-bin/abstract/112092785/ABSTRACT |url-status=dead |archive-date=2011-08-13 |pmid=16163729}}
*{{cite journal |doi=10.1103/PhysRevE.70.037103 |author=Onody, R.N. |author2=de Castro, P.A. |title=Complex Network Study of Brazilian Soccer Player |journal=Phys. Rev. E |volume=70 |issue=3 |pages=037103 |year=2004 |pmid=15524675 |arxiv=cond-mat/0409609|bibcode = 2004PhRvE..70c7103O |s2cid=31653489 }}
*{{cite journal |author=Kasthurirathna, D. |author2=Piraveenan, M. |title=Complex Network Study of Brazilian Soccer Player |journal=Sci. Rep. | year=2015 |id=In Press}}

{{DEFAULTSORT:Scale-Free Network}}
[[Category:Graph families]]
[[Category:Networks]]