research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleOn the bias of traceroute sampling: Or, power-law degree distributions in regular graphs
Bibtex cite IDRACTI-RU1-2009-68
Journal Journal of the ACM
Year published 2009
Volume 56
Understanding the graph structure of the Internet is a crucial step for building accurate network models and designing efficient algorithms for Internet applications.Yet,obtaining this graph structure can be a surprisingly difficult task,as edges cannot be explicitly queried.For instance, empirical studies of the network of InternetProtocol (IP) addresses typically rely on indirect methods like trace route to build what are approximately single-source,all-destinations,shortest-path trees. These trees only sample a fraction of the network’s edges,and a paper by Lakhinaetal.[2003]found empirically that there sulting sample is intrinsically biased.Further,in simulations,they observed that the degree distribution under trace route sampling exhibits a power law even when the underlying degree distribution is Poisson.
Achlioptas, Dimitris
Clauset, Aaron
Kempe, David
Moore, Chris
JACM published version.pdf (main file)
Publication ID713