Generalization of core percolation on complex networks
| Autor: | Sergey N. Dorogovtsev, N. Azimi-Tafreshi, Saeed Osat |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
Random graph Physics - Physics and Society Sequence Degree (graph theory) Generalization FOS: Physical sciences Natural number Disordered Systems and Neural Networks (cond-mat.dis-nn) Physics and Society (physics.soc-ph) Condensed Matter - Disordered Systems and Neural Networks Complex network 01 natural sciences 010305 fluids & plasmas Percolation 0103 physical sciences Pruning (decision trees) 010306 general physics Mathematics |
| Zdroj: | Physical Review E. 99 |
| ISSN: | 2470-0053 2470-0045 |
| Popis: | 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. Comment: 9 pages, 9 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|