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 "P"("k") ~ "k"^−"γ" where "γ" is a constant whose value is typically in the range 2<γ<3, although occasionally it may lie outside these bounds.

Scale-free networks are noteworthy because many empirically observed networks appear to be scale-free, including the world wide web, protein networks, citation networks, and some social networks.

Highlights

* Scale-free networks show a power law degree distribution like many real networks.
* The mechanism of preferential attachment has been proposed as a mechanism to explain power law degree distributions in some networks.

History

In studies of the networks of citations between scientific papers, Derek de Solla Price showed in 1965 that the number of links to papers&mdash;i.e., the number of citations they receive&mdash;had a heavy-tailed distribution following a Pareto distribution or power law, and thus that the citation network was 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 Web (Barabási and Albert 1999), 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. Soon after, Amaral et al. showed that most of the real-world networks can be classified into two large categories according to the decay of P(k) for large k.

Barabási and Albert proposed a mechanism to explain the appearance of the power-law distribution, 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.

Although the scientific community is still debating the usefulness of the scale-free term in reference to networks, Li et al. (2005) recently offered a potentially more precise "scale-free metric". Briefly, let "g" be a graph with edge-set ε, and let the degree (number of edges) at a vertex "i" be $d\_i$. Define

: $s(g)\; =\; sum\_\{(i,j)\; in\; epsilon\}d\_i\; d\_j.$

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

$S(g)\; =\; frac\{s(g)\}\{s\_\{max$

where "s"_max is the maximum value of "s"("h") for "h" in the set of all graphs with an identical degree distribution to "g". This gives a metric between 0 and 1, such that graphs with low "S"("g") are "scale-rich", and graphs with "S"("g") close to 1 are "scale-free". This definition captures the notion of self-similarity implied in the name "scale-free".

Characteristics and examples

As with all systems characterized by a power law distribution, 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.

The power law distribution highly influences the network topology. It turns out that the major hubs are closely followed by smaller ones. These ones, in turn, are followed by other nodes with an even smaller degree and so on. This hierarchy allows for a fault tolerant behavior. Since failures occur at random and the vast majority of nodes are those with small degree, the likelihood that a hub would be affected is almost negligible. Even if such event occurs, the network will not lose its connectedness, which is guaranteed by the remaining hubs. On the other hand, if we choose a few major hubs and take them out of the network, it simply falls apart and is turned into a set of rather isolated graphs. Thus hubs are both the strength of scale-free networks and their Achilles' heel.

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. That means 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 so related to other people (e.g., celebrities, politicians) that they are connected to a large number of communities. Those people may be considered the hubs responsible for the small world phenomenon.

At present, the more specific characteristics of scale-free networks can only be discussed in either the context of the generative mechanism used to create them, or the context of a particular real-world network thought to be scale-free. 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. Many interesting results are known for this subclass of scale-free networks. For instance, 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 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; notably, the structure of the Internet is more like this latter kind of network than the kind built by preferential attachment. Indeed, many of the results about scale-free networks have been claimed to apply to the Internet, but are disputed by Internet researchers and engineers.

As with most disordered networks, such as the small world network model, the average distance between two vertices in the network is very small relative to a highly ordered network such as a lattice. The clustering coefficient of scale-free networks can vary significantly depending on other topological details, and there are now generative mechanisms that allow one to create such networks that have a high density of triangles.

It is interesting that Cohen and Havlin proved that uncorrelated power-law graph having 2 < γ < 3 will also have ultrasmall diameter "d" ~ ln ln "N". So from the practical point of view, the diameter of a growing scale-free network might be considered almost constant.

Although many real-world networks are thought to be scale-free, the evidence remains inconclusive, primarily because the generative mechanisms proposed have not been rigorously validated against the real-world data. As such, it is too early to rule out alternative hypotheses. A few examples of networks claimed to be scale-free include:

*Social networks, including collaboration networks. An example that has been studied extensively is the collaboration of movie actors in films.
*Protein-Protein interaction networks.
*Sexual partners in humans, which affects the dispersal of sexually transmitted diseases.
*Many kinds of computer networks, including the World Wide Web.
* Semantic networks. [ cite journal|title=The Large-Scale Structure of Semantic Networks: Statistical Analyses and a Model of Semantic Growth|journal=Cognitive Science|date=2005|first=Mark|last=Steyvers|coauthors=Joshua B. Tenenbaum|volume=29|issue=1|pages=41–78|doi= 10.1207/s15516709cog2901_3|url=http://www.leaonline.com/doi/abs/10.1207/s15516709cog2901_3|format=]

Generative models

These scale-free networks do not arise by chance alone. 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 graphs are not consistent with the properties observed in scale-free networks, and therefore a model for this growth process is needed.

The scale-free properties of the Web have been studied, and its distribution of links is very close to a power law, because there are a few Web sites with huge numbers of links, whichbenefit from a good placement in search engines and an established presenceon the Web. Those sites are the ones that attract more of the new links. This has been called the winner takes all phenomenon.

The mostly 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, butproportional to the current in-degree of Web pages. This model was originally discovered by Derek J. de Solla Price in 1965 under the term cumulative advantage, but did not reach popularity until Barabási rediscovered the results under its current name (BA Model). According to this process, a page with many in-links will attract more in-links than aregular page. This generates a power-law but the resulting graph differsfrom the actual Web graph in other properties such as the presence of smalltightly connected communities. More general models and networks characteristics have been proposed and studied (for a review see the book by Dorogovtsev and Mendes).

A different generative model is the copy model studied by Kumar et al. (2000),in which new nodes choose an existent node at random and copy a fraction of the links of the existent node. This alsogenerates a power law.

However, if we look at communities of interests in a specific topic, discarding the major hubs of the Web, the distribution of links is no longer a power law but resembles more a normal distribution, as observed by Pennock et al. (2002) in the communities of the home pages of universities, public companies, newspapers and scientists. Based on these observations, they propose a generative model that mixes preferential attachment with a baseline probability of gaining a link.

The growth of the networks (adding new nodes) is not a necessary condition for creating a scale-free topology. Dangalchev (2004) gives examples of generating static scale-free networks. Another 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 vertices properties (fitnesses), it turns out that in some circumstances also static networks develop scale-free properties. Recently, Manev and Manev (Med. Hypotheses, 2005) proposed that small world networks may be operative in adult brain neurogenesis. Adult neurogenesis has been observed in mammalian brains, including those of humans, but a question remains: how do new neurons become functional in the adult brain? It is proposed that the random addition of only a few new neurons functions as a maintenance system for the brain's "small-world" networks. Randomly added to an orderly network, new links enhance signal propagation speed and synchronizability. Newly generated neurons are ideally suited to become such links: they are immature, form more new connections compared to mature ones, and their number but not their precise location may be maintained by continuous proliferation and dying off. Similarly, it is envisaged that the treatment of brain pathologies by cell transplantation would also create new random links in small-world networks and that even a small number of successfully incorporated new neurons may be functionally important.

See also

* Social-circles network model - a more generalized generative model for many "real-world networks" of which the scale-free network is a special case
* Random graph
*

References

* Albert R. and Barabási A.-L., [http://www.nd.edu/~networks/Publication%20Categories/publications.htm#anchor-allpub0001 "Statistical mechanics of complex networks"] , Rev. Mod. Phys. 74, 47–97 (2002).
* Amaral, LAN, Scala, A., Barthelemy, M., Stanley, HE., [http://arxiv.org/abs/cond-mat/0001458 "Classes of behavior of small-world networks"] . Proceedings of the National Academy of Sciences (USA) 97:11149-11152 (2000).
* Barabási, Albert-László "Linked: How Everything is Connected to Everything Else", 2004 ISBN 0-452-28439-2
* Barabási, Albert-László [http://www.nd.edu/~networks/Publication%20Categories/01%20Review%20Articles/ScaleFree_Scientific%20Ameri%20288,%2060-69%20(2003).pdf "Scale-Free Networks"] . "Scientific American", 288:60-69, May 2003.
* Barabási, Albert-László and Albert, Réka. [http://arxiv.org/abs/cond-mat/9910332 "Emergence of scaling in random networks"] . "Science", 286:509-512, October 15, 1999.
*Dan Braha and Yaneer Bar-Yam, " [http://necsi.org/affiliates/braha/Topology--of--Large--Scale--Design--PRE69.pdf Topology of Large-Scale Engineering Problem-Solving Networks] " Phys. Rev. E 69, 016113 (2004)
* Caldarelli G. " [http://www.oup.com/us/catalog/general/subject/Physics/Mathematicalphysics/~~/dmlldz11c2EmY2k9OTc4MDE5OTIxMTUxNw= Scale-Free Networks"] Oxford University Press, Oxford (2007).
* Caldarelli G., Capocci A., De Los Rios P., Muñoz M.A., [http://arxiv.org/abs/cond-mat/0207366 "Scale-free networks from varying vertex intrinsic fitness"] Physical Review Letters 89, 258702 (2002).
* Dangalchev, Ch., "Generation models for scale-free networks", Physica A, 338,(2004)
* Dorogovtsev, S.N. and Mendes, J.F.F., "Evolution of Networks: from biological networks to the Internet and WWW", Oxford University Press, 2003, ISBN 0-19-851590-1
* Dorogovtsev, S.N. and Mendes, J.F.F. and Samukhin, A.N., "Structure of Growing Networks: Exact Solution of the Barabási--Albert's Model", Phys. Rev. Lett. 85, 4633 (2000)
* Dorogovtsev, S.N. and Mendes, J.F.F., Evolution of networks, Advances in Physics 51, 1079-1187 (2002)
* Erdős, P. and Rényi, A. "Random graphs". Publication of the Mathematical Institute of the Hungarian Academy of Science, 5, pages 17-61, 1960.
* Faloutsos, M., Faloutsos, P. and Faloutsos, C., "On power-law relationships of the internet topology" Comp. Comm. rev. 29, 251, 1999.
* Li, L., Alderson, D., Tanaka, R., Doyle, J.C., Willinger, W., [http://arxiv.org/abs/cond-mat/0501169 Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version)] . Internet Mathematics, 2005.
* Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., and Upfal, E.: [http://www.cs.brown.edu/research/webagent/focs-2000.pdf Stochastic models for the web graph] . In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), pages 57-65, Redondo Beach, CA, USA. IEEE CS Press, 2000.
* Manev R., Manev H.; Med. Hypotheses 2005;64(1):114-7 [http://www.ncbi.nlm.nih.gov/entrez/query.fcgi?cmd=Retrieve&db=pubmed&dopt=Abstract&list_uids=15533625&query_hl=26]
* Matlis, Jan. [http://www.computerworld.com/networkingtopics/networking/story/0,10801,75539,00.html Scale-Free Networks] . ComputerWorld. November 4, 2002.
* Newman, Mark E. J. [http://arxiv.org/abs/cond-mat/0303516 The structure and function of complex networks] , 2003.
*Pastor-Satorras, R.,Vespignani, A.,"Evolution and Structure of the Internet: A Statistical Physics Approach",Cambridge University Press, 2004, ISBN 0521826985
* Pennock, D. M., Flake, G. W., Lawrence, S., Glover, E. J., and Giles, C. L.: [http://www.modelingtheweb.com/ Winners don't take all: Characterizing the competition for links on the web] . Proceedings of the National Academy of Sciences, 99(8):5207-5211, 2002.
* Robb, John. [http://globalguerrillas.typepad.com/globalguerrillas/2004/05/scalefree_terro.html Scale-Free Networks and Terrorism] , 2004.
*Keller, E.F. [http://www3.interscience.wiley.com/cgi-bin/abstract/112092785/ABSTRACT Revisiting "scale-free" networks] , BioEssays 27(10) 1060-1068, 2005.
*R. N. Onody and P. A. de Castro, " [http://xxx.lanl.gov/abs/cond-mat/0409609 Complex Network Study of Brazilian Soccer Player] ", Phys. Rev. E 70, 037103 (2004)
*Reuven Cohen, Shlomo Havlin, " [http://arxiv.org/abs/cond-mat/0205476 Scale-Free Networks are Ultrasmall] " Phys. Rev. Lett. 90, 058701 (2003)