稀疏随机点积图中三角形数量的极限定理

肖云辉，刘 群，2*，李城恩

（1.闽南师范大学数学与统计学院，福建漳州363000;数据科学与统计重点实验室，福建漳州363000）

随着生物、技术和社会网络的日益突出和重要性，复杂网络的研究吸引了来自各个领域的研究人员.自20世纪60年代以来，随机图理论一直是研究复杂网络的基本工具.因此，关于复杂网络模型性质的研究有大量的文献[1-8]，如： Erdös 等[1]提出的简单随机图模型，该模型中每两个顶点独立地以概率P 相连;Bender 等[2]提出了配置图模型，这种模型利用给定的度序列来构建随机图；Hofstad[3-4]提出的广义随机图模型，这种模型是给图中的每个顶点赋予一个权重，这个权重可以是一个确定的常数，也可以是一个随机变量.这些模型都成功地再现了复杂网络的某些特征，然而在这些开发的模型当中，只能在一定程度上捕获观察到的复杂网络的某些特性.为了更好的模拟现实网络数据，Νickel[9]提出了随机点积图模型，它通过对顶点的随机赋值，依照点积规则计算顶点之间的连接概率，通过这种双随机性，从而形成随机图.本文在Young 等[10]的基础上对稀疏情形下的随机点积图做了进一步的研究，并得出了该模型下三角形数量的极限定理.在随机图和复杂网络的研究中，三角形数量的研究吸引了大量学者的注意.例如，可以利用计算三角形的数量研究网络连接的聚集程度[11].然而在大尺度随机图中，分析三角形数量的概率行为并不是一个简单的事.

1 预备知识

一个无向图(有向)G=(V(G)，E(G))包含两个集合V(G)和E(G)，这两个集合满足V(G)≠0，E(G)是一个由V(G)中元素构成的无序(有序)对的集合，V(G)中的元素称为图G 中的顶点，或称E(G)中的元素为边.顶点通常用它在V(G)中的序号i表示，一条边通常被记作(i，j)或Iij，在一个无向图G 中，边可以看成是两个无向图的点对，即当顶点i与顶点j相连时，顶点j也与顶点i直接相连，它们之间是没有方向而言的.而在有向图中，这两个顶点是有先后顺序的，也就是说，Iij≠Iji.

考虑n个顶点上的图G.设映射X:V(G)→Rt，即X(ν)=xν⋅，其中t为正整数.另外，令f：R→[0，1]是一个将向量的点积映射为概率的函数.我们将随机点积图G定义如下：

1)图G在顶点集V(G)上有n个顶点；

2)∀u，ν∈V(G)，则顶点u到顶点ν在图G上存在一条边的概率为：PX[u～ν]=f(xu⋅xν).

在模型中，每个顶点被安排一个取自给定分布的向量xν，则顶点u和顶点ν相连的概率为P(Xi，Xj)=f(xu⋅xν)，也就是说它等于向量点积的一个函数.

为了研究的方便，我们只考虑t=1 的情况.利用类似的分析手法，高维(t＞1)的情形也有类似的结果.具体的，每个顶点ν都赋予服从Ua[0，1]的随机变量xν，其中Ua[0，1]为均匀分布[0，1]上的第a(a＞1)次幂律，即密度函数为因此，在给定xu和xν的条件下，顶点u和v相连的概率为

2 三角形数量

接下来我们将会给出稀疏随机点积图模型下三角形数量的极限定理.

设Tn是顶点变量为x1，…，xn的随机点积图中的三角形数量.以下结果表明，三角形数量依分布收敛于泊松分布，该结论可以用来将来分析复杂网络的“小世界”特征，即具有特征路径长度短，聚类系数高的特性[12].

定理1假设顶点变量x1，…，xn是独立同分布的从Ua[0，1](a＞1)中抽取的，则

从技术上讲，证明一个随机变量依分布收敛到泊松分布，我们可以通过引理1.令(X)r=X(X−1)…(X−r+1)，以及表示X的第r次阶乘矩.

引理1[3-4]对于一个整数随机变量序列(Tn)n≥1，如果满足

其中r=1，2，…，则该整数随机变量序列(Tn)n≥1依分布收敛为参数λ的泊松随机变量.

当给定顶点变量条件时，我们在引理2中计算出三角形数量Xn的第r次阶乘矩.

引理2在顶点变量条件下，三角形数量Tn的第r次阶乘矩为

证明这里我们在r≥1上采用数学归纳法证明.

对于r=1，(Tn)1=Tn，则

其中倒数第二个等式来自于一个事实：在给定顶点变量的条件下，随机点积图中不同边是条件独立的.

为了进一步提出归纳假设，我们将(Tn)r改写成

用Pi1，j1，k1表示在给定条件Ii1j1Ij1k1Ik1i1=1下的条件分布，那么，对于任意事件E，我们有

因此，

定义

那么，在Ii1j1Ij1k1Ik1i1=1条件下，我们可以得到Tn=Yn+1，因此

因此，有

注意到

以及

因此，引理2得证.

由引理1和引理2，为了证明定理1，只需证明(Tn)r的期望的极限是存在的.

引理3当n→∞时，三角形数量Tn的第r次阶乘矩的极限存在，

证明根据引理2，只需证明

注意到

根据大数定律，易得Ii=o(1)，2 ≤i≤3r.

因此，我们现在只需计算I1.

注意到

再结合大数定律得到

故引理3得证.

因此，结合引理1-3，可以得出三角形数量Tn依分布收敛到泊松分布，故定理1得证.