A k-shell decomposition structural entropy of complex networks

Structural entropy is a powerful tool for quantifying the structural complexity of complex networks and answering the question of how complex these networks are. In this paper, a new structural entropy measure for complex networks, based on the k-shell method, is proposed to fill the gaps left by traditional node-based structural entropy and statistical physics entropy, quantifying the structural complexity of networks based on the distribution of nodes among different shells. The effectiveness of k-shell decomposition structural entropy is validated in networks with different structures generated by the Erdős–Rényi and Barabási–Albert models. We find that networks generated by the Barabási–Albert model tend to have higher k-shell decomposition structural entropy. In contrast, networks generated by the Erdős–Rényi model exhibit oscillations in k-shell decomposition structural entropy, which gradually stabilize as the network size increases. We also find that the frequency of these oscillations in the k-shell decomposition structural entropy for networks generated by the Erdős–Rényi model is related to the linking probability in the model. These oscillations arise due to ’phase transitions’ in the distribution of nodes among shells during the network’s growth process, a phenomenon distinct from existing entropy measures of complex networks. This finding shows that the proposed k-shell decomposition structural entropy is fundamentally different from degree-based and betweenness-based structural entropy. Additionally, the k-shell decomposition structural entropy has been applied to measure the structural complexity of real-world networks. We find that even though the Yeast Interaction network and the Twitter social network have different sizes and originate from different systems, they exhibit very similar k-shell decomposition structural entropy. In other words, the k-shell decomposition structural entropy provides unique insights into structural changes during network growth. Unlike traditional measures, k-shell decomposition structural entropy is not extensive with network size growth and focuses on the shell-topological structure of networks. All of these results demonstrate that the k-shell decomposition structural entropy is a new and useful tool for the structural analysis of complex networks.