Normal approximation for subgraph counts in random intersection graphs: the case of edges

Abstract

We investigate the subgraph count in the random intersection graph model $\mathcal{G}(n,m,p)$. Due to substantial edge dependencies, studying even such fundamental statistics is significantly more challenging than in the classical binomial model $\mathcal{G}(n,p)$. This article establish new normal approximation bounds in both the Wasserstein and Kolmogorov distances for general non-degenerate $U$-statistics. We then illustrate how these results can be potentially applied to the standardized number of subgraphs in the random intersection graph model. Finally, as a basic example, we derive necessary and sufficient conditions for the asymptotic normality of the number of edges in $\mathcal{G}(n,m,p)$.

arXiv comment39 pages