Beyond Trivial Edges: A Fractional Approach to Cohesive Subgraph Detection in Hypergraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908659806633984 |
|---|---|
| author | Kim, Hyewon Shin, Woocheol Kim, Dahee Kim, Junghoon Lim, Sungsu Jeong, Hyunji |
| author_facet | Kim, Hyewon Shin, Woocheol Kim, Dahee Kim, Junghoon Lim, Sungsu Jeong, Hyunji |
| contents | Hypergraphs serve as a powerful tool for modeling complex relationships across domains like social networks, transactions, and recommendation systems. The (k,g)-core model effectively identifies cohesive subgraphs by assessing internal connections and co-occurrence patterns, but it is susceptible to inflated cohesiveness due to trivial hyperedges. To address this, we propose the $(k,g,p)$-core model, which incorporates the relative importance of hyperedges for more accurate subgraph detection. We develop both Naïve and Advanced pruning algorithms, demonstrating through extensive experiments that our approach reduces the execution frequency of costly operations by 51.9% on real-world datasets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_20350 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Beyond Trivial Edges: A Fractional Approach to Cohesive Subgraph Detection in Hypergraphs Kim, Hyewon Shin, Woocheol Kim, Dahee Kim, Junghoon Lim, Sungsu Jeong, Hyunji Social and Information Networks Hypergraphs serve as a powerful tool for modeling complex relationships across domains like social networks, transactions, and recommendation systems. The (k,g)-core model effectively identifies cohesive subgraphs by assessing internal connections and co-occurrence patterns, but it is susceptible to inflated cohesiveness due to trivial hyperedges. To address this, we propose the $(k,g,p)$-core model, which incorporates the relative importance of hyperedges for more accurate subgraph detection. We develop both Naïve and Advanced pruning algorithms, demonstrating through extensive experiments that our approach reduces the execution frequency of costly operations by 51.9% on real-world datasets. |
| title | Beyond Trivial Edges: A Fractional Approach to Cohesive Subgraph Detection in Hypergraphs |
| topic | Social and Information Networks |
| url | https://arxiv.org/abs/2410.20350 |