Kaushal Kurapati\’s blog

Thoughts on Search, Technology and Management

Structure of Graphs and Networks – part 1

Posted by kaushalkurapati on May 28, 2007

I have been reading “LINKED” by Albert-Laszlo Barabasi. Through a series of blog posts I will summarize my understandings of the various concepts regarding the structure of graphs and networks.

Random Network model

Paul Erdos and Alfred Renyi, both great mathematicians, assumed that complex networks are essentially random. Start with a large set of unconnected nodes and begin adding links randomly between nodes. After a while, most of the nodes will be connected and each node will approximately have the same number of links. There may be some outliers–far more links than most or far fewer links than most–but in general most of the nodes will end up with approximately same number of links. This is like a Poisson distribution.

Imagine a cocktail party with a large number of guests. You incentivize your guests to pass on a secret by introducing it to a node or few nodes. The guests have to make acquaintances to pass on the message. Will the message reach everyone? Almost all is the answer. If you plot a histogram of how many of the guests had 1, 2, …N acquaintances, the distribution will turn out to be Poisson! This is as per the random network model of Erdos and Renyi. A majority of the guests would have made the same # of acquaintances and on either sides of the peak the distribution diminishes rapidly indicating that extreme variations are very rare.

It is worthwhile to note that Erdos and Renyi did not intend to model real-world phenomenon like web-page distributions, cell-phone distributions, etc., with their random network model. They were purely interested in the mechanics of graphs.

To summarize the random network model then, it states that the average is the norm. Most people have same number of acquaintances and very few people know tons of others and very few people are compleltely isolated. This model does not answer how real world networks indeed look like. Other models were derived to explain that.


2 Responses to “Structure of Graphs and Networks – part 1”

  1. […] 28th, 2007 We looked at Random network model in Part 1  of this […]

  2. […] 28th, 2007 Part 1 of this series looked at Erdos and Renyi’s Random model of networks. Part 2 of the series looked at Six degrees of separation as per Milgram’s experiment. We […]

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: