What is the equation for the average path length in a random graph? If we have random network/graph having a number of vertices $N_v$ and there number of edges $N_e$, how do we calculate the average path length between two random vertices?
 A: This paper 10.1103/PhysRevE.70.056110  calculates analytically the characteristic length (= Average shortest path) $l_{ER}$ of an Erdös-Renyi Random Network with $N$ vertices and $ \langle k \rangle $ average degree (#edges $ m= \frac{N \langle k \rangle}{2}$). 
$$
l_{ER} = \frac{\ln{N} - \gamma}{\ln{\langle k \rangle}} + \frac{1}{2},
$$
or, equally
$$
l_{ER} = \frac{\ln{N} - \gamma}{\ln(\frac{2m}{N})} + \frac{1}{2},
$$
where $\gamma \approx 0.57722$ is Euler's Constant.
A: We can do better than the average path length, because (for sufficiently large $N_e$ compared to $N_v$) the path lengths between pairs of vertices will be concentrated on one or two values.
I will rely on the paper The Diameter of Random Graphs by Béla Bollobás. Although the diameter only tells us the length of the longest path in the random graph, that path length will actually be very common. This paper is also about the random graph $\mathcal G_{n,p}$ where each edge is present independently with probability $p$, but the same thing should hold for the random graph with $n$ vertices and $m = \binom n2p$ random edges.
Let $r = (n-1)p$ (or $r = \frac{2m}{n}$) be the average degree of this graph. We assume that $\frac{r}{(\log n)^3} \to \infty$ as $n \to \infty$. (For smaller $r$, we don't have an equally precise bound; also, if $r$ is small enough that $\frac{r}{\log n} \to 0$ as $n \to \infty$, the graph is not even connected with high probability.)
It will end up being true that for some value $d = \log_r n + O(1)$, almost all distances in the graph are $d-1$ or $d$. I will be more precise below.

First, there are some critical thresholds at which the random graph moves from one diameter to the other. Suppose that $p = p(n)$, $d = d(n)$ are functions of $n$ with $p \in [0,1], d \in \mathbb N$ and there is a constant $c$  such that $p^d n^{d-1} = \log \frac{n^2}{c}$: when this happens, we have $d \approx \log_r n$. Then by Lemma 5 and Theorem 6 in the paper, the following holds with very high probability:


*

*For every vertex $v$, the number of other vertices at distance $d-2$ or less from $v$ is less than $2r^{d-2}$, and we have $\frac{2r^{d-2}}{n} \to 0$ as $n \to \infty$. So a vanishingly small fraction of shortest paths have length $d-2$ or less.

*For every vertex $v$, the number of other paths at distance exactly $d-1$ from $v$ is $(1+o(1))r^{d-1}$: the relative error goes to $0$ as $n \to \infty$. This is also a vanishingly small fraction of path lengths.

*For every vertex $v$, almost all vertices are at distance exactly $d$ from $v$.

*The total number of pairs of vertices at distance $d+1$ from each other has a Poisson distribution with mean $\frac c2$. (So there are very few such pairs and we can be very precise about how many.)

*There are no pairs of vertices at higher distance from each other.


So in this range of $p$, almost all shortest paths are the same length $d$.

For a general edge probability $p$, we are "in between" two values of $d$. In terms of $n,d$, suppose we have $p$ somewhere between $\left(\frac{2\log n}{n^{d-1}}\right)^{1/d}$ and $\left(\frac{2\log n}{n^{d-2}}\right)^{1/(d-1)}$, but not in the range close to one of the endpoints where the above case applies. Then by monotonicity we have, with very high probability:


*

*Still, a vanishingly small fraction of shortest paths from any vertex $v$ have length $d-2$ or less.

*Shortest paths of length $d-1$ and $d$ exist in a split determined by where we are in this interval; with high probability, there are many of both.

*There are no shortest paths of length $d+1$ or higher.


Equivalently, for any $p$ we can solve for the value of $d$ where this happens; we get $d$ about $\log_r n$.
As we increase $p$ (or the number of edges $m$) the value of $d$ gets smaller and smaller. Eventually, by Corollary 7 in the paper, once $m$ satisfies $\frac{m^3}{n^2} - \frac12 \log n \to \infty$, the graph has diameter $2$ with high probability. In this case, exactly $m$ of the shortest paths have length $1$, and with high probability all others have length $2$.
