聚类系数和度相关性均可调的HK扩展模型

周玉江,王 娟

(深圳大学 信息工程学院,广东 深圳 518060)(*通信作者电子邮箱juanwang@szu.edu.cn)

0 引言

通过研究网络的生长演化模型,可以更好地了解网络的演化规律和形成过程，并且针对社交网络拓扑特性的研究有助于深入认识社交网络的形成过程。

现实生活中,很多复杂网络都具备一些共同的特征,如:高聚类系数、小世界、幂律型度分布等。为了解释幂律分布,学者Barabási和Albert提出BA模型[1],解释了幂律分布产生机理;但BA模型产生的网络,聚类系数几乎为0,为提高BA模型的聚类系数,Holme和Kim提出HK模型[2],该模型具有较高的聚类系数。受到HK模型启发,此后众多学者提出各种适用场合的网络演化增长模型。

钱大千等[3]根据现实社交网络中的熟人推荐原理,提出二步式增长模型(Two-Stage Growth Model, TSGM);王丹等[4]考虑到网络中的旧节点也会发生连接,将 HK 模型中的三角结构扩展到了旧节点之间, 并且考虑到每个时间步新增边的数量不是固定值,提出了度分布和聚类系数可调的扩展HK(Extended HK, EHK)模型;Li等[5]同样考虑到旧节点之间也会发生连接,提出一个聚类系数可调的扩展HK模型;徐玉珠等[6]考虑到在新节点加入时, 可能是单个节点也可能是一个社团, 并且将熟人推荐连接机理应用到旧节点之间进行网络演化，提出了两个度分布与聚类系数均可调的改进HK网络模型;崔爱香等[7]考虑网络演化时会出现加速增长这种情况,提出一种改进的加速增长HK演化模型;李稳国等[8]考虑到每个节点在加入网络时,添加的边数可能不同,提出改进的HK模型。

尽管以上复杂网络增长演化模型抓住了复杂网络演化的基本特征:增长和择优,构造的网络能符合幂律型度分布的特征,但忽略了网络的度相关性。现实生活中,所有的生物网络和技术网络都是负相关的,但是大多社交网络却是正相关,即度值较大的节点更倾向于连接度值较大的节点。高聚类特性和度正相关特性是社交网络的显著特征[9-10]。

最近,一些研究正负相关性可调的网络增长演化模型被提出来。Wang等[11]在权重网络中,将初始吸引度加入到双向选择机制中[12],从而成为了新的双向吸引机制,该模型生成的网络具有正负相关性可调的特性;刘建国[13]先提出一个两步增长模型，随后在两步增长模型的基础上又提出一个度相关性正负可调的复杂网络增长演化模型,通过调节择优参数达到调整网络正负相关性的目的;Catanzaro等[14]在BA模型的基础上,以概率p增加旧节点之间的连接,且旧节点之间的连接以条件概率p(k2|k1)进行,通过调节p可以实现网络正负相关性可调的特性。以上网络增长演化模型未能采用HK模型中的聚类系数可调的优点。

本文在HK增长模型的基础上作出改善,提出聚类系数和度相关性均可调的HK扩展模型(HK extended model with Turnable Degree Correlation and Clustering coefficient, HK-TDC&C)。用该模型能生成各种拓扑的网络,包括高聚类、度相关为正的社交网络。

1 社交网络的统计参量

常用以下统计参量来刻画社交网络拓扑结构:

1)度分布p(k)。

在网络中随机抽取一个节点i,它的度为k的概率可表示为p(k),p(k)通常称为度的分布函数,简称度分布。

2)平均聚类系数C。

社交网络是社会关系的一个反映,在许多真实的社交网络中,一个用户的朋友圈的成员之间的联系通常比较紧密,可用聚类系数刻画这种关系。聚类系数就是一个用户连接中实际存在的三角形数量与所有可能存在的三角形数量之比。平均聚类系数是网络中所有节点聚类系数之和与网络节点总数的商。

3)平均最短路径L及网络直径D。

网络的平均最小路径定义为网络中所有两两节点之间最短距离的算术平均值;而网络直径定义为所有两两节点之间最短距离的最大值。

4)度相关性r。

Newman利用Pearson相关系数r来描述度的相关性:通过任意一条边都可以找到两个节点,进而得到两个节点的度值,这样遍历所有的边得到了两个序列,分析这两个序列的相关性,即为网络的度相关性,用公式[15]可以表示为:

(1)

其中:ki、ji分别为第i(i=1,2,…,M,M为网络的总边数)条边的两个端点的度值。

相关系数r∈[-1,1]。当r<0时,表示网络是负相关的,即异配网络;当r>0时,网络正相关的,即同配网络;当r=0时,网络是不相关的。

近期研究发现,大部分社交网络是正相关的,而技术网络、生物网络是负相关的。

2 现实中的社交网络拓扑结构

本文所用数据集为斯坦福大学收集的Facebook的社交数据[16],该数据集抓取节点4 039个,边88 234条,平均聚类系数C=0.605 5。

计算该网络的以下拓扑参数:平均最短路径、平均聚类系数、相关系数和度分布函数。相关数据如表1所示。

表1 Facebook网络拓扑参数Tab.1 Facebook network topological parameters

通过分析表1,可以发现该网络具有典型的社交网络特征:小世界特性(L=3.690 7)、较高的聚类系数(C=0.605 4)和正相关性(r=0.206 3)。

此外,节点的度分布也是描述一个网络的重要特征, Facebook网络的度分布双对数曲线如图1所示。

图1 Facebook社交网络度分布曲线Fig. 1 Social network degree distribution curve of Facebook

从图1可以看出,Facebook网络的度分布符合幂律分布的特征。

3 聚类系数和度相关性可调的HK扩展模型

利用建模的方式研究网络结构的方法由来已久。早在20世纪60年代,Erds和Rényi[17]利用随机图理论构建了随机网络,称为ER模型,开创了用随机理论创建网络的先例;随后Barabási和Albert[1]对已有的网络模型进行分析后,对网络增长演化模型进行改进,提出实际网络增长过程中具备的两个重要特性:增长和择优。基于以上两个特性,文献[1]于1999年提出了一个无标度网络模型。但BA模型产生的网络,聚类系数几乎为0,为提高BA模型的聚类系数,Holme和Kim提出HK模型[2],该模型具有较高的聚类系数。

HK模型是高聚类系数网络增长演化模型的代表, 在BA模型择优连接(Preferential Attachment, PA)的基础上,引入三角连接(Triad Formation, TF)方法。该模型算法步骤为:首先按照PA步骤连接网络中的一个节点;然后以概率p进行TF方式连接或者以概率(1-p) 再次进行 PA 方式连接, 增加其余的(m-1) 条边,使得网络聚类系数随参数p变化。

3.1 本文提出的演化增长模型HK-TDC&C

HK模型可以同时实现网络的高聚类系数和无标度特征, 成功地实现了复杂网络中小世界特征与无标度特征的统一。但该模型在连接时,过分强调度基于度值的优先连接,所以新加入的节点更倾向于连接度值最大的节点,造成网络度值出现负相关的情况。

本文在HK模型的基础上进行改进,提出HK-TDC&C模型。该模型在上述TF连接步骤中,通过调节参数,分别实现择优与择弱的连接,解决HK模型中度相关性为负数的状况,可以实现网络的聚类系数和相关性均可调的目的。HK-TDC&C模型演化步骤如下:

1)初始状态。网络初始状态含有m0个完全连接的节点。

2)每一个时间步内,一个新的节点v连同m条边加入网络。

3)在生成的网络中,按照式(2)的概率,随机选取网络中的一个任意节点(包含初始状态的m0个节点)i,添加一条边。这种连接方式通常称为PA择优连接;

(2)

4)以概率p按照改进的三角连接(Improved Triad Formation, ITF)方式进行连接,或者以概率1-p再次进行PA方式连接, 增加其余的m-1条边。其中p为三角连接概率。

ITF规则是指对于已经选定的一个节点i, 按照式(3)的概率随机选取它的一个邻居节点a进行连接。

(3)

其中:Γ(i)表示节点i的邻居节点集合。β称为择优参数,用于调整网络的度相关性。当β>0时,度值高的节点有较高的连接概率,属于择强连接;当β<0时,度值低的节点有较高的连接概率,属于择弱连接;当β=0时,节点i的所有邻居节点被选中的概率相同,此时改进模型与HK模型等同。

在HK-TDC&C网络演化模型中,步骤3)的PA连接和步骤4)的ITF连接,这两种连接方式可用图2作进一步说明。

图2 PA连接方式和ITF连接方式Fig. 2 PA connection method and ITF connection method

图2(a)表示PA连接方式:新节点加入网络时更倾向于连接度值较大的节点;图2(b)表示ITF连接方式,选定节点i的非邻居节点(图中以画叉节点表示)不能选,只能按照式(3)的概率,随机选取节点i的邻居节点进行连接,如连接节点a。

5)返回步骤2),直到满足终止条件:网络的规模N达到所希望的值,生成了一个节点数为N的网络。

3.2 度分布的分析

根据3.1节对HK_TDC&C模型的描述,采用连续场理论[1]。在该模型中,研究网络中某一节点i的度值ki随时间的变化,假设其度值是连续变化的,则如下表达式成立:

(4)

其中:m是每个时间步时加入的边数量；G为网络中所有节点的集合。

以下分别详细讨论择优参数β取值为0和非0的情况,对度分布产生的影响。

1)β=0的情况。

由式(4)可以得到如下等式成立:

(5)

由于网络中节点数量之和等于边的数量之和的两倍,每一时间步t有下式[1]成立:

(6)

将式(6)代入式(5),并解微分方程可以得到:

(7)

该微分方程的初始条件为:

ki(ti)=m

(8)

式(8)表示在ti时刻节点i的度值为m。其中，ti为节点i加入网络的时间。

例(5)：If he buys two cents worth of peanuts, his father says, “ Remember what Franklin has said, my son- ’ A groat a day’s a penny a year ”

由初始条件,可以得到方程式(7)的解为:

ki(t)=m(t/ti)1/2

(9)

其中:t表示网络建立的总时间。可以看出,ti越小(即节点加入网络越早),度值越大,符合社交网络“富者越富”的现象。

假定用户节点都是等时间间隔加入到网络系统,则ti是一个均匀分布,密度函数可写为:

(10)

结合式(9),ki的分布函数可以表示为:

(11)

(12)

所以度的分布函数为:

(13)

系统在经历过足够长的时间后,当t→ ∞,式(13)可写为:

p(k)=2m2·k-3

(14)

综上所述,在β=0时,HK-TDC&C模型完全符合幂律分布的特征,且γ=3。

2)β≠0的情况。

(15)

由式(15)可以得出该模型的度分布并非严格服从幂律分布的结论。而通过分析图1中Facebook社交网络的双对数曲线,可以看出:现实网络中的度分布具有幂律分布的趋势,而并非严格地服从幂律分布。因此,HK-TDC&C模型可以理解为在严格的幂律分布的基础上叠加了一些噪声。

可以通过调节模型中的参数:连接概率p及择优参数β,对网络的聚类系数、度相关性进行修正,使之能更好地接近现实中的社交网络。

4 实验与评估

下面通过仿真的方法,按照HK-TDC&C模型算法生成一个网络,并分析该网络的各拓扑参数:度分布特征P(k)、平均最小路径L、聚类系数C、度相关性r。

实验参数设定如下:初始网络节点数m0=20,每步添加的边数m=18,网络节点数量N=2 000,p和β作为网络的调节参数。

1)择优参数β对网络结构的影响。

取p=0.8,当择优参数β=-0.8,0,0.8时,生成网络的各参数如表2所示。

表2 择优参数β对网络的影响Tab.2 Influence of preferred parameters β on the network

通过分析表2,可以得出:

①当β取值为负值时(β=-0.8),可以生成正相关网络。对比表1中的Facebook网络数据,可以看到,网络的各项参数,如网络直径D、平均最小距离L、度相关系数r,都能较好地符合真实社交网络特征。平均聚类系数C有待进一步提高,但在大多数社交数据集中,平均聚类系数C通常为0.2左右[9]。

②当β取值为0时,HK-TDC&C模型与HK模型等同。可以发现,HK模型及其后的扩展模型[3-8],由于未采用择优参数进行调节,生成的是不相关网络(或称为较弱的负相关网络),这是该类模型的共同特征。

③当β取值为正时,可以生成负相关性的网络。

2)连接概率p对网络结构的影响。

取β=-0.8,当p=0.2、0.5、0.9时,生成网络的各参数如表3所示。

表3 连接概率p对网络的影响Tab.3 Influence of connection probability p on the network

通过表3,可以看出:聚类系数和度相关系数都与择优参数p正相关,即p取值越大,聚类系数和度相关系数也越大。

3)网络的度分布情况。

取p=0.8,β=-0.8,0,0.8的情况下,度分布双对数曲线如图3所示。

图3 HK-TDC&C网络度分布曲线(p=0.8)Fig. 3 HK-TDC&C network degree distribution curve (p=0.8)

通过图3可以看到:HK-TDC&C模型构建的网络,它的度分布符合幂律分布的特征。

4)基于上述1)、2)、3)项对HK-TDC&C模型的数据分析,可以看到,在β取负值(如-0.8),p取值较高(如 0.8)的情况下,该模型生成的网络能较好地符合社交网络的基本特征:度值服从幂律分布、度的正相关性、较高的聚类系数、较短的平均距离。因此该模型可用来生成各种拓扑结构的社交网络。

5 结语

本文以HK模型为基础,提出了一种新型的社交网络建模方法:通过调节择优参数β实现不同程度的择优或择弱连接,实现网络正负相关性可调的目的。仿真结果表明,通过选取适当参数,该模型生成的社交网络具有的拓扑特征与社交网络相符,包括:高聚类系数、较短的平均最短路径、度的幂律分布特性、度的正相关特性。本文算法构造的社交网路与真实社交网络各参数相比,较为接近。