Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
    
Take a look at AveragePathLength[] in sindominio.net/~nilvar/code/Graph.m –  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 1

up vote 4 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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