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


CONICET and Facultad de Ingeniería, Universidad de Buenos Aires, Paseo Colón 850, C1063ACV Ciudad de Buenos Aires, Argentina


Abdus Salam International Center for Theoretical Physics, Strada Costiera 11, 34014 Trieste, Italy


LPT (UMR du CNRS 8627), Université de Paris-Sud, France


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 and Heterogeneous Media, 2008, 3 (2) : 371-393. doi: 10.3934/nhm.2008.3.371

Michael Baur, Marco Gaertler, Robert Görke, Marcus Krug, Dorothea Wagner. Augmenting $k$-core generation with preferential attachment. Networks and Heterogeneous Media, 2008, 3 (2) : 277-294. doi: 10.3934/nhm.2008.3.277


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


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


François Alouges, Sylvain Faure, Jutta Steiner. The vortex core structure inside spherical ferromagnetic particles. Discrete and Continuous Dynamical Systems, 2010, 27 (4) : 1259-1282. doi: 10.3934/dcds.2010.27.1259


Domingo González, Gamaliel Blé. Core entropy of polynomials with a critical point of maximal order. Discrete and Continuous Dynamical Systems, 2019, 39 (1) : 115-130. doi: 10.3934/dcds.2019005


Madeleine Jotz Lean, Kirill C. H. Mackenzie. Transitive double Lie algebroids via core diagrams. Journal of Geometric Mechanics, 2021, 13 (3) : 403-457. doi: 10.3934/jgm.2021023


Shunfu Jin, Wuyi Yue, Zhanqiang Huo. Performance evaluation for connection oriented service in the next generation Internet. Numerical Algebra, Control and Optimization, 2011, 1 (4) : 749-761. doi: 10.3934/naco.2011.1.749


Shu Zhang, Jian Xu. Time-varying delayed feedback control for an internet congestion control model. Discrete and Continuous Dynamical Systems - B, 2011, 16 (2) : 653-668. doi: 10.3934/dcdsb.2011.16.653


Shuren Liu, Qiying Hu, Yifan Xu. Optimal inventory control with fixed ordering cost for selling by internet auctions. Journal of Industrial and Management Optimization, 2012, 8 (1) : 19-40. doi: 10.3934/jimo.2012.8.19


Shu Zhang, Yuan Yuan. The Filippov equilibrium and sliding motion in an internet congestion control model. Discrete and Continuous Dynamical Systems - B, 2017, 22 (3) : 1189-1206. doi: 10.3934/dcdsb.2017058


Vikas Srivastava, Sumit Kumar Debnath, Pantelimon Stǎnicǎ, Saibal Kumar Pal. A multivariate identity-based broadcast encryption with applications to the internet of things. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021050


Chunhua Gao, Yufu Ning, Fengming Liu, Meiling Jin. Uncertain comprehensive evaluation of the spreading intensity of internet rumors in the new media era. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022037


Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems and Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025


Siwei Yu, Jianwei Ma, Stanley Osher. Geometric mode decomposition. Inverse Problems and Imaging, 2018, 12 (4) : 831-852. doi: 10.3934/ipi.2018035


Stefano Bianchini, Daniela Tonon. A decomposition theorem for $BV$ functions. Communications on Pure and Applied Analysis, 2011, 10 (6) : 1549-1566. doi: 10.3934/cpaa.2011.10.1549


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


Chin-Chin Wu, Zhengce Zhang. Dead-core rates for the heat equation with a spatially dependent strong absorption. Discrete and Continuous Dynamical Systems - B, 2013, 18 (8) : 2203-2210. doi: 10.3934/dcdsb.2013.18.2203


Łukasz Struski, Jacek Tabor, Tomasz Kułaga. Cone-fields without constant orbit core dimension. Discrete and Continuous Dynamical Systems, 2012, 32 (10) : 3651-3664. doi: 10.3934/dcds.2012.32.3651


Xinfu Chen, Jong-Shenq Guo, Bei Hu. Dead-core rates for the porous medium equation with a strong absorption. Discrete and Continuous Dynamical Systems - B, 2012, 17 (6) : 1761-1774. doi: 10.3934/dcdsb.2012.17.1761


Xiaofeng Ren, Chong Wang. A stationary core-shell assembly in a ternary inhibitory system. Discrete and Continuous Dynamical Systems, 2017, 37 (2) : 983-1012. doi: 10.3934/dcds.2017041

2020 Impact Factor: 1.213


  • PDF downloads (97)
  • HTML views (0)
  • Cited by (52)

[Back to Top]