Interplay between $$k$$-core and community structure in complex networks
Irene Malvestio, Alessio Cardillo, Naoki Masuda
Abstract
Abstract The organisation of a network in a maximal set of nodes having at least k neighbours within the set, known as $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -core decomposition, has been used for studying various phenomena. It has been shown that nodes in the innermost $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -shells play a crucial role in contagion processes, emergence of consensus, and resilience of the system. It is known that the $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -core decomposition of some empirical networks as well as that of some randomised counterparts, and examine the extent to which the $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -shells into a small number of communities.