Ranking cliques in higher-order complex networks

Yang Zhao; Cong Li; Dinghua Shi; Guanrong Chen; Xiang Li

doi:10.1063/5.0147721

Ranking cliques in higher-order complex networks

Chaos. 2023 Jul 1;33(7):073139. doi: 10.1063/5.0147721.

Authors

Yang Zhao¹, Cong Li¹, Dinghua Shi², Guanrong Chen³, Xiang Li^{4

5}

Affiliations

¹ Adaptive Networks and Control Lab, Department of Electronic Engineering, School of Information Science and Technology, Fudan University, Shanghai 200433, China.
² Department of Mathematics, College of Science, Shanghai University, Shanghai 200444, China.
³ Department of Electrical Engineering, City University of Hong Kong, Hong Kong 999077, China.
⁴ Institute of Complex Networks and Intelligent Systems, Shanghai Research Institute for Intelligent Autonomous Systems, Tongji University, Shanghai 201210, China.
⁵ State Key Laboratory of Intelligent Autonomous Systems, the Frontiers Science Center for Intelligent Autonomous Systems, Tongji University, Shanghai 201210, China.

PMID: 37463096
DOI: 10.1063/5.0147721

Abstract

Traditional network analysis focuses on the representation of complex systems with only pairwise interactions between nodes. However, the higher-order structure, which is beyond pairwise interactions, has a great influence on both network dynamics and function. Ranking cliques could help understand more emergent dynamical phenomena in large-scale complex networks with higher-order structures, regarding important issues, such as behavioral synchronization, dynamical evolution, and epidemic spreading. In this paper, motivated by multi-node interactions in a topological simplex, several higher-order centralities are proposed, namely, higher-order cycle (HOC) ratio, higher-order degree, higher-order H-index, and higher-order PageRank (HOP), to quantify and rank the importance of cliques. Experiments on both synthetic and real-world networks support that, compared with other traditional network metrics, the proposed higher-order centralities effectively reduce the dimension of a large-scale network and are more accurate in finding a set of vital nodes. Moreover, since the critical cliques ranked by the HOP and the HOC are scattered over a complex network, the HOP and the HOC outperform other metrics in ranking cliques that are vital in maintaining the network connectivity, thereby facilitating network dynamical synchronization and virus spread control in applications.