WLS12

Summary

Xiaomin Wang, Matthieu Latapy and Michèle Soria, (2012) Deciding on the type of the degree distribution of a graph from traceroute-like measurements. International Journal of Computer Networks & Communications, 4(2):1-20. (PDF)

Abstract

The degree distribution of the Internet topology is considered as one of its main properties. However, it is only known through a measurement procedure which gives a biased estimate. This measurement may in first approximation be modeled by a BFS (Breadth-First Search) tree. We explore here our ability to infer the type (Poisson or power-law) of the degree distribution from such a limited knowledge. We design procedures which estimate the degree distribution of a graph from a BFS of it, and show experimentally (on models and real-world data) that this approach succeeds in making the difference between Poisson and power-law degree distributions.

Bibtex entry

@ARTICLE { WLS12,
    AUTHOR = { Xiaomin Wang and Matthieu Latapy and Michèle Soria, },
    TITLE = { Deciding on the type of the degree distribution of a graph from traceroute-like measurements },
    JOURNAL = { International Journal of Computer Networks & Communications },
    VOLUME = { 4 },
    NUMBER = { 2 },
    YEAR = { 2012 },
    MONTH = { may },
    PDF = { http://www.complexnetworks.fr/wp-content/uploads/2012/06/Article.pdf },
    PAGES = { 1-20 },
    ABSTRACT = { The degree distribution of the Internet topology is considered as one of its main properties. However, it is only known through a measurement procedure which gives a biased estimate. This measurement may in first approximation be modeled by a BFS (Breadth-First Search) tree. We explore here our ability to infer the type (Poisson or power-law) of the degree distribution from such a limited knowledge. We design procedures which estimate the degree distribution of a graph from a BFS of it, and show experimentally (on models and real-world data) that this approach succeeds in making the difference between Poisson and power-law degree distributions. },
}