Network's shortest paths

Network's shortest paths

Team: Sergey Melnik, Roberta Sinatra, Bruno Abrahao, Michael Szell, Drew Levin

Consider a random network consisting of N nodes where each pair of nodes is connected with a given probability p (see Erdos-Renyi random graph). The question is about the shortest path through the network from one node to another (also called geodesic path, or intervertex distance):

Can we calculate analytically (and exactly) the probability distribution of shortest paths in such a network? That is, how likely it is that a pair of nodes chosen at random will be distance D apart. For distance D=1 the answer is obviously p. What are such probabilities for distances D=2, D=3, D=4, etc.?

Note that the network has a finite number of nodes (which is not necessarily large) and there are only 2 parameters here, N and p. This is a simple yet fundamental question and there is much more to follow in terms of immediate applications and new theories once we answer it.