CPSC 327, Spring 2004
Assignment: Random Graphs
Consider the following quote from the book Signs of Life: How Complexity Pervades Biology, by Ricard Solé and Brian Goodwin:
This result is strongly related to the classical Erdös-Renyi theorem on random graphs, where the nodes [vertices] of the graph are randomly wired. In 1959, Erdös and Renyi proved that in a large graph ΓN with N nodes and with E randomly assigned arcs [edges], the probability P(ΓN) of getting a single gigantic component (containing most of the nodes) jumps from zero to one as we increase E/N beyond the critical value 0.5. This surprising result was one of the most celebrated theorems in the theory of random graphs. The Erdös-Renyi result is a very important result for complex networks and so has great relevance for complexity theory.... The ratio of links to nodes is indicated by C. Below the critical value, many nodes remain unconnected. But close to the critical value C = 0.5, a phase transition occurs: suddenly, most of the nodes start belonging to the so-called single gigantic component. This means that percolation occurs in such a way that it is possible to go from almost any node to any other. In other words, the phase transition leads to a sudden shift from a nearly unconnected set to a nearly connected set. If we plot the probability of finding a fully connected set as C is varied, we would see the familiar phase transition plot with a sudden jump at the critical probability.
Your assignment is to investigate this idea experimentally. You should design one or more experiments in which you create random graphs and test whether you "get a single gigantic component (containing most of the nodes)." One approach that I can suggest is to look at a series of values of E/N near 0.5 and look at the size and number of connected components that you get. Although the quote does not mention it, I believe that other things that might be interesting to investigate are how the "suddenness" of the phase transition depends on the size of the graph and the average path length from one node to another in the graphs.
You can work with one other person on this lab, if you want. However, note that I expect work turned in by a team of two people to be suitably more ambitious than work turned in my one person working alone.
This assignment is due in three weeks, on Monday, April 12. (I might give out some additional, less ambitious assignments in the meantime.) You should turn in printouts of your code along with an essay that discusses your procedures and your results. The essay is a formal writing assignment that should be at least several typewritten pages long.
We will discuss this assignment further in class.