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:
• Here is the output from 10 runs. In each run, I generated a small world graph (as in Project 1) with n = 10,000 on a 50 by 50 square with p = 0.1 and chose 1000 st-pairs chosen uniformly at random. The success rate of the greedy algorithm is around 91% and the average number of hops and the average Euclidean distance traveled by the message is around 14 and 44 respectively. It is remarkable how the average number of hops and the average Euclidean distance remain the same across all 10 runs.

• Here is another output from 10 runs. The difference between this and the previous output is that here p was set to 0. In other words, the experiment was conducted on UDGs. Notice how the number of hops increases and the Euclidean distance falls. This is to be expected because a UDG does not contain "long range" links. Also notice that the success rate falls to about 87%.

• Here is a single run in which I generated a small world graph (as in Project 1) with n = 10,000 on a 50 by 50 square with p = 0.1 and chose one million st-pairs chosen uniformly at random. As can be seen from the recorded times, it takes less than a minute to generate a small world graph and run the greedy algorithm on a million st-pairs.

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.