Kaushal Kurapati\’s blog

Thoughts on Search, Technology and Management

Structure of graphs and networks – part 4: scale-free networks

Posted by kaushalkurapati on June 23, 2007

Till now we have seen (part1, part 2, part 3) that random networks can typically be captured by a bell curve. Many nodes have similar ‘scale’ and there is a characteristic peak. Few nodes in the network have many links or few links. In contrast, Barabasi’s group discovered that certain networks do not show peaks and there is no characteristic node or scale in the network. His group started to describe such networks as “scale-free”. They are represented mathematically in terms of a power-law. Most nodes have few links and the network is held together by a few highly connected ‘hubs’. To quote from the book,

The random network theory of Erdos and Renyi and its cluster-friendly extension by Watts and Strogatz both insisted that the number of nodes with k links should decreases exponentially–a much faster decay than that predicted by a power law. They both told us, in rigorous mathematical terms, that hubs do not exist.

Networks before the proposal of scale-free model by Barabasi’s group were modeled as static and randomly connected, which even though could model a small world, did not model the Web or spread of AIDS or computer viruses, etc. Real world networks grow, and there is preferential attachment (rich get richer). Incorporating these two conditions into a network model helps capture the scale-free model represented by the Web, for instance.

Scale-free networks can also be small-world, just like the random + clustered model proposed by Watts & Strogatz; meaning in few hops one can get from any node to another node. The difference in these networks comes in how they break down and how information spreads through these networks. In random networks, taking many nodes out won’t affect reachability in most of the network until a large % of the network nodes are removed. In scale-free networks as well, if nodes are removed randomly then the network holds up, which is great news for the stability of a network like the Internet. However, if key hubs are removed in the scale-free network, you will immediately have islands in the network thereby crippling reachability across the network. Consider the spread of information or virus or a disease: if the web of intimate links in a human society were to be random, something like AIDS may not have spread like it did. Unfortunately, that intimate links graph apparently is a scale-free hubs-type network and so once a hub gets a disease, it spreads rapidly to many-many links in the network. The silver lining here could be that curing only the hubs, which may be cost effective, can drastically reduce the spread of the disease. If it were a random network, we would have to cure all nodes in the network to stop the spread of a disease in the network. The challenge I would think is figuring out who the hubs are, especially in a disease-spread scenario. In the case of computers, it is relatively easy to figure that out given there is lot of knowledge about the network.

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: