June  2008, 3(2): 323-332. doi: 10.3934/nhm.2008.3.323

Bounding the bias of tree-like sampling in IP topologies


Department of Mathematics, Bar-Ilan University, Ramat-Gan 52900, Israel


School of Electrical Engineering, Tel Aviv University, Ramat Aviv 69978, Israel, Israel

Received  September 2007 Revised  January 2008 Published  March 2008

It is widely believed that the Internet's AS-graph degree distribution obeys a power-law form. However, it was recently argued that since Internet data is collected in a tree-like fashion, it only produces a sample of the degree distribution, and this sample may be biased. This argument was backed by simulation data and mathematical analysis, which demonstrated that under certain conditions a tree sampling procedure can produce an artificial power-law in the degree distribution. Thus, although the observed degree distribution of the AS-graph follows a power-law, this phenomenon may be an artifact of the sampling process. In this work we provide some evidence to the contrary. We show, by analysis and simulation, that when the underlying graph degree distribution obeys a power-law with an exponent $\gamma>2$, a tree-like sampling process produces a negligible bias in the sampled degree distribution. Furthermore, recent data collected from the DIMES project, which is not based on single source sampling, indicates that the Internet indeed obeys a power-law degree distribution with an exponent $\gamma>2$. Combining this empirical data with our simulation of traceroute experiments on DIMES-measured AS-graph as the underlying graph, and with our analysis, we conclude that the bias in the degree distribution calculated from BGP data is negligible.
Citation: Reuven Cohen, Mira Gonen, Avishai Wool. Bounding the bias of tree-like sampling in IP topologies. Networks and Heterogeneous Media, 2008, 3 (2) : 323-332. doi: 10.3934/nhm.2008.3.323

D. Alderson, H. Chang, M. Roughan, S. Uhlig, W. Willinger. The many facets of internet topology and traffic. Networks and Heterogeneous Media, 2006, 1 (4) : 569-600. doi: 10.3934/nhm.2006.1.569


Shuping Li, Zhen Jin. Impacts of cluster on network topology structure and epidemic spreading. Discrete and Continuous Dynamical Systems - B, 2017, 22 (10) : 3749-3770. doi: 10.3934/dcdsb.2017187


Tingting Zhu. Emergence of synchronization in Kuramoto model with frustration under general network topology. Networks and Heterogeneous Media, 2022, 17 (2) : 255-291. doi: 10.3934/nhm.2022005


T. S. Evans, A. D. K. Plato. Network rewiring models. Networks and Heterogeneous Media, 2008, 3 (2) : 221-238. doi: 10.3934/nhm.2008.3.221


Inom Mirzaev, David M. Bortz. A numerical framework for computing steady states of structured population models and their stability. Mathematical Biosciences & Engineering, 2017, 14 (4) : 933-952. doi: 10.3934/mbe.2017049


Alberto Bressan, Khai T. Nguyen. Conservation law models for traffic flow on a network of roads. Networks and Heterogeneous Media, 2015, 10 (2) : 255-293. doi: 10.3934/nhm.2015.10.255


Gabriel Montes-Rojas, Pedro Elosegui. Network ANOVA random effects models for node attributes. Journal of Dynamics and Games, 2020, 7 (3) : 239-252. doi: 10.3934/jdg.2020017


Simone Göttlich, Stephan Knapp. Semi-Markovian capacities in production network models. Discrete and Continuous Dynamical Systems - B, 2017, 22 (9) : 3235-3258. doi: 10.3934/dcdsb.2017090


Claus Kirchner, Michael Herty, Simone Göttlich, Axel Klar. Optimal control for continuous supply network models. Networks and Heterogeneous Media, 2006, 1 (4) : 675-688. doi: 10.3934/nhm.2006.1.675


Tanka Nath Dhamala. A survey on models and algorithms for discrete evacuation planning network problems. Journal of Industrial and Management Optimization, 2015, 11 (1) : 265-289. doi: 10.3934/jimo.2015.11.265


Gunhild A. Reigstad. Numerical network models and entropy principles for isothermal junction flow. Networks and Heterogeneous Media, 2014, 9 (1) : 65-95. doi: 10.3934/nhm.2014.9.65


Hari Nandan Nath, Urmila Pyakurel, Tanka Nath Dhamala, Stephan Dempe. Dynamic network flow location models and algorithms for quickest evacuation planning. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2943-2970. doi: 10.3934/jimo.2020102


Hasan Hosseini-Nasab, Vahid Ettehadi. Development of opened-network data envelopment analysis models under uncertainty. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022027


Bruce Hughes. Geometric topology of stratified spaces. Electronic Research Announcements, 1996, 2: 73-81.


Guizhen Cui, Wenjuan Peng, Lei Tan. On the topology of wandering Julia components. Discrete and Continuous Dynamical Systems, 2011, 29 (3) : 929-952. doi: 10.3934/dcds.2011.29.929


Fengbo Hang, Fanghua Lin. Topology of Sobolev mappings IV. Discrete and Continuous Dynamical Systems, 2005, 13 (5) : 1097-1124. doi: 10.3934/dcds.2005.13.1097


Robert Cardona. The topology of Bott integrable fluids. Discrete and Continuous Dynamical Systems, 2022  doi: 10.3934/dcds.2022054


Yu-Jhe Huang, Zhong-Fu Huang, Jonq Juang, Yu-Hao Liang. Flocking of non-identical Cucker-Smale models on general coupling network. Discrete and Continuous Dynamical Systems - B, 2021, 26 (2) : 1111-1127. doi: 10.3934/dcdsb.2020155


Dengfeng Sun, Issam S. Strub, Alexandre M. Bayen. Comparison of the performance of four Eulerian network flow models for strategic air traffic management. Networks and Heterogeneous Media, 2007, 2 (4) : 569-595. doi: 10.3934/nhm.2007.2.569


Kuo-Shou Chiu. Periodicity and stability analysis of impulsive neural network models with generalized piecewise constant delays. Discrete and Continuous Dynamical Systems - B, 2022, 27 (2) : 659-689. doi: 10.3934/dcdsb.2021060

2020 Impact Factor: 1.213


  • PDF downloads (44)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]