Nested Subgraphs of Complex Networks

Abstract

We analytically explore the scaling properties of a general class of nested subgraphs in complex networks, which includes the $K$-core and the $K$-scaffold, among others. We name such class of subgraphs $K$-nested subgraphs due to the fact that they generate families of subgraphs such that $...S_{K+1}(\mathcal{G})\subseteq S_K(\mathcal{G})\subseteq S_{K-1}(\mathcal{G})...$. Using the so-called {\em configuration model} it is shown that any family of nested subgraphs over a network with diverging second moment and finite first moment has infinite elements (i.e. lacking a percolation threshold). Moreover, for a scale-free network with the above properties, we show that any nested family of subgraphs is self-similar by looking at the degree distribution. Both numerical simulations and real data are analyzed and display good agreement with our theoretical predictions.

6 pages, 4 figures

References in corpus (11)

• Uncovering the overlapping community structure of complex networks in nature and society
• Random graphs with arbitrary degree distributions and their applications
• Network robustness and fragility: Percolation on random graphs
• Critical phenomena in complex networks
• Self-similar community structure in organisations
• Self-similarity of complex networks
• k-core organization of complex networks
• Skeleton and fractal scaling in complex networks
• k-core decomposition: a tool for the visualization of large scale networks
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• K-Scaffold subgraphs of Complex networks

Cited by in corpus (4)

• k-core organization of complex networks
• Heterogeneous-k-core versus Bootstrap Percolation on Complex Networks
• Detection of the elite structure in a virtual multiplex social system by means of a generalized $K$-core
• Universality in percolation of arbitrary Uncorrelated Nested Subgraphs