$(k,q)$-core decomposition of hypergraphs

Abstract

In complex networks, many elements interact with each other in different ways. A hypergraph is a network in which group interactions occur among more than two elements. In this study, first, we propose a method to identify influential subgroups in hypergraphs, named $(k,q)$-core decomposition. The $(k,q)$-core is defined as the maximal subgraph in which each vertex has at least $k$ hypergraph degrees \textit{and} each hyperedge contains at least $q$ vertices. The method contains a repeated pruning process until reaching the $(k,q)$-core, which shares similarities with a widely used $k$-core decomposition technique in a graph. Second, we analyze the pruning dynamics and the percolation transition with theoretical and numerical methods in random hypergraphs. We set up evolution equations for the pruning process, and self-consistency equations for the percolation properties. Based on our theory, we find that the pruning process generates a hybrid percolation transition for either $k\ge 3$ \textit{or} $q\ge 3$. The critical exponents obtained theoretically are confirmed with finite-size scaling analysis. Next, when $k=q=2$, we obtain a unconventional degree-dependent critical relaxation dynamics analytically and numerically. Finally, we apply the $(k,q)$-core decomposition to a real coauthorship dataset and recognize the leading groups at an early stage.

27 pages, 10 figures

References in corpus (8)

• The physics of higher-order interactions in complex systems
• Abrupt Desynchronization and Extensive Multistability in Globally Coupled Oscillator Simplices
• Random walks on hypergraphs
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• Abrupt phase transition of epidemic spreading in simplicial complexes
• Simplicial SIS model in scale-free uniform hypergraph
• Heterogeneous-k-core versus Bootstrap Percolation on Complex Networks
• Critical behavior of $k$-core percolation: Numerical studies

Cited by in corpus (7)

• The theory of percolation on hypergraphs
• Hyper-cores promote localization and efficient seeding in higher-order processes
• Contagion dynamics on hypergraphs with nested hyperedges
• The nature of hypergraph $k$-core percolation problems
• Global topological synchronization of weighted simplicial complexes
• Exploring Cohesive Subgraphs in Hypergraphs: The (k,g)-core Approach
• Growing Hypergraphs with Preferential Linking