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 & 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 & 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 & Continuous Dynamical Systems - A, 2010, 27 (4) : 1259-1282. doi: 10.3934/dcds.2010.27.1259
[3]

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 & Continuous Dynamical Systems - B, 2012, 17 (6) : 1605-1638. doi: 10.3934/dcdsb.2012.17.1605
[4]

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

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

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

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

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

[9]

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

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

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

[12]

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

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

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

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

Mario Roy, Mariusz Urbański. Random graph directed Markov systems. Discrete & Continuous Dynamical Systems - A, 2011, 30 (1) : 261-298. doi: 10.3934/dcds.2011.30.261
[17]

Dominique Zosso, Braxton Osting. A minimal surface criterion for graph partitioning. Inverse Problems & Imaging, 2016, 10 (4) : 1149-1180. doi: 10.3934/ipi.2016036
[18]

Mario Jorge Dias Carneiro, Rafael O. Ruggiero. On the graph theorem for Lagrangian minimizing tori. Discrete & Continuous Dynamical Systems - A, 2018, 38 (12) : 6029-6045. doi: 10.3934/dcds.2018260
[19]

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

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

2018 Impact Factor: 0.871

Tools

Metrics

  • PDF downloads (12)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences