Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Accuracy and scaling phenomena in Internet mapping.

Aaron Clauset1, Cristopher Moore

  • 1Computer Science Department, University of New Mexico, Albuquerque, NM 87131, USA. aaron@cs.unm.edu

Physical Review Letters
|February 9, 2005
PubMed
Summary

Network sampling via limited sources, like internet traceroutes, introduces bias in topological features. Accurate degree distribution estimation requires a number of sources proportional to the graph's mean degree.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Cross-assay RNA modeling reveals cancer biomarkers.

bioRxiv : the preprint server for biology·2026
Same author

On the predictability of progression-free survival in ovarian cancer from NanoString gene expression data.

bioRxiv : the preprint server for biology·2026
Same author

Predicting missing links in food webs using stacked models and species traits.

Nature communications·2026
Same author

In Science Journals.

Science (New York, N.Y.)·2025
Same author

Recommendations for sharing network data and materials.

Network science (Cambridge University Press)·2025
Same author

Gender and racial diversity socialization in science.

Nature computational science·2025

Area of Science:

  • Network Science
  • Graph Theory
  • Internet Measurement

Background:

  • Network sampling methods, such as traceroutes, are widely used for analyzing network topology.
  • Previous research suggests that sampling from a limited number of sources can introduce fundamental biases in observed network properties.

Purpose of the Study:

  • To analytically and experimentally examine the bias introduced by source-limited network sampling.
  • To investigate the impact of sampling on degree distribution estimation in random and power-law graphs.
  • To determine the conditions necessary for accurate estimation of topological parameters.

Main Methods:

  • Analytical derivations for Erdos-Renyi random graphs.
  • Experimental simulations on graphs with power-law degree distributions.
  • Comparison of observed degree distributions with underlying distributions.

Main Results:

  • Source-limited sampling generates an observed degree distribution P(k) ~ k(-1) for Erdos-Renyi graphs, deviating from the Poissonian underlying distribution.
  • Sampling can significantly underestimate the power-law exponent alpha in graphs with many edges.
  • Accurate estimation of alpha requires a number of sources that scales linearly with the mean degree.

Conclusions:

  • Network sampling methodology significantly impacts topological feature accuracy.
  • The number of sampling sources is critical for reliable degree distribution estimation.
  • Published values for Internet topology parameters may require re-evaluation due to sampling biases.

Related Experiment Videos