Model-based clustering of multiple networks with a hierarchical algorithm

DOI10.48550/ARXIV.2211.02314MaRDI QIDQ57414zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Tabea Rebafka

Publication date 4 November 2022

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

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

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)

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.

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

Cites work

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