Counting Hypertriangles through Hypergraph Orientations
Daniel Paul-Pena, Vaishali Surianarayanan, Deeparnab Chakrabarty, C. Seshadhri
原文摘要
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 new 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 faster on all but one small instance, achieving speedups of up to 100x, and is 6-100x more memory-efficient than existing state-of-the-art methods.
cs.DS · cs.DB · cs.SI