Compound Poisson approximation of subgraph counts in stochastic block models with multiple edges

Matthew Coulson, Robert Gaunt, Gesine Reinert

    Research output: Contribution to journalArticlepeer-review

    Abstract

    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. Both the cases that the fixed graph is a simple graph and that it has multiple edges are treated. 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 [19].
    Original languageEnglish
    Pages (from-to)759-782
    Number of pages24
    JournalAdvances in Applied Probability
    Volume50
    Issue number3
    DOIs
    Publication statusPublished - Sep 2018

    Fingerprint

    Dive into the research topics of 'Compound Poisson approximation of subgraph counts in stochastic block models with multiple edges'. Together they form a unique fingerprint.

    Cite this