$(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.

arXiv comment27 pages, 10 figures

References in corpus (30)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Random graphs with arbitrary degree distributions and their applications
• Identification of influential spreaders in complex networks
• Evolution of networks
• Networks beyond pairwise interactions: structure and dynamics
• The physics of higher-order interactions in complex systems
• Simplicial models of social contagion
• k-core organization of complex networks
• Evolutionary dynamics of higher-order interactions in social networks
• Small vulnerable sets determine large network cascades in power grids
• Explosive higher-order Kuramoto dynamics on simplicial complexes
• Higher-order interactions in complex networks of phase oscillators promote abrupt synchronization switching
• 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 Activity Driven Model
• Coupled Dynamics on Hypergraphs: Master Stability of Steady States and Synchronization
• Higher-order percolation processes on multiplex hypergraphs
• Simplicial SIS model in scale-free uniform hypergraph
• Heterogeneous-k-core versus Bootstrap Percolation on Complex Networks
• Covering Problems and Core Percolations on Hypergraphs
• Critical dynamics of the k-core pruning process
• Social confinement and mesoscopic localization of epidemics on networks
• Betweenness centrality of teams in social networks
• Generalized Two-mode Cores
• Homological percolation transitions in growing simplicial complexes
• 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