# American Institute of Mathematical Sciences

June  2008, 3(2): 371-393. doi: 10.3934/nhm.2008.3.371

## K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases

 1 CONICET and Facultad de Ingeniería, Universidad de Buenos Aires, Paseo Colón 850, C1063ACV Ciudad de Buenos Aires, Argentina 2 Abdus Salam International Center for Theoretical Physics, Strada Costiera 11, 34014 Trieste, Italy 3 LPT (UMR du CNRS 8627), Université de Paris-Sud, France 4 School of Informatics, Indiana University, Bloomington, IN 47048

Received  February 2008 Revised  March 2008 Published  March 2008

We consider the $k$-core decomposition of network models and Internet graphs at the autonomous system (AS) level. The k-core analysis allows to characterize networks beyond the degree distribution and uncover structural properties and hierarchies due to the specific architecture of the system. We compare the $k$-core structure obtained for AS graphs with those of several network models and discuss the differences and similarities with the real Internet architecture. The presence of biases and the incompleteness of the real maps are discussed and their effect on the $k$-core analysis is assessed with numerical experiments simulating biased exploration on a wide range of network models. We find that the $k$-core analysis provides an interesting characterization of the fluctuations and incompleteness of maps as well as information helping to discriminate the original underlying structure.
Citation: José Ignacio Alvarez-Hamelin, Luca Dall'Asta, Alain Barrat, Alessandro Vespignani. K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases. Networks & Heterogeneous Media, 2008, 3 (2) : 371-393. doi: 10.3934/nhm.2008.3.371
 [1] Michael Baur, Marco Gaertler, Robert Görke, Marcus Krug, Dorothea Wagner. Augmenting $k$-core generation with preferential attachment. Networks & Heterogeneous Media, 2008, 3 (2) : 277-294. doi: 10.3934/nhm.2008.3.277 [2] D. Alderson, H. Chang, M. Roughan, S. Uhlig, W. Willinger. The many facets of internet topology and traffic. Networks & Heterogeneous Media, 2006, 1 (4) : 569-600. doi: 10.3934/nhm.2006.1.569 [3] Marek Bodnar, Urszula Foryś. Time Delay In Necrotic Core Formation. Mathematical Biosciences & Engineering, 2005, 2 (3) : 461-472. doi: 10.3934/mbe.2005.2.461 [4] François Alouges, Sylvain Faure, Jutta Steiner. The vortex core structure inside spherical ferromagnetic particles. Discrete & Continuous Dynamical Systems - A, 2010, 27 (4) : 1259-1282. doi: 10.3934/dcds.2010.27.1259 [5] Domingo González, Gamaliel Blé. Core entropy of polynomials with a critical point of maximal order. Discrete & Continuous Dynamical Systems - A, 2019, 39 (1) : 115-130. doi: 10.3934/dcds.2019005 [6] Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems & Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025 [7] Siwei Yu, Jianwei Ma, Stanley Osher. Geometric mode decomposition. Inverse Problems & Imaging, 2018, 12 (4) : 831-852. doi: 10.3934/ipi.2018035 [8] Stefano Bianchini, Daniela Tonon. A decomposition theorem for $BV$ functions. Communications on Pure & Applied Analysis, 2011, 10 (6) : 1549-1566. doi: 10.3934/cpaa.2011.10.1549 [9] Shunfu Jin, Wuyi Yue, Zhanqiang Huo. Performance evaluation for connection oriented service in the next generation Internet. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 749-761. doi: 10.3934/naco.2011.1.749 [10] Shu Zhang, Jian Xu. Time-varying delayed feedback control for an internet congestion control model. Discrete & Continuous Dynamical Systems - B, 2011, 16 (2) : 653-668. doi: 10.3934/dcdsb.2011.16.653 [11] Shuren Liu, Qiying Hu, Yifan Xu. Optimal inventory control with fixed ordering cost for selling by internet auctions. Journal of Industrial & Management Optimization, 2012, 8 (1) : 19-40. doi: 10.3934/jimo.2012.8.19 [12] Shu Zhang, Yuan Yuan. The Filippov equilibrium and sliding motion in an internet congestion control model. Discrete & Continuous Dynamical Systems - B, 2017, 22 (3) : 1189-1206. doi: 10.3934/dcdsb.2017058 [13] Jonathan H. Tu, Clarence W. Rowley, Dirk M. Luchtenburg, Steven L. Brunton, J. Nathan Kutz. On dynamic mode decomposition: Theory and applications. Journal of Computational Dynamics, 2014, 1 (2) : 391-421. doi: 10.3934/jcd.2014.1.391 [14] Steven L. Brunton, Joshua L. Proctor, Jonathan H. Tu, J. Nathan Kutz. Compressed sensing and dynamic mode decomposition. Journal of Computational Dynamics, 2015, 2 (2) : 165-191. doi: 10.3934/jcd.2015002 [15] Fritz Colonius, Paulo Régis C. Ruffino. Nonlinear Iwasawa decomposition of control flows. Discrete & Continuous Dynamical Systems - A, 2007, 18 (2&3) : 339-354. doi: 10.3934/dcds.2007.18.339 [16] Thiago Ferraiol, Mauro Patrão, Lucas Seco. Jordan decomposition and dynamics on flag manifolds. Discrete & Continuous Dynamical Systems - A, 2010, 26 (3) : 923-947. doi: 10.3934/dcds.2010.26.923 [17] Mauro Patrão, Luiz A. B. San Martin. Morse decomposition of semiflows on fiber bundles. Discrete & Continuous Dynamical Systems - A, 2007, 17 (3) : 561-587. doi: 10.3934/dcds.2007.17.561 [18] Brandy Rapatski, James Yorke. Modeling HIV outbreaks: The male to female prevalence ratio in the core population. Mathematical Biosciences & Engineering, 2009, 6 (1) : 135-143. doi: 10.3934/mbe.2009.6.135 [19] Xiaofeng Ren, Chong Wang. A stationary core-shell assembly in a ternary inhibitory system. Discrete & Continuous Dynamical Systems - A, 2017, 37 (2) : 983-1012. doi: 10.3934/dcds.2017041 [20] Chin-Chin Wu, Zhengce Zhang. Dead-core rates for the heat equation with a spatially dependent strong absorption. Discrete & Continuous Dynamical Systems - B, 2013, 18 (8) : 2203-2210. doi: 10.3934/dcdsb.2013.18.2203

2018 Impact Factor: 0.871