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. },
}