Deciding on the Type of the Degree Distribution of a Graph From Trace route-Like Measurements
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. The authors explore here, their ability to infer the type (Poisson or power-law) of the degree distribution from such a limited knowledge. They 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.