Scale Free Networks

Essential knowledge:

• A Scale Free Network is one in which the distribution of links to nodes follows a power law. The power law means that the vast majority of nodes have very few connections, while a few important nodes (we call them Hubs) have a huge number of connections.

• On the Web you can see that major websites like the BBC or Facebook are hubs, they dominate the network, while there are millions of smaller websites with very few connections.

You may be interested that:

A scale free network is simply a network whose degree distribution follows a power law. It is one of the most encountered network types in the real world.

In 1965, Price studied the network of citations in scientific papers and he showed that new papers tend to cite papers with large number of citations already; he called that phenomenon cumulative advantage (preferential attachment), you may know it as ‘The Rich Get Richer’ . Therefore, he found out that the number of citations a paper has follows a power law distribution.

In 1999 Albert-László Barabási mapped the network of a portion of the World Wide Web (WWW). The analysis of that network had led to some interesting findings:

1. There are a number of nodes (hubs) that have more connections than others.

2. The WWW network has a power law distribution of the number of links connected to Web pages.

From the above we can conclude that scale free networks have the following key features:

1. A number of nodes with high degree known as hubs, they appear as a result of preferential attachment.

2. The degree distribution follows a power law.

3. Hubs usually have links from all around the network, serving as links between different parts of the network, therefore showing a small world property.

Are there hubs in your own social networks? What do you think are the reasons that these hubs appear in a given network?

If you’re really curious:

To better understand scale free networks, it will be useful to discuss how we could generate the power law distribution. To create a network with a power law distribution we can use the following rules:

1. The network expands over time as new nodes are added to the network.

2. When a node is added to the network it will be connected to older nodes using the principle of preferential attachment, in which nodes that have a high degree are more likely to attract new nodes than nodes with a low degree.

Optional further reading

1. Albert, A and Barabási, AL (2002) ‘Statistical mechanics of complex networks’, Reviews of Modern Physics, vol.74, pp. 47–97

2. Barabási, AL and Albert, R (1999) ‘Emergence of scaling in random networks’, Science, vol. 286, no. 5439, pp. 509–512. October