Efficiency of traceroute-like network exploration
Let us consider a graph with N vertices and choose n of its vertices. An example is shown in Fig. 1 [graph.eps], where N = 20 and the red circles denote the chosen vertices (n = 4). Let e denote the number of edges which are lying on the shortest paths between these n vertices. In our example in Fig. 1, e = 5. We define the quantity E(n) as the average of these e values for the vertex configurations with n vertices. Our goal was to study the quantity E(n) theoretically and numerically in the case of Barabási-Albert (BA) random graphs, and empirically in the case of the Internet.
Special case of Barabási-Albert trees
For Barabási-Albert (BA) trees, which form a special class of random graphs, we were able to derive the functional form of the E(n) function theoretically, for the case n/N << 1. The result is E(n) = a*(n-b*log(n)), where a and b are two fitting parameters. To justify the theoretical results, we have carried out computer simulations on BA trees. As can be seen in Fig. 2 [BAtree.eps], the theoretical curve can be fitted precisely to the simulation results, and this is true irrespectively of the graph size N.
No theoretical estimation for E(n) is known for the case of generic graphs. However, it is possible to derive a formula for E(n) which is valid for certain graphs where the different shortest paths discovered by the probes are independent, i.e. they do not share common segments. For example, any fully connected graph fulfills the above criterion, which in turn fails for any tree. For graphs fulfilling the criterion it can be derived that E(n) = c*n*(n-1), where c can be regarded as an empirical fitting parameter (see also Dall'Asta et al., Phys. Rev. E 71, 2005). We studied the correspondence between this theoretical result, our simulations on generic BA random graphs and our real-world internet topology measurements on Etomic and PlanetLab.
The simulation results for E(n) on BA graphs with different average degrees are shown on Fig. 3 [BAgraph.eps]. The results gained from our ip-level internet topology measurements on PlanetLab and Etomic are shown on Fig. 4 [measurement.eps]. We compared these results with the theoretical prediction by fitting the function E(n) = c*n^d*(n-1) on the simulation and measurement curves with fitting paramaters c and d. In all cases we found d < 0.6, whereas theory predicts d = 1. Therefore we conclude that the existing theory is insufficient to describe the observed properties of both non-tree BA random graphs and real-world internet networks.