1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Take a look at AveragePathLength[] in sindominio.net/~nilvar/code/Graph.m $\endgroup$ Nov 19 '13 at 2:38
  • $\begingroup$ 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. $\endgroup$
    – user9858
    Nov 19 '13 at 3:41
  • $\begingroup$ 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? $\endgroup$ Nov 19 '13 at 4:22
  • $\begingroup$ Yes, that what I mean. Some nodes/vertices are not connected to others. $\endgroup$
    – user9858
    Nov 19 '13 at 4:42
5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – user9858
    Dec 29 '13 at 3:29
3
$\begingroup$

The IGraph/M package has the function IGAveragePathLength for computing the mean path length, with the following advantages:

  • Unlike MeanGraphDistance, it does not compute the whole graph distance matrix before doing the averaging. Thus we can use it on large graphs such as ExampleData[{"NetworkGraph", "CondensedMatterCollaborations2005"}] without running out of memory.

  • Vertex pairs between which there is no path are excluded. Thus it is possible to get results (other than Infinity) for disconnected graphs.

There are also the IGDistanceCounts and IGDistanceHistogram functions for the unweighted and weighted path length histograms.

$\endgroup$
4
  • $\begingroup$ Hi Szabolcs, thanks for the mention of the other features too, this has been helpful! To make sure I've understood correctly, IGAveragePathLength always assumes edge-weights are $=1,$ or in case the graph is weighted, does it find the average path length in terms of shortest path corresponding to minimum sum of weights? I ask, because I am creating random graphs RandomGraph[{15,20},EdgeWeight -> RandomReal[1., 20]] and treat them as electric networks, then edge-weights are conductances, and wanted to ask how to interpret IGAveragePathLength for such graphs. Thanks a lot in advance! $\endgroup$
    – user52181
    Nov 19 '19 at 14:49
  • $\begingroup$ @user929304 IGAveragePathLength considers edge weights. You can test this by comparing IGAveragePathLength[Graph[{1 <-> 2}]] and IGAveragePathLength[Graph[{1 <-> 2}, EdgeWeight -> {.123}]]. It appears that there was an error in the documentation that claimed that weights are ignored. This is now corrected. $\endgroup$
    – Szabolcs
    Nov 21 '19 at 6:46
  • $\begingroup$ @user929304 "and treat them as electric networks" Instead of using path lengths, you may want to consider computing effective resistances/conductances between all pairs of vertices. $\endgroup$
    – Szabolcs
    Nov 21 '19 at 6:46
  • $\begingroup$ Many thanks Szabolcs, this clarified things perfectly! I thought if the weights are resistances, I can interpret the ave-path-len as ave series connection between 2 arbitrary nodes, does that make sense? In case one computes the effective resistances, do you happen to know of a reasonable way of averaging them? to resemble the average path length property, but in terms of resistances. Thanks again for your feedback. $\endgroup$
    – user52181
    Nov 21 '19 at 8:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.