> Matthieu Latapy and Jean-Loup Guillaume

A random graph of *n* nodes may be constructed by adding each possible link with a given probability *p*. The obtained graph then has density *p*.

One may roughly model traceroute measurements of the internet topology from one monitor as the collection of *all* shortest paths from this monitor to *all* other nodes in a graph, which we call an *exploration* of the graph.

Then, one obtains all the links which belong to a shortest path from the monitor to any other node; in other words, **the only missing links are the ones between two nodes at the same distance from the monitor**.

The number of such links higly depends on the density of the graph. If the graph is a tree (and thus its density is very low) then all links belong to a shortest path, and its exploration will show 100% of the links; if the graph is a clique (and thus has the maximal density, *1*), then only *n* links are on a shortest path, and thus the exploration will miss many links (*(n-1)(n-2)/2* precisely, *i.e.* almost all of them if *n* is large).

The plot gives the proportion of links discovered during the exploration of a random graph as a function of its density. It has several non-trivial peaks, and has been called *camel plot* for this reason. It shows that the exploration process has a very complex behavior which depends strongly on the density, but has no direct relation with it.

More information in:

Complex Network Metrology, by Jean-Loup Guillaume and Matthieu Latapy.

Distance distribution in random graphs and application to networks exploration, by Vincent D. Blondel, Jean-Loup Guillaume, Julien M. Hendrickx, and Raphael M. Jungers.