Interplay between $k$-core and community structure in complex networks

Abstract

The organisation of a network in a maximal set of nodes having at least $k$ neighbours within the set, known as $k$-core decomposition, has been used for studying various phenomena. It has been shown that nodes in the innermost $k$-shells play a crucial role in contagion processes, emergence of consensus, and resilience of the system. It is known that the $k$-core decomposition of many empirical networks cannot be explained by the degree of each node alone, or equivalently, random graph models that preserve the degree of each node (i.e., configuration model). Here we study the $k$-core decomposition of some empirical networks as well as that of some randomised counterparts, and examine the extent to which the $k$-shell structure of the networks can be accounted for by the community structure. We find that preserving the community structure in the randomisation process is crucial for generating networks whose $k$-core decomposition is close to the empirical one. We also highlight the existence, in some networks, of a concentration of the nodes in the innermost $k$-shells into a small number of communities.

34 pages, 4 tables, and 15 figures. Main + supplementary. Final version accepted for publication

References in corpus (14)

• Fast unfolding of communities in large networks
• The NumPy array: a structure for efficient numerical computation
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• The Rich-Club Phenomenon In The Internet Topology
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Triadic closure as a basic generating mechanism of communities in complex networks
• Nestedness in complex networks: Observation, emergence, and implications
• Emergence of communities in weighted networks
• Spectral coarse-graining of complex networks
• An Empirical Study of the Relation Between Community Structure and Transitivity
• Hierarchical benchmark graphs for testing community detection algorithms