# Asymptotics ofm-Cliques in a Sparse Inhomogeneous Random Graph

Authors: Xiaofeng Zhao
Journal: Journal of Mathematics
 (2022)

---

## Abstract

One of the classical questions in random graph theory is to understand the asymptotics of subgraph counts. In inhomogeneous random graph, this question has not been well studied. In this study, we investigate the asymptotic distribution ofm-cliques in a sparse inhomogeneous random graph. Under mild conditions, we prove that the number of m-cliques converges in law to the standard normal distribution.


---

## Body

## 1. Introduction

The random graph theory was founded by Erdös–Rényi [1]. The well-known Erdös–Rényi random graph Gn,p is an undirected graph on vertices’ (nodes) set n=1,2,…,n, where any two nodes form an edge independently with probability p. In random graph theory, one of the classical questions concerns the asymptotics of the number of subgraphs [2–7]. Much attention has been paid to the limiting distribution of subgraph counts. In a dense Erdös–Rényi graph, the subgraph count converges in law to the standard normal distribution under some conditions [3]. This result was proven to be true for sparse random graph [2]. Analogue results exist for the number of strictly balanced subgraph or short cycles in random regular graphs [4–6, 8].In practice, a lot of real networks display the inhomogeneity property, that is, the vertex degrees vary a lot. In many cases, the degree follows a power law [9]. To accommodate the inhomogenity, the inhomogeneous random graph has recently been introduced [10]. It is natural to study the asymptotics of subgraphs in an inhomogeneous random graph. Some of the first results concern the asymptotic clique or cycle number in special inhomogeneous random graph [9, 11, 12, 23, 24]. For example, the authors gave the upper bound and lower bound of the average number of cycles in [12]. The authors of [9, 13] obtained the asymptotic order of large cliques in scale-free random graph, and Janson [14] studied the order of the largest component. In [12], the order of expected number of cycles and cliques in a random graph were given. Hu and Dong [15] derived the limiting distribution of the number of edges in a generalized random graph, and Liu and Dong [16] derived the asymptotic distribution of the number of triangles. However, to our knowledge, the limiting distribution of the number of cliques is unknown. In this study, we study this problem in sparse inhomogeneous random graph and derive its asymptotic distribution.


## 2. The Model and Main Result

In this section, we introduce the model and present the main result. The inhomogeneous random graphGn,p,W is defined as follows: given a positive array W=Wij1≤i<j≤n, every pair of nodes i,j in Gn,p,W are joined as an edge with probability pWij independently. The adjacency matrix A of a graph is a symmetric 0,1-matrix with zeros on its diagonal and Aij=1 if i,j is an edge, Aij=0 otherwise. For Gn,p,W, the adjacency matrix A is a symmetric random matrix, with elements following independent Bernoulli distributions, that is,(1)pij=ℙAij=1=pWij,1≤i<j≤n,and Aij is independent of Akl if i,j≠k,l. By symmetry, pji=pij for i≠j and pii=0 for i=1,2,…,n. This model was introduced in [10], and it contains the models in [9, 11, 18] as a special case. If Wij≡11≤i<j≤n, the random graph is the homogeneous Erdös–Rényi model, where nodes i,j form an edge with probability p [1].In graphG, an m-clique is a subgraph of m vertices such that any two distinct vertices are adjacent. Given the adjacency matrix A and vertices i1<i2<⋯<im, the node set i1,i2,…,im forms an m-clique if and only if(2)∏1≤k<l≤mAikil=1.Then, the total numberNn of m-clique in G is(3)Nn=∑1≤i1<i2<…<im≤n∏1≤k<l≤mAikil.For the random graphGn,p,W, Nn is a sum of dependent random variables. The asymptotic distribution of Nn is given in the following theorem.Theorem 1.
LetNn be the number of m-cliques in the random inhomogeneous graph Gn,p,W with expectation ENn and variance VNn. Suppose m≥3 is a fixed integer, for some 0<ϵ<1,(4)limn⟶∞nm−2pm+1m−2/2=0,limn⟶∞nm1−ϵpmm−1/2=∞,for some positive constants c1,c2, 0≤Wij≤c2,1≤i<j≤n, and(5)c1nm≤∑1≤i1<i2<…<im≤n∏1≤k<l≤mWikil.Then,(6)Nn−ENnVNn⇒N0,1,asn⟶∞,where ‘⇒’ represents convergence in distribution.According to Theorem1, the scaled and centered number of m-cycle in Gn,p,W converges in law to the standard normal distribution. Note that Theorem 1 only holds for sparse random graph. The first equation in (4) implies p=on−2/m+1 and the second one requires the average degree tends to infinity. Our proof relies on the martingale central limit theorem.The conditions onW seem to be very restrictive. In fact, there are many models which satisfy these conditions. Here, we provide some of the examples that satisfy the conditions of Theorem 1. Consider the rank one model with(7)pij=pWij,Wij=ijn2,i≠j,Wii=0, 1≤i≤n. Suppose p satisfies (4). Straightforward computation yields(8)∑1≤i1<i2…<im≤n∏1≤k<l≤mWikil=∑1≤i1<i2…<im≤n∏1≤k≤miknm−1≍n2mnmm−1=nm.Hence, (5) holds and Theorem 1 applies to this model. The average degree di of each vertex i is given by(9)di=∑jpij=ip2+ip2n−i2pn2,i=1,2,…,n.The degreedn is approximately n times of d1, that is, dn≍nd1. Hence, this model is essentially different from the homogeneous Erdös–Rényi model. Furthermore, suppose p=logn/n, satisfying (4) for m=3. Then, for some constant κ>0,(10)0<κ≤maxidi=logn2+o1≤ηlogn,maxi≠jpij≤n−1+η,η∈0.5,1.This model is a special case in [17], where the authors studied asymptotic behavior of the extreme eigenvalues.Another interesting model is the power-law graphs [22]:(11)pij=1nin−1/pjn−1/p,i≠j,p>0.Rewrite the probabilities as(12)pij=annn2/pan1i1/p1i1/p=pWij,where p=an/n and Wij=n2/p/an1/i1/p1/i1/p. If an≍n2/p, then Wij≤c2<∞ for some constant c2. For some generic positive constant c3,(13)∑1≤i1<i2…<im≤n∏1≤k<l≤mWikil≥c3∑1≤i1<i2…<im≤n∏1≤k≤m1ik1/pm−1≍n2mnmm−1=nm.


## 3. Proof of Main Result

In this section, we prove Theorem1. For convenience, denote αn≍βn if 0<c1≤αn/βn≤c2<∞ for some constants c1 and c2; αn≪βn if αn=oβn. The proof relies on the following result.Proposition 1 (see [20]).
Suppose that, for everyn∈ℕ and kn⟶∞, the random variables Xn,1,…,Xn,kn are a martingale difference sequence relative to an arbitrary filtration ℱn,1⊂ℱn,2⊂⋯ℱn,kn. If (I) ∑i=1knEXn,i2|ℱn,i−1⟶1 in probability, (II) ∑i=1knEXn,i2IXn,i>ϵ|ℱn,i−1⟶0 in probability, for every ϵ>0, then ∑i=1knXn,i⟶N0,1 in distribution.Now, we prove Theorem1. Let M=m2=mm−1/2, S=ik,il|1≤k<l≤m, and(14)St=st|stisasubset consisting oftelements inS.Denotestc, the complement set of st in S. By Taylor expansion, for generic constants ci, 1≤i≤M−1, it follows(15)Nn−ENn=∑1≤i1<i2<…<im≤n∏1≤k<l≤mAikil−∏1≤k<l≤mpWikil=∑1≤i1<i2<…<im≤n∏1≤k<l≤mAikil−pWikil+∑t=1M−1Rt,where(16)Rt=∑1≤i1<i2<…<im≤n∑st∈St∏i,j∈stAij−pWij∏i,j∈stcpWij.Next, we show the first term in (15) is the leading term. Note that if ik,il≠jk,jl, by the independence of Aikil and Ajkjl, it follows(17)EAikil−pWikilAjkjl−pWjkjl=0.Then, it s easy to obtain(18)E∑1≤i1<i2<…<im≤n∏1≤k<l≤mAikil−pWikil2=∑1≤i1<…<im≤n1≤j1<…<jm≤nE∏1≤k<l≤mAikil−pWikilAjkjl−pWjkjl=∑1≤i1<i2<…<im≤n∏1≤k<l≤mEAikil−pWikil2=∑1≤i1<i2<…<im≤n∏1≤k<l≤mpWikil1−pWikil.For convenience, let(19)σn2=∑1≤i1<i2<…<im≤n∏1≤k<l≤mpWikil1−pWikil.Note thatσn2≍nm1−ϵpM under the assumption of Theorem 1. To get the order of R1, let s1=i1,i2 and s1∗=j1,j2; then,(20)E∑1≤i1<i2<…<im≤nAi1i2−pWi1i2∏i,j∈s1cpWij2=∑1≤i1<…<im≤n1≤j1<…<jm≤nEAi1i2−pWi1i2Aj1j2−pWj1j2∏i,j∈s1cpWij∏i,j∈s1∗cpWij=∑1≤i1<…<im≤ni2<j3<…<jm≤nEAi1i2−pWi1i22∏i,j∈s1cpWij∏i,j∈s1∗cpWij=∑1≤i1<…<im≤ni2<j3<…<jm≤npWi1i21−pWi1i2∏i,j∈s1cpWij∏i,j∈s1∗cpWij=OPn2m−2p2M−1,which implies R12=OPn2m−2p2M−1. For RM−1, let sM−1=i1,i2,i1,i3,…,im−2,im−1 and sM−1∗=j1,j2,j1,j3,…,jm−2,jm−1. Then,(21)E∑1≤i1<i2<…<im≤npWim−1im∏i,j∈sM−1Aij−pWij2=∑1≤i1<…<im≤n1≤j1<…<jm≤nEpWim−1impWjm−1jm∏i,j∈sM−1Aij−pWij∏i,j∈sM−1∗Aij−pWij=∑1≤i1<…<im≤np2Wim−1im2∏i,j∈sM−1EAij−pWij2=∑1≤i1<…<im≤np2Wim−1im2∏i,j∈sM−1pWij1−pWij=OPnmpM+1,from which it yields RM−12=OPnmpM+1. For t≥m, any st involves all the vertices i1,i2,…,im. Hence, by a similar proof of (20) and (21), it follows that Rt2=OPnmp2M−t. For 3≤t≤m−1, any st involves at least t distinct vertices; then, Rt2=OPn2m−tp2M−t. When t=2, st contains at least 3 distinct vertices; then, R22=OPn2m−3p2M−2.We claim the following hold:(22)n2m−2p2M−1nmpM=nm−2pM−1⟶0,t=1,(23)n2m−3p2M−2nmpM=nm−3pM−2⟶0,t=2,(24)nmp2M−tnmpM=pM−t⟶0,m≤t≤M−1,(25)n2m−tp2M−tnmpM=nm−tpM−t⟶0,3≤t≤m−1.Firstly, according to the first equation in (4), (22) and (24) hold trivially. Let p=an/n; then, an≪nM−m+1/M−1 by (22). Equations (23) and (25) hold if(26)an≪nM−m+1/M−2,an≪nM−m/M−t,3≤t≤m−1.Simple algebra yields(27)M−m+1M−1−M−mM−3=−m−2m−32M−3M−1≤0,m≥3.Hence,M−m+1/M−1≤M−m/M−t3≤t≤m−1. Then, the first equation in (4) implies (22)–(25).As a result, by (15), one has(28)Nn−ENn=∑1≤i1<i2<…<im≤n∏1≤k<l≤mAikil−pWikil+oPnmpM,and VNn=σn2+onmpM. Therefore, to prove Theorem 1, it suffices to prove(29)Xn=∑1≤i1<i2<…<im≤n∏1≤k<l≤mAikil−pWikilσn⇒N0,1.In the following, we use Proposition1 to prove (29). To this end, define Zt=Xt−Xt−1 for 4≤t≤n, where X3=0 and(30)Xt=∑1≤i1<i2<…<im≤t∏1≤k<l≤mAikil−pWikilσn.LetFt=Aij|1≤i<j≤t and Ct=ik,im|1≤k≤m−1,im=t. Then,(31)σnEZt|Ft−1=∑1≤i1<i2<…<im=t∏i,j∈CtcAij−pWij∏i,j∈CtEAij−pWij=0,which implies Zt is a Martingale difference.Check conditionI in Proposition 1. It suffices to show the following:(32)E∑t=mnEZt2|Ft−1⟶1,E∑t=mnEZt2|Ft−12⟶1.For (30), direct computation yields(33)E∑t=mnEZt2|Ft−1=E∑t=mnEXt2−2XtXt−12+Xt−12|Ft−1=∑t=mnEXt2−EXt−12=EXn2=1.For (32), let Ct∗=jk,jm|1≤k≤m−1,jm=t. Then,(34)σn2EZt2|Ft−1=∑1≤i1<…<im=t1≤j1<…<jm=t∏i,j∈CtcAij−pWij∏i,j∈Ct∗cAij−pWij×E∏i,j∈CtAij−pWij∏i,j∈Ct∗Aij−pWij=∑1≤i1<…<im=t∏i,j∈CtcAij−pWij2∏i,j∈CtEAij−pWij2=∑1≤i1<…<im=t∏i,j∈CtcAij−pWij2∏i,j∈CtpWij1−pWij.LetD=ik,im|1≤k≤m−1 and D∗=jk,jm|1≤k≤m−1. Then,(35)σn2∑t=mnEZt2|Ft−1=∑t=mn∑1≤i1<…<im=t∏i,j∈CtcAij−pWij2∏i,j∈CtpWij1−pWij=∑1≤i1<…<im≤n∏i,j∈DcAij−pWij2∏i,j∈DpWij1−pWij.Now, (32) follows from the following calculation:(36)σn4E∑t=mnEZt2|Ft−12=∑1≤i1<…<im≤n1≤j1<…<jn≤nE∏i,j∈DcAij−pWij2∏i,j∈Dp×∏i,j∈D∗cAij−pWij2∏i,j∈D∗pWij1−pWij=∑1≤i1<…<im≤nE∏i,j∈DcAij−pWij2∏i,j∈DpWij1−pWij×∑1≤j1<…<jn≤nE∏i,j∈D∗cAij−pWij2∏i,j∈D∗pWij1−pWij+oσn4=σn4+oσn4.Hence,∑t=mnEZt2|Ft−1⟶1 in probability.Check conditionII in Proposition 1. By Cauchy–Schwarz inequality and Markov inequality, for any ϵ>0 and generic constant C>0, it follows that(37)E∑t=mnEZt2IZt>ϵ|Ft−1≤E∑t=mnEZt4|Ft−1EIZt>ϵ|Ft−1≤1ϵ2E∑t=mnEZt4|Ft−1EZt4|Ft−1=1ϵ2σn4∑t=mnEZt4=1ϵ2σn4∑t=mn∑1≤i1<…<im=t1≤j1<…<jm=t1≤k1<…<km=t1≤l1<…<lm=tE∏1≤r<s≤mAiris−pWiris∏1≤r<s≤mAjrjs−pWjrjs×∏1≤r<s≤mAkrks−pWkrks∏1≤r<s≤mAlrls−pWlrls=Cϵ2σn4∑t=mn∑1≤i1<…<im=t1≤j1<…<jm=tE∏1≤r<s≤mAiris−pWiris2∏1≤r<s≤mAjrjs−pWjrjs2+Cϵ2σn4∑t=mn∑1≤i1<…<im=tE∏1≤r<s≤mAiris−pWiris4=Cϵ2σn4∑t=mnt2m−2p2M+Cϵ2σn4∑t=mntm−1pM=On2m−1p2Mσn4+nmpMσn4=O1n+1nmpM⟶0,if nmpM⟶∞. Hence, ∑t=mnEZt2IZt>ϵ|Ft−1=oP1. By Proposition 1, the proof is complete.[19, 21]



---

*Source: 7411831-2022-05-26.xml*