22C:21: Computer Science II: Data Structures

Project 2 Notes. Started on 4/23

  1. 4/23: I started by implementing the greedy routing algorithm (for Experiment 3). I tested and timed this implementation and here are some results:

  2. 4/23: I implemented degreeDistribution and here are the degree distributions of 10 small world graphs (as in Project 1). I chose n = 10,000, d = 50, and p = 0.1. For each graph, there are two lines of output. The first line contains minimum degree, maximum degree, and average degree whereas the second line contains the degree distribution itself. Here is a plot that shows the first three degree distributions; these are virtually identical and all have the "bell shaped" binomial distribution that classical random graphs have.

  3. 4/23: To perform Experiment 1, I generated small world graphs with n = 10,000, p = 0.1, and d varying from 40 to 45 (in increments of one). The output is here. The average degrees varied from 19.1696 for d = 40 to 15.1292 for d = 45. The 6 plots are here. Note that the experiments were done with p = 0.1 because for this value of p the graphs in Project 1 have high clustering coefficient and small average path length. So with p = 0.1, we have these two properties of small world networks and we want to check if the third property also holds.

  4. 4/24: I ran some timing tests to get a sense of how long Experiment 3 might take. I generated a small world graph with n = 10,000, d = 45, and p = 0.1. I generated one million st-pairs and ran greedy as well as breadth-first search. Here is the output from two runs and it shows that each run takes about 1 minute and 50 seconds. Assuming that Dijkstra's shortest path algorithm takes just a bit more time than breadth-first search, one run of Experiment 3 would complete in about 5 minutes on my machine. Assuming that different runs take the same amount of time, it seems like 250 runs (5 values of p, 5 values of D, 10 graphs) would complete in about 21 hours. Since we have the run the experiment on the preferential attachment graph as well, I would estimate about 2 days of running time.

    You might consider a pared down version of the experiment in which you use 3 values of p, 3 values of D, and 5 different graphs to average over. This is 45 runs for each model and therefore a total of 90 runs. Assuming, 5 minutes per run means that the pared down version of Experiment 3 will complete in 8-9 hours.