BACKGROUND I completed this analysis as a self-directed extension of work on random graph models we performed in Olin's Computational Modeling course. SUMMARY One of the most simple and most fascinating random graph model was first documented by mathematicians Paul Erdos and Alfred Renyi in the 1950s. The Erdos-Renyi random graph model assigns each possible edge in a n-vertex undirected graph a fixed probability p of existence. Each edge's existence is determined independently of its neighbors, though every edge uses the same value of p. With this model, we can tackle a very interesting experiment. First described by Erdos and Renyi in 1960, the experiment tests the connectivity of random Erdos-Renyi graphs over many values of p. Recall that in a connected graph, there exists a path between all possible pairs of vertices. The fascinating conclusion of this experiment observes that there exists some critical value p* such that for p < p* almost all graphs are disconnected and for p > p* almost all graphs are connected. This phenomena is known as a phase change due to the abrupt change in the connectivity property for a small change in the parameter p. In addition to this percolation, the trend between graph size n and the critical point value p* is also notable, and will form the focus of this analysis. We'll tackle this problem in a few ways. First, we implement a simulation to observe the percolation phenomenon firsthand and gain some sense of its dependence on n. Next, we use theoretical analysis to discover a closed-form expression relating graph size to critical point value. In fact, we show that, as n approaches infinity, the critical point approaches p* = ln(n)/n. Finally, we validate our analytical results with more simulation. ACKNOWLEDGMENTS This work is heavily indebted to Gopal Pandurangan, a computer science professor at Purdue, who published an online monograph on this subject. The document is available at http://www.cs.purdue.edu/homes/gopal/CS590A-2007/11.pdf. All errors are my own. |
 | |
|
|
