Kaushal Kurapati\’s blog

Thoughts on Search, Technology and Management

Structure of graphs and networks – part 3

Posted by kaushalkurapati on May 28, 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 continue here with Granovetter’s strength of weak ties and Watts & Strogatz’ clustered world approach.

Strength of Weak Ties

Mark Granovetter identified a critical element in modeling real world networks, called the strength of weak ties. In this model, we have very close ties to few friends, forming a complete graph — implying all our friends are friends of one another too (strong ties). Some members of our close-friend-circle have acquaintance relationships (weak ties) with others, who in turn have their friend circles. So the entire human network graph is connected that has lumps of close friends /strong ties, who are joined to other lumps with weak ties.

These weak ties are what help us find jobs apparently–at least better than our strong ties. The weak ties lead us to new worlds and new opportunities that we ourselves do not know of or our strongly-tied friends are not aware of. Our close friend circle is presumably aware of similar opportunities as we do…so it is unlikely to open new doors.

Contrast this with the random model of Erdos and Renyi — in that model any two arbitrary nodes are just as likely to be connected as our close friends are! That seems quite unlikely given what we know of our world. Granovetter says that social networks are not random and that our close friends form a near complete graph (strong ties) with a high clustering coefficient and we are tied to acquaintances through weak ties. 

Duncan Watts & Steven Strogatz proposed a model where people are envisioned to live on a circle. We are closed to the nodes next to us and also the ones one step away from the immediate neighbors. This network offers a highly clustered world model–like Granovetter imagined–but is also a large world model. It would take several steps to reach a node that is diametrically opposite to a node on the circle. Watts & Strogatz went on to add few random links between distant nodes on the circle. This suddenly shrunk the distance between diametrically opposite nodes and their next neighbors. Importantly a few such long-distance links are enough to reduce the overall average separation between nodes. This model then accomodates the six-degrees world view as well. Few nodes / people have distant links to people living far-off and thereby become bridges/connectors reducing hopping distance.

According to the book “this [Watts & Strogatz] model offered an elegant compromise between the completely random world of Erdos and Renyi, which is a small world but hostile to circles of friends, and a regular lattice, which displays high clustering but in which nodes are far from each other.”


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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: