Abstract
Networks are used in many scientific fields such as biology, social science, and information technology. They aim at modelling, with edges, the way objects of interest, represented by vertices, are related to each other. Looking for clusters of vertices, also called communities or modules, has appeared to be a powerful approach for capturing the underlying structure of a network. In this context, the Block-Clustering model has been applied on random graphs. The principle of this method is to assume that given the latent structure of a graph, the edges are independent and generated from a parametric distribution. Many EM-like strategies have been proposed, in a frequentist setting, to optimize the parameters of the model. Moreover, a criterion, based on an asymptotic approximation of the Integrated Classification Likelihood (ICL), has recently been derived to estimate the number of classes in the latent structure. In this paper, we show how the Block-Clustering model can be described in a full Bayesian framework and how the posterior distribution, of all the parameters and latent variables, can be approximated efficiently applying Variational Bayes (VB). We also propose a new non-asymptotic Bayesian model selection criterion. Using simulated data sets, we compare our approach to other strategies. We show that our criterion can outperform ICL.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Attias, H. (1999). Inferring parameters and structure of latent variable models by variational bayes. In K. B. Laskey, & H. Prade (Eds.), Uncertainty in artificial intelligence: Proceedings of the fifth conference (pp. 21–30). San Fransisco, CA: Morgan Kaufmann.
Biernacki, C., Celeux, G., & Govaert, G. (2000). Assessing a mixture model for clustering with the integrated completed likelihood. IEEE Transactions on Pattern Analysis and Machine Intelligence, 7, 719–725.
Bishop, C. M. (2006). Pattern recognition and machine learning. Berlin: Springer.
Corduneanu, A., & Bishop, C. M. (2001). Variational bayesian model selection for mixture distributions. In T. Richardson, & T. Jaakkola (Eds.), Proceedings eighth international conference on artificial intelligence and statistics (pp. 27–34). San Fransisco, CA: Morgan Kaufmann.
Daudin, J., Picard, F., & Robin, S. (2008). A mixture model for random graph. Statistics and Computing, 18, 1–36.
Hofman, J. M., & Wiggins, C. H. (2008). A bayesian approach to network modularity. Physical Review Letters, 100, 258701.
Hubert, L., & Arabie, P. (1985). Comparing partitions. Journal of Classification, 2, 193–218.
Latouche, P., Birmelé, E., & Ambroise. C. (2008). Bayesian methods for graph clustering. Technical report, SSB.
MacKay, D. (1992). A practical bayesian framework for backpropagation networks. Neural Computation, 4, 448–472.
Mariadassou, M., & Robin, S. (2007). Uncovering latent structure in networks. Technical report, INRA, SSB.
Ng, A. Y., Jordan, M. I., & Weiss, Y. (2001). On spectral clustering: Analysis and an algorithm. Advances in Neural Information Processing Systems, 14.
Parisi, G. (1988). Statistical field theory. Reading MA: Addison Wesley.
Snijders, T. A. B., & Nowicki, K. (1997). Estimation and prediction for stochastic block-structures for graphs with latent block sturcture. Journal of Classification, 14, 75–100.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Latouche, P., Birmelé, E., Ambroise, C. (2009). Bayesian Methods for Graph Clustering. In: Fink, A., Lausen, B., Seidel, W., Ultsch, A. (eds) Advances in Data Analysis, Data Handling and Business Intelligence. Studies in Classification, Data Analysis, and Knowledge Organization. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01044-6_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-01044-6_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01043-9
Online ISBN: 978-3-642-01044-6
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)