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.