Loading [MathJax]/jax/output/SVG/jax.js
Search Advanced

Networks and Heterogeneous Media

2008, Volume 3, Issue 2: 277-294. doi: 10.3934/nhm.2008.3.277
Previous Article Next Article

Augmenting k-core generation with preferential attachment

  • 1.
    Faculty of Informatics, Universität Karlsruhe (TH), 78131 Karlsruhe
  • Received: 01 August 2007 Revised: 01 March 2008

  • Primary: 05C85, 05C80; Secondary: 05C75.

  • 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.

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

    Related Papers:

    [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] 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
    [3] Thomas Geert de Jong, Georg Prokert, Alef Edou Sterk . Reaction–diffusion transport into core-shell geometry: Well-posedness and stability of stationary solutions. Networks and Heterogeneous Media, 2025, 20(1): 1-14. doi: 10.3934/nhm.2025001
    [4] Dilip Sarkar, Shridhar Kumar, Pratibhamoy Das, Higinio Ramos . Higher-order convergence analysis for interior and boundary layers in a semi-linear reaction-diffusion system networked by a k-star graph with non-smooth source terms. Networks and Heterogeneous Media, 2024, 19(3): 1085-1115. doi: 10.3934/nhm.2024048
    [5] Sergei Avdonin, Julian Edward . An inverse problem for quantum trees with observations at interior vertices. Networks and Heterogeneous Media, 2021, 16(2): 317-339. doi: 10.3934/nhm.2021008
    [6] Riccardo Adami, Ivan Gallo, David Spitzkopf . Ground states for the NLS on non-compact graphs with an attractive potential. Networks and Heterogeneous Media, 2025, 20(1): 324-344. doi: 10.3934/nhm.2025015
    [7] Vaibhav Mehandiratta, Mani Mehra, Günter Leugering . Existence results and stability analysis for a nonlinear fractional boundary value problem on a circular ring with an attached edge : A study of fractional calculus on metric graph. Networks and Heterogeneous Media, 2021, 16(2): 155-185. doi: 10.3934/nhm.2021003
    [8] Laura M. Pérez, Jean Bragard, Hector Mancini, Jason A. C. Gallas, Ana M. Cabanas, Omar J. Suarez, David Laroze . Effect of anisotropies on the magnetization dynamics. Networks and Heterogeneous Media, 2015, 10(1): 209-221. doi: 10.3934/nhm.2015.10.209
    [9] A. Chauviere, T. Hillen, L. Preziosi . Modeling cell movement in anisotropic and heterogeneous network tissues. Networks and Heterogeneous Media, 2007, 2(2): 333-357. doi: 10.3934/nhm.2007.2.333
    [10] Liuchao Xiao, Wenbo Li, Leilei Wei, Xindong Zhang . A fully discrete local discontinuous Galerkin method for variable-order fourth-order equation with Caputo-Fabrizio derivative based on generalized numerical fluxes. Networks and Heterogeneous Media, 2023, 18(2): 532-546. doi: 10.3934/nhm.2023022
  • 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.


  • This article has been cited by:

    1. Daniel R. Wuellner, Soumen Roy, Raissa M. D’Souza, Resilience and rewiring of the passenger airline networks in the United States, 2010, 82, 1539-3755, 10.1103/PhysRevE.82.056101
    2. Irene Malvestio, Alessio Cardillo, Naoki Masuda, Interplay between k
    -core and community structure in complex networks, 2020, 10, 2045-2322, 10.1038/s41598-020-71426-8
    3. Vishesh Karwa, Michael J. Pelsmajer, Sonja Petrović, Despina Stasi, Dane Wilburne, Statistical models for cores decomposition of an undirected random graph, 2017, 11, 1935-7524, 10.1214/17-EJS1235
    4. Ahmet Erdem Sarıyüce, Buğra Gedik, Gabriela Jacques-Silva, Kun-Lung Wu, Ümit V. Çatalyürek, Incremental k-core decomposition: algorithms and evaluation, 2016, 25, 1066-8888, 425, 10.1007/s00778-016-0423-8
    5. Jiaojiao Jiang, Shuiqiao Yang, Sanjay Jha, Network Growth From Global and Local Influential Nodes, 2022, 9, 2327-4697, 2549, 10.1109/TNSE.2022.3165528
    6. Ahmet Erdem Saríyüce, Buğra Gedik, Gabriela Jacques-Silva, Kun-Lung Wu, Ümit V. Çatalyürek, Streaming algorithms for k-core decomposition, 2013, 6, 2150-8097, 433, 10.14778/2536336.2536344
    7. Shicheng Gao, Jie Xu, Xiaosen Li, Fangcheng Fu, Wentao Zhang, Wen Ouyang, Yangyu Tao, Bin Cui, 2022, K-core decomposition on super large graphs with limited resources, 9781450387132, 413, 10.1145/3477314.3507064
  • Reader Comments
  • © 2008 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
Networks and Heterogeneous Media
1.2 1.8

Metrics

Article views(4819) PDF downloads(62) Cited by(7)

Preview PDF
Download XML
Export Citation
Article outline
Abstract

Other Articles By Authors

Related pages

Tools

Copyright © AIMS Press

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog