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]

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

[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]

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

[8]

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

[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]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

Bertrand Lods. Variational characterizations of the effective multiplication factor of a nuclear reactor core. Kinetic & Related Models, 2009, 2 (2) : 307-331. doi: 10.3934/krm.2009.2.307

[20]

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

2016 Impact Factor: 1.2

Metrics

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

[Back to Top]