A Variational Bayesian Algorithm for Clustering of Large and Complex Networks
Please always quote using this URN: urn:nbn:de:0297-zib-54588
- We propose the Blockloading algorithm for the clustering of large and complex graphs with tens of thousands of vertices according to a Stochastic Block Model (SBM). Blockloading is based on generalized Variational Bayesian EM (VBEM) schemes and works for weighted and unweighted graphs. Existing Variational (Bayesian) EM methods have to consider each possible number of clusters sepa- rately to determine the optimal number of clusters and are prone to converge to local optima making multiple restarts necessary. These factors impose a severe restriction on the size and complexity of graphs these methods can handle. In con- trast, the Blockloading algorithm restricts restarts to subnetworks in a way that provides error correction of an existing cluster assignment. The number of clusters need not be specified in advance because Blockloading will return it as a result. We show that Blockloading outperforms all other variational methods regarding reliability of the results and computational efficiency.
Author: | Christian Tobias Willenbockel, Christof Schütte |
---|---|
Document Type: | ZIB-Report |
Tag: | Clustering; Model Selection,; Networks; Stochastic Block Model; Variational Bayes EM; unsupervised classification |
MSC-Classification: | 62-XX STATISTICS / 62Hxx Multivariate analysis [See also 60Exx] / 62H12 Estimation |
62-XX STATISTICS / 62Hxx Multivariate analysis [See also 60Exx] / 62H30 Classification and discrimination; cluster analysis [See also 68T10] | |
Date of first Publication: | 2015/04/21 |
Series (Serial Number): | ZIB-Report (15-25) |
ISSN: | 1438-0064 |