Small subgraph counts can be used as summary statistics for large random graphs. We use the Stein–Chen method to derive Poisson approximations for the distribution of the number of subgraphs in the stochastic block model which are isomorphic to some fixed graph. We also obtain Poisson approximations for subgraph counts in a graphon-type generalisation of the model in which the edge probabilities are (possibly dependent) random variables supported on a subset of . Our results apply when the fixed graph is a member of the class of strictly balanced graphs.
Accepté le :
DOI : 10.1051/ps/2016006
Mots-clés : Graphon model, stochastic block model, Erdős–Rényi Mixture Model, subgraph counts, Poisson approximation, Stein–Chen method
@article{PS_2016__20__131_0,
author = {Coulson, Matthew and Gaunt, Robert E. and Reinert, Gesine},
title = {Poisson approximation of subgraph counts in stochastic block models and a graphon model},
journal = {ESAIM: Probability and Statistics},
pages = {131--142},
publisher = {EDP-Sciences},
volume = {20},
year = {2016},
doi = {10.1051/ps/2016006},
mrnumber = {3528620},
zbl = {1353.05112},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ps/2016006/}
}
TY - JOUR AU - Coulson, Matthew AU - Gaunt, Robert E. AU - Reinert, Gesine TI - Poisson approximation of subgraph counts in stochastic block models and a graphon model JO - ESAIM: Probability and Statistics PY - 2016 SP - 131 EP - 142 VL - 20 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ps/2016006/ DO - 10.1051/ps/2016006 LA - en ID - PS_2016__20__131_0 ER -
%0 Journal Article %A Coulson, Matthew %A Gaunt, Robert E. %A Reinert, Gesine %T Poisson approximation of subgraph counts in stochastic block models and a graphon model %J ESAIM: Probability and Statistics %D 2016 %P 131-142 %V 20 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ps/2016006/ %R 10.1051/ps/2016006 %G en %F PS_2016__20__131_0
Coulson, Matthew; Gaunt, Robert E.; Reinert, Gesine. Poisson approximation of subgraph counts in stochastic block models and a graphon model. ESAIM: Probability and Statistics, Tome 20 (2016), pp. 131-142. doi : 10.1051/ps/2016006. http://archive.numdam.org/articles/10.1051/ps/2016006/
, and , Stochastic blockmodel approximation of a graphon: Theory and consistent estimation. Adv. Neur. In. 26 (2013) 692–700.
, Representations for partially exchangeable arrays of random variables. J. Multivariate Anal. 11 (1981) 581–598. | DOI | MR | Zbl
, , , and , Alignment-free protein interaction network comparison. Bioinformatics 30 (2014) i430–i437. | DOI
and , Two Moments Suffice for Poisson Approximations: the Chen-Stein Method. Ann. Probab. 17 (1989) 9–25. | DOI | MR | Zbl
A.D. Barbour, L. Holst and S. Janson, Poisson Approximation. Oxford University Press, Oxford (1992). | MR | Zbl
and , A non parametric view of network models and Newman-Girvan and other modularities. Proc. Natl. Acad. Sci. USA 106 (2009) 21068–21073. | DOI | Zbl
, and , The phase transition in inhomogeneous random graphs. Random Struct. Algor. 31 (2007) 3–122. | DOI | MR | Zbl
, Poisson approximation for dependent trials. Ann. Probab. 3 (1975) 534–545. | MR | Zbl
A. Condon and R.M. Karp, Algorithms for graph partitioning on the planted partition model. In Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques. Springer Berlin Heidelberg (1999) 221-232. | MR | Zbl
, and , A mixture model for random graphs. Stat. Comput. 18 (2008) 173–183. | DOI | MR
and , Graph limits and exchangeable random graphs. Rendiconti di Matematica 28 (2008) 33–61. | MR | Zbl
and , Markov graphs. J. Am. Stat. Assoc. 81 (1986) 832-842. | DOI | MR | Zbl
, and , Stochastic blockmodels: First steps. Soc. Networks 5 (1983) 109–137. | DOI | MR
, and , Stochastic blockmodels and community structure in networks. Phys. Rev. E 83 (2011), 016107. | DOI | MR
P. Latouche and S. Robin, Bayesian Model Averaging of Stochastic Block Models to Estimate the Graphon Function and Motif Frequencies in a W-graph Model. Preprint arXiv:1310.6150 (2013).
and , Limits of dense graph sequences. J. Comb. Theory B 96 (2006) 933–957. | DOI | MR | Zbl
and , Modeling heterogeneity in random graphs through latent space models: a selective review. ESAIM: Proc. Surv. 47 (2014) 55–74. | DOI | MR | Zbl
and , Multivariate Archimedean Copulas, d-monotone functions and -norm symmetric distributions. Ann. Stat. 37 (2007) 3059–3097. | MR | Zbl
, , , , and , Network motifs: simple building blocks of complex networks. Science 298 (2002) 824-827. | DOI
and Estimation and prediction for stochastic blockstructures. J. Am. Stat. Assoc. 96 (2001) 1077–1087. | DOI | MR | Zbl
and , Network histograms and universality of blockmodel approximation. P. Natl. Acad. Sci. USA 111 (2014) 14722–14727. | DOI
, , , and , Assessing the exceptionality of network motifs. J. Comput. Biol. 15 (2008) 1–20. | DOI | MR
and , Balanced graphs and the problem of subgraphs of random graphs. Congr. Numerantium 49 (1985) 181–190. | MR | Zbl
, , , and , Network topology reveals key cardiovascular disease genes. PLoS One 8 (2013) e71537. | DOI
, Compound Poisson approximation of subgraph counts in random graphs. Random Struct. Algor. 18 (2001) 39–60. | DOI | MR | Zbl
P.J. Wolfe and S.C. Olhede, Nonparametric graphon estimation. Preprint arXiv:1309.5936 (2013).
Cité par Sources :
