3
$\begingroup$

I am calculating the average minimum path length of Erdős–Rényi graphs. I am using the $G(N,n)$ model whereby a $N$ node graph with $n$ edges are generated uniformly.

I found the expected average minimum path length here

$$l_{ER} = \frac{\ln(N) - \gamma}{\ln(\langle k \rangle)} + \frac{1}{2} = \frac{\ln(N) - \gamma}{\ln(2n) - \ln(N)} + \frac{1}{2}{}$$

Where $\gamma$ is the Euler–Mascheroni constant and the average degree $\langle k \rangle = 2n/N$ is an obvious corollary of the handshaking lemma.

Is there is an estimate for the variance of average minimum path length for Erdős–Rényi graphs?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.