Random graph exploration with shortest paths

> Matthieu Latapy and Jean-Loup Guillaume

Random graph exploration with shortest paths

Random graph exploration with shortest paths

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.

This entry was posted in Plots and tagged , ,