Why Mapping the Internet is Hard

Details Why Mapping the Internet is Hard Why Mapping the Internet is Hard

2004-07-13

arxiv.org/abs/cond-mat/0407339v1

Physics

Condensed Matter

Disordered Systems and Neural Networks

supercedes cond-mat/0312674

Scientific paper

Despite great effort spent measuring topological features of large networks like the Internet, it was recently argued that sampling based on taking paths through the network (e.g., traceroutes) introduces a fundamental bias in the observed degree distribution. We examine this bias analytically and experimentally. For classic random graphs with mean degree c, we show analytically that traceroute sampling gives an observed degree distribution P(k) ~ 1/k for k < c, even though the underlying degree distribution is Poisson. For graphs whose degree distributions have power-law tails P(k) ~ k^-alpha, the accuracy of traceroute sampling is highly sensitive to the population of low-degree vertices. In particular, when the graph has a large excess (i.e., many more edges than vertices), traceroute sampling can significantly misestimate alpha.

Affiliated with

Also associated with

No associations

Rating

Why Mapping the Internet is Hard does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Why Mapping the Internet is Hard, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Why Mapping the Internet is Hard will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-334889