Giant Component Emergence in Erdös-Rényi graphs

I was hoping to discuss the notion of “small-world” networks, but we ended up spending most our time  discussing a couple of sentences from the “The Random Universe” (Chapter 2) in Barabási’s book. The sentences in question (bottom of Page 17) are:

But when you add enough links such that each node has an average of one link, a miracle happens: A unique giant cluster emerges.

We tried an activity in class to make this idea concrete. Notice that for an n-node Erdös-Rényi graph to have expected degree 1, p would have to be 1/(n-1). I asked each of you to build a 9-node Erdös-Rényi graph with p = 1/8. To simulate the random process of adding edges, you would need an 8-sided die and since I did not have any handy, I gave each of you a pre-generated sequence of 36 rolls of an 8-sided die. Why 36? This is because a 9-node graph has 9*8/2 = 36 distinct node-pairs. Here are the sequences I passed around and here is the Python program that I used to generate these sequences.

After completing this activity, students answered three questions:

  1. Is your graph connected?
  2. How many connected components does it have?
  3. What are the sizes of the connected components?

I polled a few (4) students and here are their answers:

  • No; 3; 6, 2, 1
  • No; 3; 7, 1, 1
  • No; 4; 5, 2, 1, 1
  • No; 4; 5, 2, 1, 1

Even with small values of n we start getting a glimpse of the “miracle” that Barabási is alluding to. In fact, with p fixed at 1/(n-1), as n grows, the “miracle” becomes more clearly visible as the graph essentially consists of one “giant” connected component along with a small number of tiny components.

Homework (due: 9/11)
Netlogo is a library of models from a variety of disciplines. I noticed that they had a model called Giant Component that turned out to be just what we were discussing in class this past Tuesday. Your homework for next Tuesday (9/11) is basically to play with the Giant Component model and report on your exploration.

Here is how you get started:

  • Follow the Giant Component link and then click on “Run Giant Component in your browser.”
  • Adjust the slider on “num-nodes” to a number you want
  • Click on “setup” and then click on “go” or “go once”
  • You can click on “setup” to restart the process

Your machine needs Java for the model to work in your browser. If you don’t have it, you can download Java here.

Play with the model until you understand all the controls and the answer the following questions:

  1. For number of nodes equal to (about) 250, what is the size of the giant component when the connections per node is (about) 1?
  2. For number of nodes equal to (about) 250, what does the number of connections per node have to become for the giant component to get to 90% of the network?

Since these are random experiments, the answers will vary from attempt to attempt. To make sure that your answers are “robust,” do the experiment 10 times and report the means and medians.

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