Model-based clustering of multiple networks with a hierarchical algorithm

DOI10.48550/ARXIV.2211.02314zbMATH Open1529.62033DBLPjournals/sac/Rebafka24arXiv2211.02314OpenAlexW4388464963WikidataQ131285860 ScholiaQ131285860MaRDI QIDQ57414FDOQ57414

Authors: Tabea Rebafka 

Publication date: 4 November 2022

Published in: Statistics and Computing (Search for Journal in Brave)

Abstract: The paper tackles the problem of clustering multiple networks, that do not share the same set of vertices, into groups of networks with similar topology. A statistical model-based approach based on a finite mixture of stochastic block models is proposed. A clustering is obtained by maximizing the integrated classification likelihood criterion. This is done by a hierarchical agglomerative algorithm, that starts from singleton clusters and successively merges clusters of networks. As such, a sequence of nested clusterings is computed that can be represented by a dendrogram providing valuable insights on the collection of networks. Using a Bayesian framework, model selection is performed in an automated way since the algorithm stops when the best number of clusters is attained. The algorithm is computationally efficient, when carefully implemented. The aggregation of groups of networks requires a means to overcome the label-switching problem of the stochastic block model and to match the block labels of the graphs. To address this problem, a new tool is proposed based on a comparison of the graphons of the associated stochastic block models. The clustering approach is assessed on synthetic data. An application to a collection of ecological networks illustrates the interpretability of the obtained results.

Full work available at URL: https://arxiv.org/abs/2211.02314

Recommendations

• Model-based clustering for network data
• Model-based clustering of large networks
• A review of statistical models for clustering networks with an application to a PPI network
• Improved Bayesian inference for the stochastic block model with application to large networks
• Model selection in overlapping stochastic block models

zbMATH Keywords

agglomerative algorithmgraph clusteringgraphon distanceintegrated classification likelihoodmultiple networksstochastic block model

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Cites Work

• Modeling heterogeneity in random graphs through latent space models: a selective review
• Tracking network dynamics: a survey using graph distances
• What's in a crowd? Analysis of face-to-face behavioral networks
• Estimating a network from multiple noisy realizations
• From here to infinity: sparse finite versus Dirichlet process mixtures in model-based clustering
• Monte Carlo strategies in scientific computing.
• A nonparametric view of network models and Newman–Girvan and other modularities
• Model-based clustering for populations of networks
• Statistical analysis of finite mixture distributions
• Estimation and Prediction for Stochastic Blockstructures
• Model-Based Clustering, Discriminant Analysis, and Density Estimation
• Directed scale-free graphs
• Finite mixture models
• Model selection and clustering in stochastic block models based on the exact integrated complete data likelihood
• The Bayesian Choice
• Spectral clustering and the high-dimensional stochastic blockmodel
• Limits of dense graph sequences
• Pseudo-likelihood methods for community detection in large sparse networks

Cited In (1)

• graphclust

Summary: This paper introduces a hierarchical algorithm for clustering multiple networks, even when these networks vary in size and do not share the same vertices. The method uses a statistical model-based approach, leveraging stochastic block models (SBMs) to group networks with similar topological structures. Clustering is achieved by maximizing the integrated classification likelihood (ICL) criterion, with an automated selection of the optimal number of clusters. A novel technique is presented to address label-switching issues in SBMs by comparing graphons, enabling accurate aggregation of clusters. The method is evaluated on synthetic data and applied to ecological food web networks, demonstrating its efficiency, interpretability, and robustness compared to existing graph clustering approaches.

Summary_simple: This paper explains a way to group networks, like maps of connections between people or animals, based on how their structure is similar. It uses a smart math-based method called stochastic block models (SBMs) to figure out these groups automatically. The process builds a tree-like diagram (dendrogram) to show how the networks are connected and picks the best number of groups without guessing. A special trick compares parts of the networks to make sure the grouping is accurate, even if the networks are labeled differently. This method was tested on fake data and real examples, like food chains in nature, and worked better than older techniques.

This page was built for publication: Model-based clustering of multiple networks with a hierarchical algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q57414)