Geodesic
Poisson approximation of subgraph counts in stochastic block models and a graphon model
Coulson, Matthew1 ; Gaunt, Robert E.2 ; Reinert, Gesine2 
1 The Queen’s College, University of Oxford, High Street, Oxford, OX1 4AW, UK.
2 Department of Statistics, University of Oxford, 24-29 St Giles’, Oxford OX1 3LB, UK.
ESAIM: Probability and Statistics, Tome 20 (2016), pp. 131-142.

Voir la notice de l'article provenant de la source Numdam

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 [0,1]. Our results apply when the fixed graph is a member of the class of strictly balanced graphs.

Reçu le :
Accepté le :
DOI : 10.1051/ps/2016006
Classification : 90B15, 62E17, 60F05, 05C80
Keywords: Graphon model, stochastic block model, Erdős–Rényi Mixture Model, subgraph counts, Poisson approximation, Stein–Chen method

Coulson, Matthew 1 ; Gaunt, Robert E. 2 ; Reinert, Gesine 2

1 The Queen’s College, University of Oxford, High Street, Oxford, OX1 4AW, UK.
2 Department of Statistics, University of Oxford, 24-29 St Giles’, Oxford OX1 3LB, UK. 
@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/articles/10.1051/ps/2016006/

E.M. Airoldi, T.B. Costa and S.H. Chan, Stochastic blockmodel approximation of a graphon: Theory and consistent estimation. Adv. Neur. In. 26 (2013) 692–700.

D.J. Aldous, Representations for partially exchangeable arrays of random variables. J. Multivariate Anal. 11 (1981) 581–598. | MR | Zbl | DOI

W. Ali, T. Rito, G. Reinert, F. Sun and C.M. Deane, Alignment-free protein interaction network comparison. Bioinformatics 30 (2014) i430–i437. | DOI

R. Arratia L. Goldstein and L. Gordon, Two Moments Suffice for Poisson Approximations: the Chen-Stein Method. Ann. Probab. 17 (1989) 9–25. | MR | Zbl | DOI

A.D. Barbour, L. Holst and S. Janson, Poisson Approximation. Oxford University Press, Oxford (1992). | MR | Zbl

P. Bickel and A. Chen, A non parametric view of network models and Newman-Girvan and other modularities. Proc. Natl. Acad. Sci. USA 106 (2009) 21068–21073. | Zbl | DOI

B. Bollobas, S. Janson and O. Riordan, The phase transition in inhomogeneous random graphs. Random Struct. Algor. 31 (2007) 3–122. | MR | Zbl | DOI

L.H.Y. Chen, 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

J.J. Daudin, F. Picard and S. Robin, A mixture model for random graphs. Stat. Comput. 18 (2008) 173–183. | MR | DOI

P. Diaconis and S. Janson, Graph limits and exchangeable random graphs. Rendiconti di Matematica 28 (2008) 33–61. | MR | Zbl

O. Frank and D. Strauss, Markov graphs. J. Am. Stat. Assoc. 81 (1986) 832-842. | MR | Zbl | DOI

P.W. Holland, K.B. Laskey and S. Leinhardt, Stochastic blockmodels: First steps. Soc. Networks 5 (1983) 109–137. | MR | DOI

B. Karrer, and M.E. Newman, Stochastic blockmodels and community structure in networks. Phys. Rev. E 83 (2011), 016107. | MR | DOI

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).

L. Lovász and B. Szegedy, Limits of dense graph sequences. J. Comb. Theory B 96 (2006) 933–957. | MR | Zbl | DOI

C. Matias and S. Robin, Modeling heterogeneity in random graphs through latent space models: a selective review. ESAIM: Proc. Surv. 47 (2014) 55–74. | MR | Zbl | DOI

A. Mcneil and J. Neslehová, Multivariate Archimedean Copulas, d-monotone functions and L 1 -norm symmetric distributions. Ann. Stat. 37 (2007) 3059–3097. | MR | Zbl

R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii and U. Alon, Network motifs: simple building blocks of complex networks. Science 298 (2002) 824-827. | DOI

K. Nowicki and T. Snijders Estimation and prediction for stochastic blockstructures. J. Am. Stat. Assoc. 96 (2001) 1077–1087. | MR | Zbl | DOI

S.C. Olhede and P.J. Wolfe, Network histograms and universality of blockmodel approximation. P. Natl. Acad. Sci. USA 111 (2014) 14722–14727. | DOI

F. Picard, J.J. Daudin, M. Koskas, S. Schbath and S. Robin, Assessing the exceptionality of network motifs. J. Comput. Biol. 15 (2008) 1–20. | MR | DOI

R.J. Ruciński and A. Vince, Balanced graphs and the problem of subgraphs of random graphs. Congr. Numerantium 49 (1985) 181–190. | MR | Zbl

A. Sarajlić, V. Janjić, N. Stojković, D. Radak and N. Pržulj, Network topology reveals key cardiovascular disease genes. PLoS One 8 (2013) e71537. | DOI

D. Stark, Compound Poisson approximation of subgraph counts in random graphs. Random Struct. Algor. 18 (2001) 39–60. | MR | Zbl | 3.0.CO;2-B class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI

P.J. Wolfe and S.C. Olhede, Nonparametric graphon estimation. Preprint arXiv:1309.5936 (2013).

Cité par Sources :