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 and 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 and 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 and 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 and Continuous Dynamical Systems, 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 and Continuous Dynamical Systems, 2019, 39 (1) : 115-130. doi: 10.3934/dcds.2019005

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Ł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

[19]

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

[20]

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

Metrics

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

[Back to Top]