Generalization of core percolation on complex networks

N. Azimi-Tafreshi, S. Osat, and S. N. Dorogovtsev
Phys. Rev. E 99, 022312 – Published 22 February 2019

Abstract

We introduce a k-leaf removal algorithm as a generalization of the so-called leaf removal algorithm. In this pruning algorithm, vertices of degree smaller than k, together with their first nearest neighbors and all incident edges, are progressively removed from a random network. As the result of this pruning the network is reduced to a subgraph which we call the Generalized k-core (Gk-core). Performing this pruning for the sequence of natural numbers k, we decompose the network into a hierarchy of progressively nested Gk-cores. We present an analytical framework for description of Gk-core percolation for undirected uncorrelated networks with arbitrary degree distributions (configuration model). To confirm our results, we also derive rate equations for the k-leaf removal algorithm which enable us to obtain the structural characteristics of the Gk-cores in another way. Also we apply our algorithm to a number of real-world networks and perform the Gk-core decomposition for them.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
2 More
  • Received 1 August 2018
  • Revised 9 December 2018

DOI:https://doi.org/10.1103/PhysRevE.99.022312

©2019 American Physical Society

Physics Subject Headings (PhySH)

NetworksStatistical Physics & Thermodynamics

Authors & Affiliations

N. Azimi-Tafreshi

  • Physics Department, Institute for Advanced Studies in Basic Sciences, 45195-1159 Zanjan, Iran

S. Osat

  • Quantum Complexity Science Initiative, Skolkovo Institute of Science and Technology, Skoltech Building 3, Moscow, 143026, Russia

S. N. Dorogovtsev

  • Departamento de Física da Universidade de Aveiro and I3N, Campus Universitário de Santiago, 3810-193 Aveiro, Portugal and A. F. Ioffe Physico-Technical Institute, 194021 St. Petersburg, Russia

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 99, Iss. 2 — February 2019

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×