Hypergraph Motifs: Concepts, Algorithms, and Discoveries

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 21
  • Download : 0
Hypergraphs naturally represent group interactions, which are omnipresent in many domains: collaborations of researchers, co-purchases of items, joint interactions of proteins, to name a few. In this work, we propose tools for answering the following questions in a systematic manner: (Q1) what are structural design principles of real-world hypergraphs? (Q2) how can we compare local structures of hypergraphs of di.erent sizes? (Q3) how can we identify domains which hypergraphs are from? We first define hypergraph motifs (h-motifs), which describe the connectivity patterns of three connected hyperedges. Then, we define the significance of each h-motif in a hypergraph as its occurrences relative to those in properly randomized hypergraphs. Lastly, we define the characteristic profile (CP) as the vector of the normalized significance of every h-motif. Regarding Q1, we find that h-motifs' occurrences in 11 real-world hypergraphs from 5 domains are clearly distinguished from those of randomized hypergraphs. In addition, we demonstrate that CPs capture local structural patterns unique to each domain, and thus comparing CPs of hypergraphs addresses Q2 and Q3. Our algorithmic contribution is to propose MoCHy, a family of parallel algorithms for counting h-motifs' occurrences in a hypergraph. We theoretically analyze their speed and accuracy, and we show empirically that the advanced approximate version MoCHy-A(+) is up to 25 x more accurate and 32. faster than the basic approximate and exact versions, respectively.
Publisher
ASSOC COMPUTING MACHINERY
Issue Date
2020-07
Language
English
Article Type
Article
Citation

PROCEEDINGS OF THE VLDB ENDOWMENT, v.13, no.11, pp.2256 - 2269

ISSN
2150-8097
DOI
10.14778/3407790.3407823
URI
http://hdl.handle.net/10203/276951
Appears in Collection
RIMS Journal Papers
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0