American Institute of Mathematical Sciences

Advanced
June  2008, 3(2): 277-294. doi: 10.3934/nhm.2008.3.277

Augmenting $k$-core generation with preferential attachment

Michael Baur 1, , Marco Gaertler 1, , Robert Görke 1, , Marcus Krug 1, and  Dorothea Wagner 1,

1. 

Faculty of Informatics, Universität Karlsruhe (TH), 78131 Karlsruhe, Germany, Germany, Germany, Germany, Germany

Received  August 2007 Revised  March 2008 Published  March 2008

The modeling of realistic networks is of prime importance for modern complex systems research. Previous procedures typically model the natural growth of networks by means of iteratively adding nodes, geometric positioning information, a definition of link connectivity based on the preference for nearest neighbors or already highly connected nodes, or combine several of these approaches.
Our novel model brings together the well-know concepts of $k$-cores, originally introduced in social network analysis, and of preferential attachment. Recent studies exposed the significant $k$-core structure of several real world systems, e.g., the AS network of the Internet. We present a simple and efficient method for generating networks which at the same time strictly adhere to the characteristics of a given $k$-core structure, called core fingerprint, and feature a power-law degree distribution. We showcase our algorithm in a com- parative evaluation with two well-known AS network generators.
Keywords: k-core structure, graph generation, preferential attachment.
Mathematics Subject Classification: Primary: 05C85, 05C80; Secondary: 05C7.
Citation: 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
[1]

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

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

Magdalena Foryś-Krawiec, Jana Hantáková, Piotr Oprocha. On the structure of α-limit sets of backward trajectories for graph maps. Discrete and Continuous Dynamical Systems, 2022, 42 (3) : 1435-1463. doi: 10.3934/dcds.2021159
[4]

Maria Aguareles, Marco A. Fontelos, Juan J. Velázquez. The structure of the quiescent core in rigidly rotating spirals in a class of excitable systems. Discrete and Continuous Dynamical Systems - B, 2012, 17 (6) : 1605-1638. doi: 10.3934/dcdsb.2012.17.1605
[5]

Zhiwen Zhao. Asymptotic analysis for the electric field concentration with geometry of the core-shell structure. Communications on Pure and Applied Analysis, 2022, 21 (4) : 1109-1137. doi: 10.3934/cpaa.2022012
[6]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-periodic binary sequences. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016
[7]

Yaping Wu, Qian Xu. The existence and structure of large spiky steady states for S-K-T competition systems with cross-diffusion. Discrete and Continuous Dynamical Systems, 2011, 29 (1) : 367-385. doi: 10.3934/dcds.2011.29.367
[8]

Fadoua El Moustaid, Amina Eladdadi, Lafras Uys. Modeling bacterial attachment to surfaces as an early stage of biofilm development. Mathematical Biosciences & Engineering, 2013, 10 (3) : 821-842. doi: 10.3934/mbe.2013.10.821
[9]

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

Nikolaz Gourmelon. Generation of homoclinic tangencies by $C^1$-perturbations. Discrete and Continuous Dynamical Systems, 2010, 26 (1) : 1-42. doi: 10.3934/dcds.2010.26.1
[11]

Johannes Giannoulis. Transport and generation of macroscopically modulated waves in diatomic chains. Conference Publications, 2011, 2011 (Special) : 485-494. doi: 10.3934/proc.2011.2011.485
[12]

Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.

[13]

Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17
[14]

J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413
[15]

John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16.

[16]

Roberto De Leo, James A. Yorke. The graph of the logistic map is a tower. Discrete and Continuous Dynamical Systems, 2021, 41 (11) : 5243-5269. doi: 10.3934/dcds.2021075
[17]

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

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

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

Roy H. Goodman. NLS bifurcations on the bowtie combinatorial graph and the dumbbell metric graph. Discrete and Continuous Dynamical Systems, 2019, 39 (4) : 2203-2232. doi: 10.3934/dcds.2019093

2021 Impact Factor: 1.41

Tools

Metrics

  • PDF downloads (58)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy