Scale-Free Networks
in an egalitarian, random network most people will have about the same number of links. In a scale free network, governed by Power Laws, a few nodes account for the vast majority of connections.
- Jonas Andersen [1]
Definition
"a network that is scale-free will have the same properties no matter what the number of its nodes is. Their defining characteristic is that their degree distribution follows the Power Law relationship"
From the Wikipedia at http://en.wikipedia.org/wiki/Scale-free_network
Description
From Andi Balik [2]:
"The most interesting kind of networks, and those which have received the most attention and publicity recently, are known as scale-free. In this type of network, there is an inverse relationship between the number of links per node, and the number of nodes with this many links. That is, most nodes have very few links, and the more links a node has, the more uncommon it is. So when one plots the number of links per node against the number of nodes, one gets an exponential curve (Fig. 4B), or a straight line on a logarithmic scale. This kind of relationship is also called a Power Law distribution, and is a characteristic feature of scale-free networks." (http://www.geocities.com/andybalik/network.html)
Sam Rose:
Quoted from wikipedia http://en.wikipedia.org/wiki/Scale-free_networks
"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"
The mechanism of Wikipedia:Preferential_attachment is theorized to be a factor explaining Power law distribution of resources, attention, wealth, etc in some networks.
As a "p2p metric", the method for analyzing network and determining if it is "scale free" creates a data profile about the network that informs about the nature of the network.
Examples
"Scale-free networks have now been shown to exist very widely in both the natural world and in human societies. In the cell, examples include metabolic networks, in which each kind of molecule is linked to other molecules by enzymatic reactions (Jeong et al. 2000); and protein networks, in which protein molecules are linked to each other by physical interactions (Jeong et al. 2001; Wuchty 2001)). It seems likely that some kinds of tissues, particularly the nervous system, also exhibit scale-free organization, though so far the complexity of these tissues has not made it possible to test this hypothesis.6
In human societies, scale-free networks include many kinds of social relationships between people, including networks of acquaintances, business contacts, and sexual partners (Barabasi 2002). It even turns out that if one "links" movie actors who have appeared in at least one film together, one also gets a scale-free network! Other examples include the scientific literature, in which individual articles or papers are the nodes, linked to each other by citations (Bilke and Petersen 2001); and human language itself, in which words are nodes, linked by relationships such as similar meanings or associations in speech and text (Ferrer et al. 2001). Scale-free organization has also been reported for electrical power grids. where power sources are linked by lines to various consumer areas, and airline routes, which link cities to other cities.
The best known and most intensively studied scale-free networks, however, are the internet--the physical structure of servers and individual computers linked by phone lines all over the globe--and the world wide web, the documents or pages of information accessible through the internet. Because of the enormous number of nodes and links involved, particularly in the world wide web, and because this information can be accessed in a straightforward and systematic manner, a seemingly unending amount of data on the internet's organization has accumulated, and has been subjected to rigorous statistical analysis. Much of what is known about scale-free organization has come from this work." (http://www.geocities.com/andybalik/network.html)
Characteristics
"What are some of the distinguishing features of scale-free networks? As I pointed out earlier, this class of networks is characterized by a few relatively highly linked or well-connected nodes, and a great many others with few links. One important implication of this organization is that such networks are highly resistant to random perturbations. Elimination of a few randomly chosen nodes will usually have little effect on the overall structure and function of the network, because the probability is that these nodes will have few links, and not be critical to the overall organization. This aspect of scale-free networks is thought to account for the fact that the internet and the world wide web as a whole have proven quite resistant to random breakdowns. That is, when individual servers go down, the problem is generally confined to a small region of the web or the internet. The same property may contribute to the resistance of cells to chemical or biological insults, or to mutations; a loss or deficiency of one type of molecule in the metabolic network is unlikely to have serious repercussions for the rest of the network.
On the other hand, scale-free organization turns out to be much more vulnerable than a random or ordered network to a selected perturbation. If one or more of the highly connected nodes--commonly called a hub--is eliminated or compromised, this will have potentially enormous repercussions on the entire network, because so many other nodes depend on these hubs for their connection to everyone else. Alberto-Laslo Barabasi, one of the leading investigators of scale-free networks, has suggested that the Asian financial crisis in 1997, which was triggered by a relatively common failure of a bank to meet certain debts, might have reflected weakening of a critical hub in the financial network. The same principle underlies the potential vulnerability of sources of information, energy or wealth in America to a terrorist attack. And again, if we consider scale-free networks within cells, a biological agent--such as a virus or bacterium--that is adapted to disrupting a key node within the network may have a lethal effect on the cell.
Another signal feature of scale-free networks is that they have relatively small diameters, that is, average distances between nodes. This discovery was actually presaged three decades ago, long before the appreciation of scale-free properties, by the psychologist Stanley Milgram. Milgram claimed that virtually every person in America was no more than six links removed from every other person (Milgram 1967). That is to say, if we select any person at random, he or she knows people who know other people who know others, and so on, who will lead, in no more than six steps, to any other person. This has become famous as "six degrees of separation". While the number may not be as small as six, it is a very small number, and is now believed to apply not just to people in America, but to everyone on the planet.
With more than six billion people on earth, many of them living in areas remote from the rest of civilization, this claim may seem preposterous. The key, however, is again found in the well-connected nodes or hubs. Most people are fairly closely linked to one of these hubs; that is, they know a very well-connected person, or know someone who does, or know someone who knows someone who does. One of this well-connected individual's acquaintances, in turn, will know someone who knows someone who knows...and quickly to any other person. In other words, the few highly linked nodes, well-connected individuals, act as bridges that facilitate contacts between less connected individuals. Because of this property, scale-free networks are also often referred to as small world networks. No node in such a network is very far removed from any other node." (http://www.geocities.com/andybalik/network.html)
Discussions
Conditions for Scale-Free Networks
"Studies by Barabasi and his colleagues have found that two key factors or conditions are required in a group of interacting nodes in order for them to form a scale-free network (Barabasi and Reka 1999). First, the group must be growing, constantly adding new members. This of course is an obvious feature of human societies, as well as of most artifacts produced by these societies. One could not have a better example than the internet. This property is also a feature of molecular networks within cells, if we take an evolutionary perspective, and recognize that such networks did not emerge full-blown, but rather were created through a gradual accumulation of new molecular partners. The earliest such networks, perhaps found in enclosed structures that resembled cells in some respects, probably contained a relatively few such substances. Over time, the number increased, as new enzymatic reactions made it possible for new metabolites to be increased. As Stuart Kauffman (1993) has shown, as the number of substances increases, so does the probability that one substance will be capable of catalyzing the formation of another substance. Once this occurs, links between substances can be formed.
A second critical feature of scale-free organization is that new nodes must preferentially link up to other nodes that already have a high number of links; that is, the more links a node has, the higher the probability that it will get still more. This phenomenon is often referred to as "the rich get richer", and indeed, the distribution of wealth in America and most other societies also follows a scale-free organization (Buchanan 2001). That is, rather than there being a Gaussian distribution of wealth, with most people clustered about a mean, there is an inverse or Power Law relationship between any degree of wealth and the number of people who have attained it." (http://www.geocities.com/andybalik/network.html)
Scale-Free Networks, the Long Tail, and the Power Law
Ross Dawson:
"The familiar shape of the long tail is a “power law” distribution, based on an exponential function. The most fundamental aspect of a power law curve is “scale invariance,” meaning that it has the same shape, whatever its scale.
Indeed, it has been proven that for a network to have a classic long tail power law distribution, it needs to be a “scale-free” network. To be a scale-free network, its nodes must be able to have any number of network connections, from none to essentially infinite. If it is bounded on the upside, then as the networks scales upwards in size, its shape will change as the top end of it becomes limited.
Some networks are not scale-free. For example personal networks are not, because there is a limit to the number of people we can know. Airline networks are limited by the size of airports and physical constraints.
However digital networks, epitomized by the Internet, are scale-free, because there is no limit to the number of connections that nodes (webpages) can have. Media has become effectively a scale-free network, not so much because the top end is unbounded, as because production and distribution costs have become negligible and now many nodes (media producers) have very few connections (audience)" (http://www.rossdawsonblog.com/weblog/archives/2007/12/the_long_tail_i.html)