Computing Motifs in Hypergraphs Duarte Nóbrega and and Pedro Ribeiro 2024

Abstract

Motifs are overrepresented and statistically significant sub-patterns in a network, whose identification is relevant to uncover its underlying functional units. Recently, its extraction has been performed on higher-order networks, but due to the complexity arising from polyadic interactions, and the similarity with known computationally hard problems, its practical application is limited. Our main contribution is a novel approach for hyper-subgraph census and higher-order motif discovery, allowing for motifs with sizes 3 or 4 to be found efficiently, in real-world scenarios. It is consistently an order of magnitude faster than a baseline state-of-art method, while using less memory and supporting a wider range of base algorithms.

Keywords

Hypergraphs; Hyper-subgraphs; Motifs; Subgraph census

Digital Object Identifier (DOI)

doi 10.1007/978-3-031-57515-0_5

Publication in PDF format

pdf Download PDF

Software

software

Journal/Conference/Book

15th Conference on Complex Networks

Reference (text)

Duarte Nóbrega and and Pedro Ribeiro. Computing Motifs in Hypergraphs. Proceedings of the 15th Conference on Complex Networks (CompleNet), pp. 55-70, Springer, Exeter, UK, April, 2024.

Bibtex

@inproceedings{ribeiro-COMPLENET2024,
  author = {Duarte Nóbrega and and Pedro Ribeiro},
  title = {Computing Motifs in Hypergraphs},
  doi = {10.1007/978-3-031-57515-0_5},
  booktitle = {15th Conference on Complex Networks},
  pages = {55-70},
  publisher = {Springer},
  month = {April},
  year = {2024}
}