Probability in the Engineering and Informational Sciences

Probability in the Engineering and Informational Sciences

Table of Contents - 2001 - Volume 15, Issue 02  


FIRST-PASSAGE PERCOLATION ON THE RANDOM GRAPH

Remco  van der Hofstad a1, Gerard  Hooghiemstra  a2 and Piet  Van Mieghem a3
a1 ITS, Department of Mathematics, Delft University of Technology, 2628 CD Delft, The Netherlands, E-mail: R.W.vanderHofstad@its.tudelft.nl
a2 ITS, Department of Mathematics, Delft University of Technology, 2628 CD Delft, The Netherlands, E-mail: G.Hooghiemstra@its.tudelft.nl
a3 ITS, Department of Electrical Engineering, Delft University of Technology, 2628 CD Delft, The Netherlands, E-mail: p.vanmieghem@its.tudelft.nl

Abstract

We study first-passage percolation on the random graph Gp(N) with exponentially distributed weights on the links. For the special case of the complete graph, this problem can be described in terms of a continuous-time Markov chain and recursive trees. The Markov chain X(t) describes the number of nodes that can be reached from the initial node in time t. The recursive trees, which are uniform trees of N nodes, describe the structure of the cluster once it contains all the nodes of the complete graph. From these results, the distribution of the number of hops (links) of the shortest path between two arbitrary nodes is derived.

We generalize this result to an asymptotic result, as N [rightward arrow] [infty infinity], for the case of the random graph where each link is present independently with a probability pN as long as NpN/(log N)3 [rightward arrow] [infty infinity]. The interesting point of this generalization is that (1) the limiting distribution is insensitive to p and (2) the distribution of the number of hops of the shortest path between two arbitrary nodes has a remarkable fit with shortest path data measured in the Internet.