Variational Bayes model averaging for graphon functions and motif frequencies inference in \(W\)-graph models. (English) Zbl 1349.62081

Summary: \(W\)-graph refers to a general class of random graph models that can be seen as a random graph limit. It is characterized by both its graphon function and its motif frequencies. In this paper, relying on an existing variational Bayes algorithm for the stochastic block models (SBMs) along with the corresponding weights for model averaging, we derive an estimate of the graphon function as an average of SBMs with increasing number of blocks. In the same framework, we derive the variational posterior frequency of any motif. A simulation study and an illustration on a social network complete our work.


62F15 Bayesian inference
05C80 Random graphs (graph-theoretic aspects)
62G05 Nonparametric estimation
91D30 Social networks; opinion dynamics
Full Text: DOI arXiv


[1] Airoldi, E.M., Costa, T.B., Chan, S.H.: Stochastic blockmodel approximation of a graphon: theory and consistent estimation. Adv. Neural Inf. Process. Syst. 692-700 (2013)
[2] Asta, D., Shalizi, C.R.: Geometric Network Comparison. Technical report (2014). arXiv:1411.1350v1
[3] Barabási, AL; Albert, R, Emergence of scaling in random networks, Science, 286, 509-512, (1999) · Zbl 1226.05223
[4] Barbour, A; Reinert, G, Discrete small world networks, Electron. J. Probab., 11, 1234-1283, (2006) · Zbl 1184.90027
[5] Beal, JM; Ghahramani, Z, The variational Bayesian EM algorithm for incomplete data: with application to scoring graphical model structures, Bayesian Stat., 7, 543-552, (2003)
[6] Bhattacharyya, S; Bickel, PJ, Subsampling bootstrap of count features of networks, Ann. Stat., 43, 2384-2411, (2015) · Zbl 1326.62067
[7] Bickel, P; Chen, A, A non parametric view of network models and Newman-girvan and other modularities, Proc. Natl Acad. Sci. USA, 106, 21068-21073, (2009) · Zbl 1359.62411
[8] Bickel, P; Chen, A; Levina, E, The method of moments and degree distributions for network models, Ann. Stat., 39, 2280-2301, (2011) · Zbl 1232.91577
[9] Bollobás, B; Janson, S; Riordan, O, The phase transition in inhomogeneous random graphs, Random Struct. Algorithms, 31, 3-122, (2007) · Zbl 1123.05083
[10] Borgs, C., Chayes, J., Cohn, H., Ganguly, S.: Consistent Nonparametric Estimation for Heavy-Tailed Sparse Graphs. Technical report (2015). arXiv:1508.06675
[11] 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
[12] Chan, S; Airoldi, E, A consistent histogram estimator for exchangeable graph models, J. Mach. Learn. Res. Conf. Proc., 32, 208-216, (2014)
[13] Channarond, A; Daudin, J-J; Robin, S, Classification and estimation in the stochastic block model based on the empirical degrees, Electron. J. Stat., 6, 2574-2601, (2012) · Zbl 1295.62065
[14] Chatterjee, S, Matrix estimation by universal singular value thresholding, Ann. Stat., 43, 177-214, (2015) · Zbl 1308.62038
[15] Daudin, J-J; Picard, F; Robin, S, A mixture model for random graphs, Stat. Comput., 18, 173-183, (2008)
[16] Diaconis, P; Janson, S, Graph limits and exchangeable random graphs, Rend. Mat. Appl., 7, 33-61, (2008) · Zbl 1162.60009
[17] Gazal, S; Daudin, J-J; Robin, S, Accuracy of variational estimates for random graph mixture models, J. Stat. Comput. Simul., 82, 849-862, (2012) · Zbl 1431.62232
[18] Girvan, M; Newman, M, Community structure in social and biological networks, Proc. Natl Acad. Sci. USA, 99, 7821, (2002) · Zbl 1032.91716
[19] Gouda, A; Szántai, T, On numerical calculation of probabilities according to Dirichlet distribution, Ann. Oper. Res., 177, 185-200, (2010) · Zbl 1202.60027
[20] Hoeting, JA; Madigan, D; Raftery, AE; Volinsky, CT, Bayesian model averaging: a tutorial, Stat. Sci., 14, 382-417, (1999) · Zbl 1059.62525
[21] Hoff, P, Modeling homophily and stochastic equivalence in symmetric relational data, Adv. Neural Inf. Process. Syst., 20, 657-664, (2008)
[22] Kallenberg, O, Multivariate sampling and the estimation problem for exchangeable arrays, J. Theor. Probab., 12, 859-883, (1999) · Zbl 0983.62055
[23] 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
[24] Latouche, P; Birmelé, E; Ambroise, C, Variational Bayesian inference and complexity control for stochastic block models, Stat. Model., 12, 93-115, (2012)
[25] Lloyd, J., Orbanz, P., Ghahramani, Z., Roy, D.: Random function priors for exchangeable arrays with applications to graphs and relational data. Adv. Neural Inf. Process. Syst. 998-1006 (2012) · Zbl 1162.60009
[26] Lovász, L; Szegedy, B, Limits of dense graph sequences, J. Comb. Theory B, 96, 933-957, (2006) · Zbl 1113.05092
[27] 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
[28] Milo, R; Shen-Orr, S; Itzkovitz, S; Kashtan, N; Chklovskii, D; Alon, U, Networks motifs: simple building blocks of complex networks, Science, 298, 824-827, (2002)
[29] Nowicki, K; Snijders, T, Estimation and prediction for stochastic block-structures, J. Am. Stat. Assoc., 96, 1077-1087, (2001) · Zbl 1072.62542
[30] Palla, G; Lovasz, L; Vicsek, T, Multifractal network generator, Proc. Natl Acad. Sci. USA, 107, 7640-7645, (2010)
[31] Picard, F; Daudin, J-J; Koskas, M; Schbath, S; Robin, S, Assessing the exceptionality of network motifs, J. Comput. Biol., 15, 1-20, (2008)
[32] Robins, G; Pattison, P; Kalish, Y; Lusher, D, An introduction to exponential random graph models for social networks, Soc. Netw., 29, 173-191, (2007)
[33] Stark, D, Compound Poisson approximations of subgraph counts in random graphs, Random Struct. Algorithms, 18, 39-60, (2001) · Zbl 0968.05070
[34] Volant, S; Magniette, M-LM; Robin, S, Variational Bayes approach for model aggregation in unsupervised classification with Markovian dependency, Comput. Stat. Data Anal., 56, 2375-2387, (2012) · Zbl 1252.62067
[35] Watts, DJ; Strogatz, SH, Collective dynamics of ‘small-world’ networks, Nature, 393, 440-442, (1998) · Zbl 1368.05139
[36] Wolfe, P.J., Olhede, S.C.: Nonparametric graphon estimation. Technical report (2013). arXiv:1309.5936 · Zbl 1151.68623
[37] Yang, J; Han, Q; Airoldi, E, Nonparametric estimation and testing of exchangeable graph models, J. Mach. Learn. Res. Conf. Proc., 30, 1060-1067, (2014)
[38] Zanghi, H; Ambroise, C; Miele, V, Fast online graph clustering via Erdös renyi mixture, Pattern Recognit., 41, 3592-3599, (2008) · Zbl 1151.68623
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.