Compound Poisson approximation of subgraph counts in stochastic block models with multiple edges
We use the Stein‒Chen method to obtain compound Poisson approximations for the distribution of the number of subgraphs in a generalised stochastic block model which are isomorphic to some fixed graph. This model generalises the classical stochastic block model to allow for the possibility of multipl...
Main Authors: | , , |
---|---|
Format: | Journal article |
Published: |
Cambridge University Press
2018
|
_version_ | 1797067236066721792 |
---|---|
author | Coulson, M Gaunt, R Reinert, G |
author_facet | Coulson, M Gaunt, R Reinert, G |
author_sort | Coulson, M |
collection | OXFORD |
description | We use the Stein‒Chen method to obtain compound Poisson approximations for the distribution of the number of subgraphs in a generalised stochastic block model which are isomorphic to some fixed graph. This model generalises the classical stochastic block model to allow for the possibility of multiple edges between vertices. We treat the case that the fixed graph is a simple graph and that it has multiple edges. The former results apply when the fixed graph is a member of the class of strictly balanced graphs and the latter results apply to a suitable generalisation of this class to graphs with multiple edges. We also consider a further generalisation of the model to pseudo-graphs, which may include self-loops as well as multiple edges, and establish a parameter regime in the multiple edge stochastic block model in which Poisson approximations are valid. The results are applied to obtain Poisson and compound Poisson approximations (in different regimes) for subgraph counts in the Poisson stochastic block model and degree corrected stochastic block model of Karrer and Newman (2011). |
first_indexed | 2024-03-06T21:53:29Z |
format | Journal article |
id | oxford-uuid:4c1e6b5f-2d42-462c-9d67-edc31945f5ad |
institution | University of Oxford |
last_indexed | 2024-03-06T21:53:29Z |
publishDate | 2018 |
publisher | Cambridge University Press |
record_format | dspace |
spelling | oxford-uuid:4c1e6b5f-2d42-462c-9d67-edc31945f5ad2022-03-26T15:47:34ZCompound Poisson approximation of subgraph counts in stochastic block models with multiple edgesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:4c1e6b5f-2d42-462c-9d67-edc31945f5adSymplectic Elements at OxfordCambridge University Press2018Coulson, MGaunt, RReinert, GWe use the Stein‒Chen method to obtain compound Poisson approximations for the distribution of the number of subgraphs in a generalised stochastic block model which are isomorphic to some fixed graph. This model generalises the classical stochastic block model to allow for the possibility of multiple edges between vertices. We treat the case that the fixed graph is a simple graph and that it has multiple edges. The former results apply when the fixed graph is a member of the class of strictly balanced graphs and the latter results apply to a suitable generalisation of this class to graphs with multiple edges. We also consider a further generalisation of the model to pseudo-graphs, which may include self-loops as well as multiple edges, and establish a parameter regime in the multiple edge stochastic block model in which Poisson approximations are valid. The results are applied to obtain Poisson and compound Poisson approximations (in different regimes) for subgraph counts in the Poisson stochastic block model and degree corrected stochastic block model of Karrer and Newman (2011). |
spellingShingle | Coulson, M Gaunt, R Reinert, G Compound Poisson approximation of subgraph counts in stochastic block models with multiple edges |
title | Compound Poisson approximation of subgraph counts in stochastic block models with multiple edges |
title_full | Compound Poisson approximation of subgraph counts in stochastic block models with multiple edges |
title_fullStr | Compound Poisson approximation of subgraph counts in stochastic block models with multiple edges |
title_full_unstemmed | Compound Poisson approximation of subgraph counts in stochastic block models with multiple edges |
title_short | Compound Poisson approximation of subgraph counts in stochastic block models with multiple edges |
title_sort | compound poisson approximation of subgraph counts in stochastic block models with multiple edges |
work_keys_str_mv | AT coulsonm compoundpoissonapproximationofsubgraphcountsinstochasticblockmodelswithmultipleedges AT gauntr compoundpoissonapproximationofsubgraphcountsinstochasticblockmodelswithmultipleedges AT reinertg compoundpoissonapproximationofsubgraphcountsinstochasticblockmodelswithmultipleedges |