BibTeX Entry |

@inproceedings{LakhinaByersCrovellaXie03, author = {Lakhina, Anukool and Byers, John and Crovella, Mark and Xie, Peng}, title = {Sampling Biases in {IP} Topology Measurements}, booktitle = {Proceedings of IEEE Infocom}, year = {2003}, month = apr, URL = {http://www.cs.bu.edu/faculty/crovella/paper-archive/infocom03-graph-bias.pdf}, abstract = {Considerable attention has been focused on the properties of graphs derived from Internet measurements. Router-level topologies collected via traceroute studies have led some authors to conclude that the router graph of the Internet is a scale-free graph, or more generally a power-law random graph. In such a graph, the degree distribution of nodes follows a distribution with a power-law tail. In this paper we argue that the evidence to date for this conclusion is at best insufficient. We show that graphs appearing to have power-law degree distributions can arise surprisingly easily, when sampling graphs whose true degree distribution is not at all like a power-law. For example, given a classical Erdos-Renyi sparse, random graph, the subgraph formed by a collection of shortest paths from a small set of random sources to a larger set of random destinations can easily appear to show a degree distribution remarkably like a power-law. We explore the reasons for how this effect arises, and show that in such a setting, edges are sampled in a highly biased manner. This insight allows us to distinguish measurements taken from the Erdos-Renyi graphs from those taken from power-law random graphs. When we apply this distinction to a number of well-known datasets, we find that the evidence for sampling bias in these datasets is strong.} }