Scale-free Networks
"Ecologists believe that the hubs of food webs are the keystone species of an ecosystem, paramount in maintaining the ecosystem's stability"
-- Albert and Barabasi Linked

Good News !!

You are viewing a draft of the book entitled "Patterns – The Art, Soul, and Science of Beholding Nature". The final version of this book has now being published as an Amazon Kindle eBook.

There are some significant changes in the eBook that are not in this draft. You may purchase the eBook here

Some of the ideas in the eBook are contained in posts at my Patterns In Nature Blog. You are encouraged to visit this blog site. If you press the "Like" button shown below, your Facebook page will provide you with short notifications and summaries of new blog posts as they become available.

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.

Useful References


Table Of Contents