The Watts-Strogatz Model

This is a much delayed post on our meeting from September 25th.

We examined the Watts-Strogatz random graph model in detail, based on its description in this paper. The Watts-Strogatz model starts with nodes distributed evenly on a circle (Question: is it important that the nodes be on a circle? Could other geometric configurations also work?). For some positive integer parameter k, each node is connected to k nearest neighbors on either side. This yields a network with high clustering coefficient (Why?), but also high diameter and average path length. Then, with some probability p each original edge e is “rewired.” Note that in the initial network, each edge connects pairs of nodes that are relatively close to each other on the circle. The process of “rewiring” deletes an edge and replaces it with one having randomly chosen endpoints. When p is small only a few edges are “rewired” and when p is close to 1, most edges are “rewired.” The main point of the Watts-Strogatz paper is that using a very small p does not disturb the clustering coefficient very much and the clustering coefficient continues to stay high. However, rewiring even a small number of edges causes the diameter and average path length to dramatically fall. Thus by using a small p, we have constructed a random network with high clustering coefficient and small average path length.

Homework: Due Oct 16th.

1. Here is a “demo” of the Watts-Strogatz model from Netlogo. Play with this and answer the following questions (bring your answers to class).

  • Set the number of nodes to the maximum possible (i.e., 300). What is the clustering coefficient and average-path-length for the network with 300 nodes before you do any rewiring?
  • Using what you know about the definition of clustering coefficient, explain the value of the clustering coefficient you see.
  • Try “rewiring” the network with probabilities p = 0.05 and 0.1. Report the clustering coefficient and average-path-length for these rewiring probabilities.

2. In 1-2 paragraphs, explain whether you think the Watts-Strogatz model is appropriate for real-world networks. In what ways does this model capture key aspects of how networks form and in what ways does it fail to do so? Do  you think the Watts-Strogatz model is appropriate for the network consisting of you and your “friends” on Facebook?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

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