Scale-free network

A scale-free network is a specific kind of complex network that has attracted attention since many real-world networks fall into this category. In scale-free networks, some nodes act as "highly connected hubs" (high degree), although most nodes are of low degree.

History

Using a Web crawler, physicist Albert-Laszlo Barabasi and his colleagues at the University of Notre Dame in Indiana in 1999 mapped the connectedness of the Web. To their surprise, the web did not have an even distribution of connectivity (so-called "random connectivity"). Instead, a very few network nodes (called "hubs") were far more connected than other nodes. In general, they found that the probability P(k) that a node in the network connects with k other nodes was, in a given network, proportional to k^−γ. At same time a similar observation was obtained to the Internet by the broders Faloutsos (1999). In this form, essentially all graphs with a power law degree distribution were grouped together as "scale-free". Several revisions of this definition have been suggested. (see below)

Characteristics and examples

Random network (a) and scale-free network (b). In the scale-free network, the larger hubs are highlighted.

Scale-free networks tend to contain centrally located, highly connected "hubs", which dramatically influences the way a network operates. For example, random node failures have very little effect on a scale-free network's connectivity or effectiveness, however deliberate attacks on such a network's hubs can dismantle a network with alarming ease. Thus, the realization that certain networks are scale-free is important to security.

These networks also exhibit the Small world phenomenon, in which two average nodes are separated by a very small number of connections. Also, scale-free networks generally have high clustering coefficients.

A multitude of real-world networks have been shown to be scale-free, including:

• Social networks, including collaboration networks. An example that have been studied extensively is the collaboration of movie actors in films.
• 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.

Generative models

These scale-free networks do not arise by chance alone. Erdös and Renyi (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, which benefit from a good placement in search engines and an established presence on the Web. Those sites are the ones that attract more of the new links. This has been called the winners take all phenomenon.

Barabasi and Albert (1999) propose a rich get richer generative model in which each new Web page creates link to existent Web pages with a probability distribution with 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 that 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 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 also generates 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, the authors propose a generative model that mixes preferential attachment with a baseline probability of gaining a link.

References

• Alberich, R., J. Miro-Julia, and F. Rossello. "Marvel Universe looks almost like a real social network".
• Barabasi, Albert-Laszlo Linked: How Everything is Connected to Everything Else, 2004 ISBN 0452284392
• Barabasi, Albert-Laszlo and Reka, Albert. "Emergence of scaling in random networks". Science, 286:509-512, October 15, 1999.
• Dorogovtsev, S.N. and Mendes, J.F.F., Evolution of Networks: from biological networks to the Internet and WWW, Oxford University Press, 2003, ISBN 0198515901
• Erdos, P. and Renyi, 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 topologyComp. Comm. rev. 29, 251, 1999.
• Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., and Upfal, E.: 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.
• Li, Lun et al. Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version)
• Matlis, Jan. Scale-Free Networks. ComputerWorld. November 4, 2002.
• Newman, Mark E. J. The structure and function of complex networks, 2003.
• Pennock, D. M., Flake, G. W., Lawrence, S., Glover, E. J., and Giles, C. L.: 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. Scale-Free Networks and Terrorism, 2004.