Volume 20, 2016
|Page(s)||131 - 142|
|Published online||14 July 2016|
Poisson approximation of subgraph counts in stochastic block models and a graphon model
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.
Revised: 22 February 2016
Accepted: 2 March 2016
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.
Mathematics Subject Classification: 90B15 / 62E17 / 60F05 / 05C80
Key words: Graphon model / stochastic block model / Erdős–Rényi Mixture Model / subgraph counts / Poisson approximation / Stein–Chen method
© EDP Sciences, SMAI 2016
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.