A highly connected network model was studied by Barabasi and Albert-Laszlo. It  became known as the "scale-free" network. Compared to a random network, the scale-free network has a very different kind of connectivity because the degree distribution is defined by a power law distribution instead of the Poisson distribution associated with the random network. In a power law distribution, most nodes have relatively few links but a few nodes (called hubs) have a high number of links.  The contribution of the hubs to the overall connectivity is very high. The connectivity contribution of the nodes with fewer links is much lower. This model corresponds to the Internet in which most web pages have only a few links connecting to them, but sites like Google and Yahoo have a very large number of hyperlinks pointing to them.

Scale-free networks are noteworthy because the world wide web, protein networks, citation networks, some social networks, and other network types appear to be scale-free.

The figure on the left shows a graphic interpretation of a section of the Internet. Notice the lower number of highly clustered nodes (hubs) containing many links and the high number of nodes with few links.

Scale-free networks feature link clustering around certain hubs based on preferential attachments that emerge due either to merit or legacy. For example, biological systems ranging from sub-atomic to ecosystems represent scale-free networks in which energy efficiency forms the basis of preferential attachments.

Clustered small world network architectures like the Watts-Strogatz model can also be described as scale-free with the characteristic power law distribution of links. According to Strogatz: "disparate networks show the same three tendencies: short chains, high clustering, and scale-free link distributions…. The challenge now is to decode the underlying meaning of small-world and scale-free architecture".

Many natural networks are well approximated by scale-free network models. Why the naturally occurring complex systems tend to self organize themselves into scale-free networks is not clear at present, but the power law connectivity distribution appears to emerge as one of the important phenomena of patterns in nature. It has been suggested that the scale-free organizational structure of natural complex systems is responsible for a number of common emergent properties that are shared by different complex systems.

There are features that the scale-free network contains that are lacking in the random network.

• In a scale free network, a small number of nodes contribute heavily to connectivity.  These nodes are called hubs. In a random network, each node contributes approximately the same to the overall connectivity of the network.
• In a scale free network, any two arbitrarily chosen nodes, even in a very large network, can be connected via few other intermediary nodes.
• A power law has a characteristic (constant) exponent which is sometimes called a dimension. No matter what size (magnification ) the network, the dimension stays the same. Thus the term "scale-free".
• Scale-free networks are "self similar". Any part of the network is statistically similar to the whole network. Self similarity is the key feature of fractals.
• A  scale-free network is "robust". It can still operate with a random removal of a few nodes. But, the failure of a hub can fragment the system into a number of smaller islands, causing connectivity failure.
• Scale-free networks tend to promote high speed transfer of information or energy. Their hubs have a combination of high global connectivity with highly developed local clustering. Consequently, there is a rapid synchronization of distant nodes.

You are invited to explore more detail by looking at regular networks, random networks, and small world networks.

This document is a draft of work in progress. Please post your comments, thoughts, and suggestions:

Comments powered by Website Comments System ® v1.0