We propose Hypergraph Motifs (h-motifs)
, whose occurrences capture local structural patterns of real-world hypergraphs.
describe connectivity patterns of three connected hyperedges with the following properties:
MoCHy (Motif Counting in Hypergraphs)
- Exhaustive: h-motifs capture connectivity patterns of all possible three connected hyperedges
- Unique: connectivity pattern of any three connected hyperedges is captured by exactly one h-motif
- Size independent: h-motifs capture connectivity patterns independently of the sizes of hyperedges
is a family of parallel algorithms for counting h-motifs' occurrences in a hypergraph.
- MoCHy-E (MoCHy Exact) exactly counts the instances of each h-motif.
- MoCHy-A (MoCHy Approximate) approximately counts the instances of each h-motif.
- The advanced approximate version MoCHy-A+ is up to 25X more accurate than MoCHy-A, and it is up to 32X faster than MoCHy-E.
Hypergraph Motifs: Concepts, Algorithms, and Discoveries
Geon Lee, Jihoon Ko, and Kijung Shin
The source code used in the paper is available. [Code]
We use the following 11 real-world hypergraphs from 5 different domains after removing duplicated hyperedges: