Census and Analysis of Higher-Order Interactions in Real-World Hypergraphs - Xihang Meng; Xuemeng Zhai; Gaolei Fei; Sheng Wen; Guangmin Hu (Big Data Mining and Analytics)
Complex systems can be more accurately described by higher-order interactions among multiple units. Hypergraphs excel at depicting these interactions, surpassing the binary limitations of traditional graphs. However, retrieving valuable information from hypergraphs is often challenging due to their intricate interconnections. To address this issue, we introduce a new category of structural patterns, hypermotifs, which are defined as statistically significant local structures formed by interconnected hyperedges. We propose a systematic framework for hypermotif extraction. This framework features the encoding, census, and evaluation of higher-order patterns, effectively overcoming their inherent complexity and diversity. Our experimental results demonstrate that hypermotifs can serve as higher-order fingerprints of real-world hypergraphs, helping to identify hypergraph classes based on network functions. These motifs potentially represent preferential attachments and key modules in real-world hypergraphs, arising from specific mechanisms or constraints. Our work validates the efficacy of hypermotifs in exploring hypergraphs, offering a powerful tool for revealing the design principles and underlying dynamics of interacting systems.