Model-based clustering in simple hypergraphs through a stochastic blockmodel

2022/10/12 by Luca Brusa, Brusa, Luca, Catherine Matias +1 · 6 citations
Computer Science · Mathematics · #Advanced Clustering Algorithms Research #Artificial intelligence #Cluster analysis #Combinatorics #Computer science #Epistemology #FOS: Computer and information sciences #Mathematics #Methodology (stat.ME) #Philosophy #Simple (philosophy)

paper · pdf · doi:10.48550/arxiv.2210.05983

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2022/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We propose a model to address the overlooked problem of node clustering in simple hypergraphs. Simple hypergraphs are suitable when a node may not appear multiple times in the same hyperedge, such as in co-authorship datasets. Our model generalizes the stochastic blockmodel for graphs and assumes the existence of latent node groups and hyperedges are conditionally independent given these groups. We first establish the generic identifiability of the model parameters. We then develop a variational approximation Expectation-Maximization algorithm for parameter inference and node clustering, and derive a statistical criterion for model selection. To illustrate the performance of our R package HyperSBM, we compare it with other node clustering methods using synthetic data generated from the model, as well as from a line clustering experiment and a co-authorship dataset.

Citations

• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
• Modeling heterogeneity in random graphs through latent space models: a selective review
• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• Networks beyond pairwise interactions: Structure and dynamics
• What Are Higher-Order Networks?
• Latent Space Modelling of Hypergraph Data
• Comparison of modularity-based approaches for nodes clustering in hypergraphs

Cited by

• Learning Multi-Order Block Structure in Higher-Order Networks
• Autoregressive Hypergraph
• Consistent line clustering using geometric hypergraphs
• Broad Spectrum Structure Discovery in Large-Scale Higher-Order Networks
• Comparison of modularity-based approaches for nodes clustering in hypergraphs
• Community detection in hypergraphs through hyperedge percolation

Related

• Model-based clustering for random hypergraphs
• Clustering in networks with the collapsed Stochastic Block Model
• Fast and reliable inference algorithm for hierarchical stochastic block models
• Clustering in Partially Labeled Stochastic Block Models via Total Variation Minimization
• Model-free algorithms for fast node clustering in SBM type graphs and application to social role inference in animals