×

Weighted stochastic block model. (English) Zbl 1477.62153

Summary: We propose a weighted stochastic block model (WSBM) which extends the stochastic block model to the important case in which edges are weighted. We address the parameter estimation of the WSBM by use of maximum likelihood and variational approaches, and establish the consistency of these estimators. The problem of choosing the number of classes in a WSBM is addressed. The proposed model is applied to simulated data and an illustrative data set.

MSC:

62H22 Probabilistic graphical models
62F12 Asymptotic properties of parametric estimators
62H30 Classification and discrimination; cluster analysis (statistical aspects)
05C80 Random graphs (graph-theoretic aspects)
68T05 Learning and adaptive systems in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abbe, E., Community detection and stochastic block models: recent developments, J Mach Learn Res, 18, 1-86 (2018) · Zbl 1403.62111
[2] Airoldi, EM; Blei, DM; Fienberg, SE; Xing, EP, Mixed membership stochastic blockmodels, J Mach Learn Res, 9, 1981-2014 (2008) · Zbl 1225.68143
[3] Aicher C, Jacobs AZ, Clauset A (2013) Adapting the stochastic block model to edge-weighted networks. ICML workshop on structured learning · Zbl 1397.68151
[4] Aicher, C.; Jacobs, AZ; Clauset, A., Learning latent block structure in weighted networks, J Compl Netw, 3, 221-248 (2015) · Zbl 1397.68151 · doi:10.1093/comnet/cnu026
[5] Allman, ES; Matias, C.; Rhodes, JA, Identifiability of parameters in latent structure models with many observed variables, Ann Stat, 37, 3099-3132 (2009) · Zbl 1191.62003 · doi:10.1214/09-AOS689
[6] Allman, ES; Matias, C.; Rhodes, JA, Parameter identifiability in a class of random graph mixture models, J Stat Plan Inference, 141, 1719-1736 (2011) · Zbl 1207.62010 · doi:10.1016/j.jspi.2010.11.022
[7] Ambroise, C.; Matias, C., New consistent and asymptotically normal parameter estimates for random-graph mixture models, J R Stat Soc Ser B Stat Methodol, 74, 3-35 (2012) · Zbl 1411.62051 · doi:10.1111/j.1467-9868.2011.01009.x
[8] Baraud, Y., A Bernstein-type inequality for suprema of random processes with applications to model selection in non-Gaussian regression, Bernoulli, 16, 1064-1085 (2010) · Zbl 1459.60044 · doi:10.3150/09-BEJ245
[9] Barrat, A.; Barthélemy, M.; Pastor-Satorras, R.; Vespignani, A., The architecture of complex weighted networks, Proc Natl Acad Sci, 101, 3747-3752 (2004) · doi:10.1073/pnas.0400087101
[10] Bickel, PJ; Chen, A., A nonparametric view of network models and Newman-Girvan and other modularities, Proc Natl Acad Sci USA, 106, 21068-21073 (2009) · Zbl 1359.62411 · doi:10.1073/pnas.0907096106
[11] Bickel, PJ; Chen, A.; Levina, E., The method of moments and degree distributions for network models, Ann Stat, 39, 2280-2301 (2011) · Zbl 1232.91577 · doi:10.1214/11-AOS904
[12] Bickel, P.; Choi, D.; Chang, X.; Zhang, H., Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels, Ann Stat, 41, 1922-1943 (2013) · Zbl 1292.62042 · doi:10.1214/13-AOS1124
[13] Biernacki, C.; Celeux, G.; Govaert, G., Assessing a mixture model for clustering with the integrated completed likelihood, IEEE Trans Pattern Anal Mach Intell, 22, 719-725 (2000) · doi:10.1109/34.865189
[14] Brault, V.; Keribin, C.; Mariadassou, M., Consistency and asymptotic normality of Latent Block Model estimators, Electron J Stat, 14, 1234-1268 (2020) · Zbl 1439.62256 · doi:10.1214/20-EJS1695
[15] Celisse, A.; Daudin, J-J; Pierre, L., Consistency of maximum-likelihood and variational estimators in the stochastic block model, Electron J Stat, 6, 1847-1899 (2012) · Zbl 1295.62028 · doi:10.1214/12-EJS729
[16] Channarond, A.; Daudin, J-J; Robin, S., Classification and estimation in the stochastic blockmodel based on the empirical degrees, Electron J Stat, 6, 2574-2601 (2012) · Zbl 1295.62065 · doi:10.1214/12-EJS753
[17] Choi, DS; Wolfe, PJ; Airoldi, EM, Stochastic blockmodels with a growing number of classes, Biometrika, 99, 273-284 (2012) · Zbl 1318.62207 · doi:10.1093/biomet/asr053
[18] Clauset, A.; Newman, MEJ; Moore, C., Finding community structure in very large networks, Phys Rev E, 70, 066111 (2004) · doi:10.1103/PhysRevE.70.066111
[19] Côme, E.; Latouche, P., Model selection and clustering in stochastic block models based on the exact integrated complete data likelihood, Stat Model, 15, 564-589 (2015) · Zbl 07259003 · doi:10.1177/1471082X15577017
[20] Daudin, J-J; Picard, F.; Robin, S., A mixture model for random graphs, Stat Comput, 18, 173-183 (2008) · doi:10.1007/s11222-007-9046-7
[21] Ghasemian, A.; Zhang, P.; Clauset, A.; Moore, C.; Peel, L., Detectability thresholds and optimal algorithms for community structure in dynamic networks, Phys Rev X, 6, 031005 (2016)
[22] Haj AE, Slaoui Y, Louis P-Y, Khraibani Z (2020) Estimation in a binomial stochastic blockmodel for a weighted graph by a variational expectation maximization algorithm. Commun Stat Simul Comput:1-20
[23] Holland, PW; Laskey, KB; Leinhardt, S., Stochastic blockmodels: first steps, Soc Netw, 5, 109-137 (1983) · doi:10.1016/0378-8733(83)90021-7
[24] Jog V, Loh P-L (2015) Information-theoretic bounds for exact recovery in weighted stochastic block models using the Rényi divergence. CoRR, arXiv:abs/1509.06418
[25] Karrer, B.; Newman, MEJ, Stochastic blockmodels and community structure in networks, Phys Rev E, 83, 016107 (2011) · doi:10.1103/PhysRevE.83.016107
[26] Latouche, P.; Birmelé, E.; Ambroise, C., Overlapping stochastic block models with application to the French political blogosphere, Ann Appl Stat, 5, 309-336 (2011) · Zbl 1220.62083 · doi:10.1214/10-AOAS382
[27] Latouche, P.; Birmelé, E.; Ambroise, C., Model selection in overlapping stochastic block models, Electron J Stat, 8, 762-794 (2014) · Zbl 1349.62276 · doi:10.1214/14-EJS903
[28] Leger, J-B; Vacher, C.; Daudin, J-J, Detection of structurally homogeneous subsets in graphs, Stat Comput, 24, 675-692 (2014) · Zbl 1322.05129 · doi:10.1007/s11222-013-9395-3
[29] Ludkin, M., Inference for a generalised stochastic block model with unknown number of blocks and non-conjugate edge models, Comput Stat Data Anal, 152, 107051 (2020) · Zbl 1510.62261 · doi:10.1016/j.csda.2020.107051
[30] Mariadassou, M.; Robin, S.; Vacher, C., Uncovering latent structure in valued graphs: a variational approach, Ann Appl Stat, 4, 715-742 (2010) · Zbl 1194.62125 · doi:10.1214/10-AOAS361
[31] Newman, MEJ, Analysis of weighted networks, Phys Rev E, 70, 056131 (2004) · doi:10.1103/PhysRevE.70.056131
[32] Peixoto, TP, Nonparametric weighted stochastic block models, Phys Rev E, 97, 012306 (2018) · doi:10.1103/PhysRevE.97.012306
[33] Peng, L.; Carvalho, L., Bayesian degree-corrected stochastic blockmodels for community detection, Electron J Stat, 10, 2746-2779 (2016) · Zbl 1395.62370 · doi:10.1214/16-EJS1163
[34] Pons P, Latapy M (2005) Computing communities in large networks using random walks. In: Proceedings of the 20th international conference on computer and information sciences. Springer, Berlin, ISCIS’05, pp 284-293 · Zbl 1161.68694
[35] Rohe, K.; Chatterjee, S.; Yu, B., Spectral clustering and the high-dimensional stochastic blockmodel, Ann Stat, 39, 1878-1915 (2011) · Zbl 1227.62042 · doi:10.1214/11-AOS887
[36] Saldaña, DF; Yu, Y.; Feng, Y., How many communities are there?, J Comput Graph Stat, 26, 171-181 (2017) · doi:10.1080/10618600.2015.1096790
[37] Snijders, TAB; Nowicki, K., Estimation and prediction for stochastic blockmodels for graphs with latent block structure, J Classif, 14, 75-100 (1997) · Zbl 0896.62063 · doi:10.1007/s003579900004
[38] Stouffer, DB; Bascompte, J., Compartmentalization increases food-web persistence, Proc Natl Acad Sci USA, 108, 3648-3652 (2011) · doi:10.1073/pnas.1014353108
[39] von Luxburg, U., A tutorial on spectral clustering, Stat Comput, 17, 395-416 (2007) · doi:10.1007/s11222-007-9033-z
[40] Wang, YXR; Bickel, PJ, Likelihood-based model selection for stochastic block models, Ann Stat, 45, 500-528 (2017) · Zbl 1371.62017
[41] Yan X (2016) Bayesian model selection of stochastic block models. In: 2016 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM), pp 323-328
[42] Ye, Z-S; Chen, N., Closed-form estimators for the gamma distribution derived from likelihood equations, Am Stat, 71, 177-181 (2017) · Zbl 07671797 · doi:10.1080/00031305.2016.1209129
[43] Zanghi, H.; Picard, F.; Miele, V.; Ambroise, C., Strategies for online inference of model-based clustering in large and growing networks, Ann Appl Stat, 4, 687-714 (2010) · Zbl 1194.62096 · doi:10.1214/10-AOAS359
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.