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?
[Math] the equation for the average path length in a random graph
graph theoryNetworkrandom-graphs
Related Solutions
Your mistake is that you assume that the probability of a union of events is the sum of their probabilities. This is only true if the events are disjoint, which isn't the case here.
Your formula for the probability that there is a path of length $k$ is wrong. Note for example that for $k=2$ your expression for $P_n(k)$ is $\frac{n-2}{2}$, which is larger than 1. Probabilities are always between zero and one.
In fact, your formula is the expected number of paths of length $k$.
When you add the probabilities together, once again you are computing an expectation. What your formula actually computes is the expected number of paths between two vertices.
Apparently, my understanding of creating the regular graphs was wrong in the case of Small World Propensity.
I did a discussion with people working in the field of brain connectivity and with the help of this paper (in this Small World Propensity is originally discussed), I was able to figure out the meaning of lattice used in this context.
Below I am quoting a few points from the paper that helped me figure it out.
In section Generating Weighted Small-World Networks
- Begin with a network of N nodes that are arranged on a lattice and connected to all neighbors within a radius, r.
In Figure 3a shows that the initial lattice is a circular graph in which every node is connected to n neighbours both on left and right.
Now, this confirmed that I needed to use Lattice(dim) for generating the initial lattice, but now a second question arose - what should be the value of dim?
This was answered in this paper, Figure 2a has explained that such a lattice is A periodic one-dimensional ( D = 1 ) lattice (i.e. a ring) where each vertex is connected to its n neighbours on left and right.
and the documentation of igraph for Lattice confirmed that I need to put a list containing 1 element (1 dimension), and the value of that element should be the number of nodes to be generated, further, I need to put the number of neighbours on either side to directly connect.
So, If I need 20 nodes and connect 3 neighbours in each direction (so total of 6 neighbours will be connected), function should be:
G = ig.Graph().Lattice(dim=[20],nei=3)
This generates the following graph.
Best Answer
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.