Uncovering High-Order Cohesive Structures: Efficient ( k , g ) (k,g) -Core Computation and Decomposition for Large Hypergraphs DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X
Dahee Kim § , Hyewon Kim § , Song Kim § , Minseok Kim § , Junghoon Kim § , Yeon-Chang Lee § , Sungsu Lim † · 2025
Read Uncovering High-Order Cohesive Structures: Efficient ( k , g ) (k,g) -Core Computation and Decomposition for Large Hypergraphs DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X by Dahee Kim § , Hyewon Kim § , Song Kim § , Minseok Kim § , Junghoon Kim § , Yeon-Chang Lee § , Sungsu Lim † (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-08328.txt.
Introduction
Dahee Kim and co-authors tackle cohesive groups in hypergraphs in a 2025 paper. Hypergraphs model links among many nodes at once, and finding tight subgroups in them gives insight into complex networks.
Picking the right parameters for such a search is an open problem. Rather than scan the whole graph each time, the team builds an index that can fetch the matching cohesive cores on demand. Their target structures are defined by two parameters that balance how connected each node and each group must be. Wide tests on real networks showed the index beats past methods on speed and quality of retrieval. The tool suits live analysis of huge hypergraphs.
Catalog record
| CREATOR | Dahee Kim § , Hyewon Kim § , Song Kim § , Minseok Kim § , Junghoon Kim § , Yeon-Chang Lee § , Sungsu Lim † |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-08328
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Uncovering High-Order Cohesive Structures: Efficient ( k , g ) (k,g) -Core Computation and Decomposition for Large Hypergraphs DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 Dahee Kim § , Hyewon Kim § , Song Kim § , Minseok Kim § , Junghoon Kim § , Yeon-Chang Lee § , Sungsu Lim † Abstract . Hypergraphs, increasingly utilised to model complex and diverse relationships in modern networks, have gained significant attention for representing intricate higher-order interactions. Among various challenges, cohesive subgraph discovery is one of the fundamental problems and offers deep insights into these structures, yet the task of selecting appropriate parameters is an open question. To address this question, we aim to design an efficient indexing structure to retrieve cohesive subgraphs in an online manner. The main idea is to enable the discovery of corresponding structures within a reasonable time without the need for exhaustive graph traversals. Our method enables faster and more effective retrieval of cohesive structures, which supports decision-making in applications that require online analysis of large-scale hypergraphs. Through extensive experiments on real-world networks, we demonstrate the superiority of our proposed indexing technique. * * footnotetext: Corresponding author 1. INTRODUCTION Graphs are a fundamental tool for modelling diverse relationships in the real-world, such as social sciences, biology, and transaction ( Harary and Norman 1953 ; Mason and Verwoerd 2007 ; Jack et al. 2013 ) . Graph analysis enables revealing the structural properties of network by identifying interconnected entities and meaningful patterns ( Wellman 1983 ) . One of the key tasks in graph analysis is to identify cohesive subgraphs, which are subsets of nodes that exhibit stronger internal connectivity than their connections to the rest of the graph ( Benson et al. 2018a ; Malliaros et al. 2020 ) . These cohesive subgraphs are useful in numerous applications, including community detection in social networks ( Cohen 2008 ) , identification of functional modules in biological systems ( Salem et al. 2012 ) , and analysis of user groups in e-commerce ( Xia et al. 2021 ) . Numerous approaches have been widely used in traditional graphs to identify cohesive subgraphs, such as the k -core ( Malliaros et al. 2020 ) , modularity-based clustering ( Girvan and Newman 2002 ) , and spectral partitioning ( Günnemann et al. 2013 ) . However, existing approaches primarily handle pairwise relationships, relying on indirect representations of higher-order structures such as motifs and cliques, for relationships between multiple entities. While these methods provide a partial representation of these complex structures, literatures ( Gao et al. 2022 ; Li et al. 2023 ; Xia et al. 2021 ) suggest that explicitly incorporating higher-order relationships can significantly enhance performance in downstream tasks, including co-authoring analysis, co-purchasing predictions, and group participation modelling. To better capture higher-order structures beyond pairwise interactions, hypergraphs have emerged as a more flexible structure where a single hyperedge can connect multiple nodes simultaneously ( Berge 1984 ) . Various models ( Arafat et al. 2023 ; Bu et al. 2023 ; Leng et al. 2013 ) have been proposed for discovering cohesive subhypergraphs, where a subhypergraph refers to the substructure of a hypergraph formed by a subset of nodes and the hyperedges that contain those nodes. The k -hypercore ( Leng et al. 2013 ) represents the first extension of the k -core ( Seidman 1983 ) to hypergraphs. However, k -hypercore only consider neighbour constraint, it often produces overly broad results, including nodes with weak connectivity with each other. Subsequently, the (k,d) -core ( Arafat et al. 2023 ) was introduced, which incorporates a degree constraint at the individual node level to identify more cohesive subhypergraphs. However, this model assumes that if any node in a hyperedge is removed, the hyperedge containing the removed node must also be discarded. This assumption does not always hold in real-world scenarios, where hyperedge can remain meaningful even if some nodes are removed, leading to unnecessary information loss ( Bu et al. 2023 ) . Furthermore, the (k,d) -core may produce subhypergraphs with weak interconnectivity since it focuses primarily on the strength of individual node, which may miss important patterns of connectivity between neighbour nodes. For example, if nodes are frequently involved together in multiple groups ( i.e. , hyperedges), their relationship may still be significant, even when their individual participation ( i.e. , degree) is low. This co-occurrence pattern can revel latent structural dependencies that are not captured by degree-based constraints alone. Therefore, this paper aims to incorporate the concept of “co-occurrence,” which accounts for the frequency of repeated interactions between nodes in hypergraphs. These interactions reflect the strength of group relationships, as demonstrated in Example 1 , enabling the identification of stronger and more structurally cohesive subhypergraphs. Figure 1 . Toy example Example 0. Consider a research-collaboration platform where each hyperedge denotes a team project, and each node represents a researcher as shown in Figure 1 . Our goal is to discover subgroups of researchers who collaborate frequently, thus enabling recommendation of future collaborations. Suppose every researcher in the subgroup is required to have participated in at least two team projects. If we rely solely on the number of team projects that each researcher participates in (i.e., degree-based approach), we would select a subgroup that includes members x_{1},x_{3},x_{4},x_{5},x_{6},x_{8} , and x_{9} . Although x_{1} and x_{8} both meet the participation requirement, they collaborate with completely different sets of researchers. In contrast, if we account for co-occurrence, we can identify two subgroups: \{x_{1},x_{3},x_{4}\} , and \{x_{6},x_{7},x_{8}\} . Members of each subgroup consistently collaborate with each other across all of their projects. Such co-occurrence patterns capture groups that are strongly interconnected, whereas relying on degree may lead to identifying groups with weaker interconnections. Motivated by this observation, we propose the (k,g) -core, a novel model for discovering cohesive subhypergraphs by incorporating co-occurrence. Compared with the (k,d) -core ( Arafat et al. 2023 ) that focuses on individual node strength, the (k,g) -core captures more strongly connected groups by considering co-occurrence, a condition that requires node pairs to frequently appear together in multiple hyperedges. Under the (k,g) -core model, we design two key algorithms: (i) the Efficient Peeling Algorithm (Section 3 ), which ensures memory efficiency and scalability by maintaining only essential information during (k,g) -core computation, and (ii) the Bucket-based Coreness Algorithm (Section 4 ), which decomposes a hypergraph into all possible (k,g) -cores. Application. The (k,g) -core model can be applied in a variety of domains, some notable applications are as follows: • Team formation : Team formation is an important task in organizational and research collaboration settings ( Li and Shan 2010 ) . Typically, each hyperedge represents a group of researchers who collaborate on publications or projects. The primary advantage of using (k,g) -cores is that it prevents teams from being formed by researchers with high individual engagement but low shared collaboration history. This helps to avoid the formation of teams with weak internal cohesion, resulting in subgroups of members who demonstrate stable and reliable collaborative relationships. • Market basket analysis : Market basket analysis is a widely used technique for marketers to create