Distance distribution in random graphs and application to network exploration

We consider the problem of determining the proportion of edges that are discovered in an Erdős-Rényi graph when one constructs all shortest paths from a given source node to all other nodes. This problem is equivalent to the one of determining the proportion of edges connecting nodes that are at identical distance from the source node. The evolution of this quantity with the probability of existence of the edges exhibits intriguing oscillatory behavior. In order to perform our analysis, we introduce a different way of computing the distribution of distances between nodes. Our method outperforms previous similar analyses and leads to estimates that coincide remarkably well with numerical simulations. It allows us to characterize the phase transitions appearing when the connectivity probability varies.

Figure 1

Evolution with $p$ (logarithmic scale) of the proportion of edges that lie on a shortest path in an Erdős-Rényi random graph with $n=1000$ vertices. Each value is computed by averaging the observations made on 1000 graphs [7].

Figure 2

Evolution of $F_d$, the probability for a random node to be at a distance larger than $d$ from the source node, for $n=1000$ nodes and for $np=\left(\text{a}\right)0.5$, (b) $2$, (c) $10$, and (d) $900$. The three curves represent the experimental observations (averaged on 500 graphs), our model, and the model of Fronczak et al. given in [6].

Figure 3

Representation of $P\left[n_d=k\right]$, the probability that there are exactly $k$ nodes at distance less than $d$ from the source, obtained experimentally, compared to $F_d$, the proportion of nodes at a distance larger than $d$ from the source, obtained experimentally and with our model, for $np=2$ (a,b) and $4$ (c,d), with $n=1000$ in both cases. $P\left[n_d=k\right]$ is represented for $d=11$ in (a) and for $d=7$ in (c) as typical path lengths are different when $np=2$ or $4$. The distribution in (a) is bimodal as it contains a large peak around 0, while the peak in (c) is much smaller. Our approximation of $n_d$ by its average value $n\left(1-F_{d-1}\right)$ leads thus to larger errors for $np=2$ than for $np=4$.

Figure 4

Comparison of the evolution of $P_s\left(n,p\right)$ with $n=1000$ (a) and $10000$ (b) according to numerical experiments [7], to our model, and to Fronczak et al.’s model.

Figure 5

Evolution of $P_s\left(n,p\right)$ with $np$ for different values of $n$. All curves present a sharp increase between $np=1$ and $2$, and a global maximum at $np\simeq 2$. For larger values, the curves present several oscillations, with local maxima tending to 0.5. (b) is a zoomed-in linear-scale version of (a).

Figure 6

Evolution of $P_s\left(n,p\right)$ with $p$ for different values of $n$. On any interval $\left[ϵ,1\right]$, $P_s$ tends to the parabola $2p\left(1-p\right)$ when $n$ increases.

Figure 7

Evolution with $n^{1/2}p$ of $P_s\left(n,p\right)$ for different values of $n$. (b) is a zoomed-in linear-scale version of (a). Asymptotically, $P_c$ behaves as $2e^{-n{p}^2}\left(1-e^{-n{p}^2}\right)$ which is represented by $\ast$ in (b).

Figure 8

Evolution of $P_s\left(n,p\right)$ with $n^{2/3}p$ (a) and $n^{3/4}p$ (b), for different values of $n$. Asymptotically, local maxima $1/2$ appear for $n^{2/3}p=\sqrt[3]{\ln 2}$ and $n^{3/4}p=\sqrt[4]{\ln 2}$. The $\ast$ represent the theoretical asymptotic behavior.