## Navigation

## Efficiency of traceroute-like network exploration

### Problem formulation

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*.

### Generic graphs

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.