(k,q)-core decomposition of hypergraphs

Jongshin Lee, Kwang Il Goh, Deok Sun Lee, B. Kahng

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

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

Original languageEnglish
Article number113645
JournalChaos, Solitons and Fractals
Volume173
DOIs
Publication statusPublished - 2023 Aug

Bibliographical note

Funding Information:
This work was supported by the National Research Foundation of Korea with Grant No. NRF-2014R1A3A2069005 (B.K.), NRF-2019R1A 2C1003486 (D.-S.L.), NRF-2020R1A2C2003669 (K.-I.G.), KENTECH Research Grant No. KRG2021-01-007 at Korea Institute of Energy Technology (B.K.), and a KIAS Individual Grant No. CG079901 at Korea Institute for Advanced Study (D.-S.L.).

Publisher Copyright:
© 2023 Elsevier Ltd

Keywords

  • Critical dynamics
  • Higher-order networks
  • Hybrid phase transition
  • Hypergraph
  • Percolation

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Mathematical Physics
  • General Physics and Astronomy
  • Applied Mathematics

Fingerprint

Dive into the research topics of '(k,q)-core decomposition of hypergraphs'. Together they form a unique fingerprint.

Cite this