alphaFeedback

WorksMathematics

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

AI contributions
Not recorded for this paper
View details

Abstract

Let Xn(r)X^{(r)}_n denote the number of copies of a complete graph KrK_r in the random intersection graph model on nn vertices. We derive upper bounds on the distance between the standardized version of Xn(r)X^{(r)}_n and the standard normal distribution, measured in both the Kolmogorov and Wasserstein metrics. We complement these results with necessary and sufficient conditions for asymptotic normality. As a byproduct, we provide precise estimates for the variance of Xn(r)X^{(r)}_n. In the process, we develop new general techniques for analysing so–called clique covers, which play a crucial role in the study of subgraph probabilities in random intersection graphs.

Introduction

The random intersection graph model, denoted by G(n,m,p)\mathcal{G}(n,m,p), was introduced in [10]. In some respects it resembles the classical G(n,p)\mathcal{G}(n,p) model, in which edges appear independently with probability pp, chosen to equal the edge probability in G(n,m,p)\mathcal{G}(n,m,p). The most interesting features, however, are precisely those that distinguish the two models. In random intersection graphs, in contrast to G(n,p)\mathcal{G}(n,p), edges are not generated independently, which in particular affects the probabilities of small subgraphs. Consequently, the seminal article on random intersection graphs [10] focused on threshold functions for the property of containing a copy of a given graph HH and demonstrated how markedly the two models differ. Subsequent studies have confirmed that the analysis of small subgraphs is central to understanding both the similarities and the differences between G(n,m,p)\mathcal{G}(n,m,p) and G(n,p)\mathcal{G}(n,p). In particular, discrepancies in the distribution of the number of triangles account for significant differences between the two models [8, 12, 21, 5].

In this article, we focus on the subgraph count in G(n,m,p)\mathcal{G}(n,m,p). It is one of the most fundamental statistics in random graph theory and has been studied extensively for several decades. In the case of G(n,p)\mathcal{G}(n,p), asymptotic normality conditions were established in [20] and complemented by convergence rates in the Wasserstein distance in [1]. An analogous result for the more natural Kolmogorov distance was first derived in [19] for triangles, and later extended to arbitrary graphs in [17]. Recently, many results dealing with other random graph models have appeared; see, for example, [2, 7, 11, 13, 14, 15, 16, 18].

In the context of the asymptotic distribution of the number of small subgraphs in G(n,m,p)\mathcal{G}(n,m,p), research has focused mainly on convergence to the Poisson distribution [24, 25]. For certain related random intersection graph models and in various parameter regimes, normal approximations for the number of triangles [3] and for the number of 22–connected subgraphs [4] have been established. However, none of the techniques developed in these studies can be adapted to derive conditions for the asymptotic normality of the number of small cliques in G(n,m,p)\mathcal{G}(n,m,p). The only known result concerning asymptotic normality for larger subgraphs in G(n,m,p)\mathcal{G}(n,m,p) applies solely to triangles [6]. However, the distance bounds obtained there are far from optimal. In particular, they do not imply convergence to the normal distribution for m≥n2m \ge n^2. On the other hand, results in [8, 12, 21, 5] show that the larger the value of mm, the more similar the models G(n,m,p)\mathcal{G}(n,m,p) and G(n,p)\mathcal{G}(n,p) become. Therefore, convergence to the normal distribution should be expected in this parameter regime. Finally, we note that the authors of [6] assume that the edge probability tends to zero.

Recently, the authors of this paper have developed a new method that considerably simplifies the analysis of the normal approximation for the number of small subgraphs in random intersection graphs. In [22], an application of this method was demonstrated for the number of edges and a wide range of parameters was considered. In the present paper, we develop new combinatorial tools aimed at extending this approach from [22] to the more general setting of arbitrary cliques. Our results cover the full range of parameters typically considered in the context of G(n,m,p)\mathcal{G}(n,m,p), including the cases where the edge probability is constant or tends to 11. This is achieved, in part, through the probabilistic techniques developed in [22]. Nevertheless, considering larger graphs significantly increases the complexity of the problem, which required a detailed analysis of subgraphs probabilities. We develop techniques for analysing so-called clique covers. These methods allow for the comparison of occurrence probabilities of different subgraphs, which proves crucial for studying the central moments of certain random variables – a necessary step in establishing convergence to the normal distribution. We believe that these results may be of independent interest, as the techniques introduced here can be applied to study the probabilities of other subgraphs in random intersection graphs. Furthermore, the general framework developed in this work may also prove valuable for estimating central moments in other models of random graphs.

In the article we use the following asymptotic notation:

  • an=o(bn)⇔an/bn→0a_n = o(b_n) \Leftrightarrow a_n/b_n \to0 as n→∞n \to\infty,

  • an=O(bn)⇔∣an∣≤Cbna_n = O(b_n) \Leftrightarrow\lvert a_n\rvert\le Cb_n for some C>0C > 0 and all n∈Nn \in\mathbb{N},

  • an≲bna_n \lesssim b_n or bn≳an⇔an=O(bn)b_n \gtrsim a_n \Leftrightarrow a_n = O(b_n) and an,bn>0a_n,b_n > 0,

  • an≍bn⇔an≲bna_n \asymp b_n \Leftrightarrow a_n \lesssim b_n and bn≲anb_n \lesssim a_n.

All constants implicit in the asymptotic notation are functions of the size of the considered graph.

We also use standard notation from graph theory. For a graph G=(V(G),E(G))G=(V(G),E(G)) we denote by V(G)V(G) its vertex set and by E(G)E(G) its edge set. G′⊆GG' \subseteq G is a subgraph of GG if V(G′)⊆V(G)V(G') \subseteq V(G) and E(G′)⊆E(G)E(G') \subseteq E(G). For V′⊆V(G)V' \subseteq V(G) and E′={e∈E(G):e⊆V′}E'=\{e\in E(G):e\subseteq V'\}, G[V′]=(V′,E′)G[V']=(V',E') is the subgraph of GG induced on the vertex set V′V'. For E′⊆E(G)E'\subseteq E(G) and V′={v:∃e∈E′ v∈e}V'=\{v:\exists e\in E'\ v\in e\}, G[E′]=(V′,E′)G[E']=(V',E') is the subgraph of GG induced on the edge set E′E', and G−E′=(V(G),E(G)∖E′)G-E'=(V(G),E(G)\setminus E'). Furthermore, G∪G′=(V(G)∪V(G′),E(G)∪E(G′))G\cup G'=(V(G)\cup V(G'),E(G)\cup E(G')) and G∩G′=(V(G)∩V(G′),E(G)∩E(G′))G\cap G'=(V(G)\cap V(G'),E(G)\cap E(G')), deg⁡G(v)=∣{e∈E(G):v∈e}∣\deg_G(v)=|\{e\in E(G):v\in e\}| stands for the degree of a vertex vv in GG. We write ≅\cong for the graph isomorphism.

We denote by KiK_i a clique of size ii. In our further considerations, any K\mathbf K and any Kx\mathbf K_x, with an index xx, will be a graph isomorphic to KrK_r, for fixed r≥2r\geq2. In addition, we denote by NiN_i an empty graph on ii vertices. In particular, we allow a graph to be empty with no vertices and no edges, and denote it by N0N_0 or K0K_0.

Main results and discussion

Let us first introduce the random intersection graph model G(n,m,p)\mathcal G(n,m,p). We are given a set of n∈Nn\in\mathbb N vertices V\mathcal V, ∣V∣=n|\mathcal V|=n, and a set of attributes A={a1,…,am}\mathcal A=\{a_1,\ldots,a_m\}, m=m(n)∈Nm=m(n)\in\mathbb N. Any attribute aia_i, 1≤i≤m1\leq i\leq m, is assigned to any vertex v∈Vv\in\mathcal V, (we say that vertex vv chose attribute aia_i) independently with probability p=p(n)∈(0,1)p=p(n)\in(0,1). Then, two vertices vv and v′v' are connected by an edge in G(n,m,p)\mathcal G(n,m,p) whenever they chose at least one common attribute. The existence probability of any edge will be denoted by p\mathbf p and is given by

p=1−(1−p2)m≍mp2∧1,(1)\mathbf p=1-(1-p^2)^m\asymp mp^2\wedge1, \tag*{(1)}

where the estimate is valid for p<cp<c for any fixed c∈(0,1)c\in(0,1).

We study the random variable Xn(r)X_n^{(r)}, r≥2r\geq2, that counts cliques on rr vertices in G(n,m,p)\mathcal G(n,m,p). Let K\mathcal K be the family of all cliques of size rr in the complete graph with the vertex set V\mathcal V. For K∈K\mathbf K\in\mathcal K, let IK\mathbb I_{\mathbf K} be the indicator random variable of the event {K⊆G(n,m,p)}\{\mathbf K\subseteq\mathcal G(n,m,p)\} and define P=E[IK]=P(K⊆G(n,m,p))\mathbf P=\mathbb E[\mathbb I_{\mathbf K}]=\mathbb P(\mathbf K\subseteq\mathcal G(n,m,p)), K∈K\mathbf K\in\mathcal K.

Then

Xn(r)=∑K∈KIK,andE[Xn(r)]=∑K∈KE[IK]=(nr)P.X_n^{(r)}=\sum_{\mathbf K\in\mathcal K}\mathbb I_{\mathbf K},\qquad\text{and}\qquad\mathbb E[X_n^{(r)}]=\sum_{\mathbf K\in\mathcal K}\mathbb E[\mathbb I_{\mathbf K}]=\binom{n}{r}\mathbf P.

Note that estimates of P\mathbf P in terms of mm, pp, and p\mathbf p were derived in [10], and are recalled below in Lemma 4.5. Our main goal is to examine the asymptotic normality of the standardized random variable

X~n(r):=Xn(r)−E[Xn(r)]Var⁡[Xn(r)].\widetilde{X}_n^{(r)}:=\frac{X_n^{(r)}-\mathbb E[X_n^{(r)}]}{\sqrt{\operatorname{Var}[X_n^{(r)}]}}.

and to establish bounds on its convergence rates to a normally distributed random variable N∼N(0,1)\mathcal N\sim\mathcal N(0,1). An important role in this context plays the expression

Ψ:=(nrP)∧(n2p),(2)\Psi:=(n^r\mathbf P)\wedge(n^2\mathbf p), \tag*{(2)}

which has the following probabilistic interpretation

References

  1. [1]A. D. Barbour, M. Karoński, and A. Ruciński. A central limit theorem for decomposable random variables with applications to random graphs. J. Combin. Theory Ser. B, 47(2):125–145, 1989.DOI
  2. [2]B. B. Bhattacharya, A. Chatterjee, and S. Janson. Fluctuations of subgraph counts in graphon based random graphs. Combin. Probab. Comput., 32(3):428–464, 2023.arxiv.org/abs/2104.07259
  3. [3]M. Bloznelis and J. Jaworski. The asymptotic normality of the global clustering coefficient in sparse random intersection graphs. In A. Bonato, P. Pralat, and A. Raigorodskii, editors, Algorithms and Models for the Web Graph. WAW 2018, volume 10836 of Lecture Notes in Computer Science, pages 16–29. Springer International Publishing, 2018.DOI
  4. [4]M. Bloznelis, J. Karjalainen, and L. Leskelä. Normal and stable approximation to subgraph counts in superpositions of bernoulli random graphs. Journal of Applied Probability, 61(2):401–419, Aug. 2023.DOI
  5. [5]M. Brennan, G. Bresler, and D. Nagaraj. Phase transitions for detecting latent geometry in random graphs. Probability Theory and Related Fields, 178(3–4):1215–1289, Sept. 2020.arxiv.org/abs/1910.14167
  6. [6]L. Dong and Z. Hu. The number of triangles in random intersection graphs. Communications in Mathematics and Statistics, 11(4):695–725, Jan. 2023.DOI
  7. [7]X. Fang, S.-H. Liu, Q.-M. Shao, and Y.-K. Zhao. Normal approximation for exponential random graphs. Probab. Theory Related Fields, 2025.arxiv.org/abs/2404.01666
  8. [8]J. A. Fill, E. R. Scheinerman, and K. B. Singer-Cohen. Random intersection graphs when m = ω(n): An equivalence theorem relating the evolution of the G(n, m, p) and G(n, p) models. Random Structures & Algorithms, 16:156–176, 2000.doi.org/10.1002/(sici)1098-2418(200003)16:2<156::aid-rsa3>3.3.co;2-8
  9. [9]S. Janson, T. Łuczak, and A. Ruciński. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000.
  10. [10]M. Karoński, E. R. Scheinerman, and K. B. Singer-Cohen. On random intersection graphs: The subgraph problem. Combinatorics, Probability and Computing, 8(1–2):131–159, 1999.
  11. [11]G. Kaur and A. Röllin. Higher-order fluctuations in dense random graph models. Electron. J. Probab., 26:Paper No. 139, 36, 2021.arxiv.org/abs/2006.15805
  12. [12]J. H. Kim, S. J. Lee, and J. Na. On the total variation distance between the binomial random graph and the random intersection graph. Random Structures & Algorithms, 52(4):662–679, Jan. 2018.arxiv.org/abs/1506.03389
  13. [13]Q. Liu and N. Privault. Normal to Poisson phase transition for subgraph counting in the random-connection model. Electron. J. Probab., 30, 2025.arxiv.org/abs/2409.16222
  14. [14]Q. Liu and N. Privault. Gaussian fluctuations of generalized U-statistics and subgraph counting in the binomial random-connection model. Stochastic Process. Appl., 192:Paper No. 104825, 2026.arxiv.org/abs/2505.12338
  15. [15]P. A. Maugis. Central limit theorems for local network statistics. Biometrika, 111(3):743–754, 2024.arxiv.org/abs/2006.15738
  16. [16]W. Michalczuk, M. Nieradko, and G. Serafin. Normal approximation for subgraph count in random hypergraphs. arxiv:, 2408.06112, 2024.arxiv.org/abs/2408.06112
  17. [17]N. Privault and G. Serafin. Normal approximation for sums of weighted U-statistics—application to Kolmogorov bounds in random subgraph counting. Bernoulli, 26(1):587–615, 2020.DOI
  18. [18]N. Privault and G. Serafin. Normal approximation for generalized U-statistics and weighted random graphs. Stochastics, 94(3):432–458, 2022.arxiv.org/abs/2007.12811
  19. [19]A. Röllin. Kolmogorov bounds for the normal approximation of the number of triangles in the Erdős-Rényi random graph. Probab. Engrg. Inform. Sci., 36(3):747–773, 2022.
  20. [20]A. Ruciński. When are small subgraphs of a random graph normally distributed? Probab. Theory Related Fields, 78(1):1–10, 1988.DOI
  21. [21]K. Rybarczyk. Equivalence of the random intersection graph and G(n,p). Random Structures & Algorithms, 38:205–234, 2011.DOI
  22. [22]K. Rybarczyk and G. Serafin. Normal approximation for subgraph counts in random intersection graphs: the case of edges. arxiv:, 2503.23110, 2025.arxiv.org/abs/2503.23110
  23. [23]K. Rybarczyk and G. Serafin. Subgraph probabilities in random intersection graphs. arxiv; 2026.arxiv.org/abs/2610.27117
  24. [24]K. Rybarczyk and D. Stark. Poisson approximation of the number of cliques in a random intersection graph. Journal of Applied Probability, 47(3):826–840, 2010.DOI
  25. [25]K. Rybarczyk and D. Stark. Poisson approximation of counts of induced subgraphs in random intersection graphs. Discrete Mathematics, 340(9):2183–2193, 2017.DOI

Paper details

vlnc:W_pjcc7xnm
v1 · latestHistory (1)

published · Fresh — added to the Hub within the last 30 days

added ·

Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

CC BY 4.0

Original source

  • Mathematics

Not recorded for this paper · View statement →

Looking for related papers…
Contents