# Mean path length of randomly generated graphs

I am looking to find the the average path length of 1000 random graphs with the following degree distribution, a few of the vertex degrees are included below

{2, 12, 5, 1, 12, 3, 6, 4, 2, 6, 3, 4, 4, 1, 2, 4, 4, 1, 4, 4, 7, 9}


My intuition was using GraphDistance, but it only works as a per vertex basis -- for it to work, it needs a complete graph or else it calculates the distance as infinity.

-
Take a look at AveragePathLength[] in sindominio.net/~nilvar/code/Graph.m – Dr. belisarius Nov 19 '13 at 2:38
I am not entirely sure what is going on, is this part of the graph package i have to download? The documentation is pretty obscure. – user9858 Nov 19 '13 at 3:41
I'm not sure I understand your question: what do you mean by your graph not being fully connected? Do you mean that it is not complete, or that there may be two or more components to the graph? – Vincent Tjeng Nov 19 '13 at 4:22
Yes, that what I mean. Some nodes/vertices are not connected to others. – user9858 Nov 19 '13 at 4:42

## 1 Answer

If you plan to set 0 for distance of two disconnected points, you could write something like this:

averPathLength[g_] :=
Total[DeleteCases[Flatten[GraphDistanceMatrix[g]],
Infinity]]/(VertexCount[g] (VertexCount[g] - 1))


And experiment:

dist = GraphPropertyDistribution[averPathLength[g],
g \[Distributed]DegreeGraphDistribution[{2, 12, 5, 1, 12, 3, 6, 4, 2, 6, 3, 4, 4, 1, 2, 4, 4, 1, 4, 4, 7, 9}]]

Mean@RandomVariate[dist, 1000]


Or you can just take N[Mean[dist]], and this will use Monte-Carlo method to get estimation:

N@Mean[dist]


2.07781

-
Thanks a lot for this. I actually don't quite understand the syntax, and those values seem a little high - can you explain what the code is doing? – user9858 Dec 29 '13 at 3:29