Counting hypertriangles through hypergraph orientations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909983276269568 |
|---|---|
| author | Paul-Pena, Daniel Surianarayanan, Vaishali Chakrabarty, Deeparnab Seshadhri, C. |
| author_facet | Paul-Pena, Daniel Surianarayanan, Vaishali Chakrabarty, Deeparnab Seshadhri, C. |
| contents | Counting the number of small patterns is a central task in network analysis. While this problem is well studied for graphs, many real-world datasets are naturally modeled as hypergraphs, motivating the need for efficient hypergraph motif counting algorithms. In particular, we study the problem of counting hypertriangles - collections of three pairwise-intersecting hyperedges. These hypergraph patterns have a rich structure with multiple distinct intersection patterns unlike graph triangles.
Inspired by classical graph algorithms based on orientations and degeneracy, we develop a theoretical framework that generalizes these concepts to hypergraphs and yields provable algorithms for hypertriangle counting. We implement these ideas in DITCH (Degeneracy Inspired Triangle Counter for Hypergraphs) and show experimentally that it is 10-100x faster and more memory efficient than existing state-of-the-art methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_03573 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Counting hypertriangles through hypergraph orientations Paul-Pena, Daniel Surianarayanan, Vaishali Chakrabarty, Deeparnab Seshadhri, C. Data Structures and Algorithms Databases Social and Information Networks Counting the number of small patterns is a central task in network analysis. While this problem is well studied for graphs, many real-world datasets are naturally modeled as hypergraphs, motivating the need for efficient hypergraph motif counting algorithms. In particular, we study the problem of counting hypertriangles - collections of three pairwise-intersecting hyperedges. These hypergraph patterns have a rich structure with multiple distinct intersection patterns unlike graph triangles. Inspired by classical graph algorithms based on orientations and degeneracy, we develop a theoretical framework that generalizes these concepts to hypergraphs and yields provable algorithms for hypertriangle counting. We implement these ideas in DITCH (Degeneracy Inspired Triangle Counter for Hypergraphs) and show experimentally that it is 10-100x faster and more memory efficient than existing state-of-the-art methods. |
| title | Counting hypertriangles through hypergraph orientations |
| topic | Data Structures and Algorithms Databases Social and Information Networks |
| url | https://arxiv.org/abs/2601.03573 |