I have found the following in a network-science article and would like clarification of what the authors are claiming:

We observe that the root mean square of the difference between the empirical probability density distributions of sample networks with $h$ and $(h + 1)$ seeds steadily decreases fitting to the $y = 1/x$ line, confirming that our estimation would converge to the true average path length.

The authors are trying to measure the average path length of a large network by sampling vertices at random (which they refer to as seeds; presumably the sampling is uniform) and then performing a breadth-first search from the selected vertex to determine the length of the path to every other node in the network. (Implicitly, the graph should be connected.)

Can anybody guess what it is that the authors do here regarding their consistency claim? Is there a name for this method? And could you please explain it better so I can understand how to do the same thing in a similar situation?

The excerpt above is from page 839, just above the section heading for Section 5.2, of the following article.

Y.-Y. Ahn, S. Han, H. Kwak, S. Moon and H. Jeong (2007), Analysis of topological characteristics of huge online social networking services, Proc. WWW 2007 (Track: Semantic Web), pp. 835–844.

  • 1
    $\begingroup$ Welcome to the site. It would be (much) better to provide a full citation to the article itself. For example, even some of the wording in the paraphrased quote comes across as a bit rough and so it's not clear if that's from the source itself or was introduced as you adapted it. So that you don't accidentally get incorrect advice, please consider my suggestion above. Cheers. $\endgroup$ – cardinal Feb 10 '13 at 14:15
  • 1
    $\begingroup$ Thank you! The original article is here: www2007.org/papers/paper676.pdf, page 5 (839), right before the 5.2 heading. I hope the technicalities of the field (network science) won't stand in the way of discussing the statistics issue. $\endgroup$ – WindChimes Feb 10 '13 at 19:05
  • $\begingroup$ (+1) I don't think the idiosyncrasies of network science will get in the way. :-) $\endgroup$ – cardinal Feb 10 '13 at 19:53

Your Answer

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

Browse other questions tagged or ask your own question.