Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-27T07:54:57.714Z Has data issue: false hasContentIssue false
  • English
  • Français

FIRST-PASSAGE PERCOLATION ON THE RANDOM GRAPH

Published online by Cambridge University Press:  10 April 2001

Remco van der Hofstad ,
Gerard Hooghiemstra  and
Piet Van Mieghem
Remco van der Hofstad
Affiliation:
ITS, Department of Mathematics, Delft University of Technology, 2628 CD Delft, The Netherlands, E-mail: [email protected]
Gerard Hooghiemstra
Affiliation:
ITS, Department of Mathematics, Delft University of Technology, 2628 CD Delft, The Netherlands, E-mail: [email protected]
Piet Van Mieghem
Affiliation:
ITS, Department of Electrical Engineering, Delft University of Technology, 2628 CD Delft, The Netherlands, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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 → ∞, for the case of the random graph where each link is present independently with a probability pN as long as NpN/(log N)3 → ∞. 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.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 15 , Issue 2 , April 2001 , pp. 225 - 237
Copyright
© 2001 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)