Clique and cycle frequencies in a sparse random graph model with overlapping communities

Abstract

A statistical network model with overlapping communities can be generated as a superposition of mutually independent random graphs of varying size. The model is parameterized by number of nodes, number of communities, distribution of community sizes, and the link probability inside the communities. This model admits sparse parameter regimes with power-law limiting degree distributions, and nonvanishing clustering coeffient. This article presents large-scale approximations of clique and cycle frequencies for graph samples generated by this model, which are valid for regimes with bounded and unbounded number of overlapping communities.