(k, q)-core decomposition of hypergraphs

초록

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 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 > 3 or q > 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.

키워드