超网络模型构建中优先连接方法研究

孟 磊,冶忠林,赵海兴,杨燕琳

(1.青海师范大学 计算机学院,西宁 810016; 2.青海省藏文信息处理与机器翻译重点实验室,西宁 810008;3.藏文信息处理教育部重点实验室,西宁 810008)

0 概述

随着复杂网络的兴起与迅速发展,其为网络的研究提供一个新方向,并对现实世界有了更好的认知。自Watts-Strogatz模型[1]与Barabási-Albert模型[2]被提出以来,学术界对复杂网络的研究不断深入,其研究领域也在不断扩展。近年来,复杂网络作为一种能够很好地描述复杂的自然科学和社会系统的工具,已经广泛应用于交通网络、生物网络、科研合作网络和社会网络等网络中。然而,到目前为止,复杂网络还没有统一的定义。钱学森给出了复杂网络一个较严格的定义,即具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络。研究复杂网络,实际上是研究其拓扑结构,图论是专门用于刻画和分析网络特性的学科,复杂网络的拓扑结构可以抽象成图论中的普通图来研究[3]。在复杂网络中,通常把实际系统中的不同个体看作节点,系统中个体之间的关系看作边,每条边只能与2个节点相关联。

然而,随着实际网络的发展,边和节点的数量与类型越来越多,网络结构也就越复杂。因此,复杂网络已不能完全描述复杂系统的特征,在现实生活中复杂网络已经不能真实反映出现实世界的特征。例如,在科学协作网络中,一条边只能描述2个作者之间的协作,但是不能描述是否有2个或者更多的作者是同一篇文章的共同作者。在食物网络中,一条边只能表示物种之间具有共同的猎物,但是并不知道具有共同猎物的整个物种群的构成。在蛋白质网络中,一条边只能表示2个复合物之间具有相同的蛋白质,但是对于该蛋白质的其他任何信息均不能得知[4]。文献[5-6]讨论了由用户、资源和标签推荐3种异质节点组成的异质网络,这3种节点很难用复杂网络来描述。为了解决该问题,表示这些系统的一种自然方法是使用图的一般形式——超图[7],可以用节点表示个体,用边表示这些个体具有共同的某种特性,这样图能够表达出网络的更多信息。文献[8]提出了超图理论的基本概念和性质,在超图中,一条超边可以包含2个以上的节点,保留了图的原始特性。基于超图理论的超网络不仅能够有效揭示各种节点和超边之间的相互影响与相互作用,而且能够有效描述这些真实系统。

近年来,随着人们对超图理论的深入研究,基于超图结构的超网络迅速发展,学者们构建了不同的超网络演化模型并对其特性进行分析。文献[9]构建一种基于超图结构的超网络动态演化模型,该超网络模型每次增加若干个新节点,这若干个新节点与原始网络中的一个旧节点相结合生成一条新的超边。文献[10]构建另一种超网络动态演化模型,该模型每次只增加一个新节点,这一个新节点与原始网络中的若干个旧节点相结合生成一条新的超边。文献[11]构建超网络和复杂网络的统一演化模型,并研究超网络无标度特性演化机理和拓扑性质。文献[12]提出一种新的超网络演化模型,在该模型中不仅有新节点的加入,还包含了旧节点与旧超边的消失。文献[13]给出了非均匀超网络模型的构建方法,并分析非均匀超网络模型的演化和拓扑性质。文献[14]根据建立的超网络演化模型分析供应链的演化机制。文献[15]基于科研作者的合作方式,用超图理论构建一个科研合作超网络演化模型,结果发现作者的超度分布符合幂律分布。文献[16]从唐诗的韵脚、韵母角度研究,构建唐诗超网络模型,发现唐诗超网络的超度分布具有无标度性质且具有很高的聚集特性和异配性。文献[17]构建蛋白复合物超网络模型,通过对该模型进行特征分析,获取了识别关键蛋白的方法。

上述超网络演化模型均是基于优先连接构建得到的,这种优先连接机制使得被选择的旧节点超度大于新节点,且超度分布符合幂律分布。本文通过分析现有超网络模型演化过程,采用赌轮法和链表法对优先选择进行了详细描述,利用基于这2种方法构建的均匀超网络模型和随机超网络模型,分析这2种超网络模型超度幂律分布斜率的规律性质,并且讨论了参数的取值对模型构建的影响。

1 超网络

目前,对超网络的定义主要有基于网络的超网络和基于超图理论的超网络2种。其中,基于网络的超网络[18-19]是指连接方式较复杂、规模较大的网络,或者是一个网络中嵌套着另一个网络的多层大型网络。这种由多层网络组成的超网络最早由美国科学家NAGURNEY等人提出,将高于而又超于现存网络的网络称为超网络,该超网络一般具有多层特性、多级特征、多属性或多准则等特性。基于超图理论的超网络是指可以用超图表示的超网络,这类超网络可以将其转化为超图来研究,运用超图的定义及性质分析研究超网络,以解决生活中的实际问题[20]。

超图的关联矩阵的定义为[21]:超图H=(V,E)的关联矩阵B是一个|V|×|E|的矩阵,如果节点vi在超边ei中,则bij=1,否则bij=0。超图H=(V,E)的节点超度分布是指超图H中节点超度的概率分布或频率分布。

2 超网络模型构建方法

2.1 均匀超网络演化模型

在超图理论中,将每条超边中所包含节点数相同的超图称为均匀超图,均匀超图是最简单、最常见的一种超图。均匀超图对应到超网络中即为均匀超网络,根据超网络模型演化过程中节点的增加与选择方式,主要分为以下3种均匀超网络模型:

1)每次选择一个旧节点生成一条新超边[9]:开始网络中只有较少的m0个节点和包含这m0个节点的一条超边,在每个时间间隔t内给网络添加m1个新节点,这m1个新节点与网络中已有的一个旧节点相结合并生成一条新的超边。选取旧节点的概率为节点的超度与原始超网络中所有节点超度之和的比值。

2)每次增加一个新节点与旧节点生成一条新超边[10]:开始网络中只有较少的m0个节点和包含这m0个节点的一条超边,在每个时间间隔t内给网络添加一个新节点,这一个新节点与网络中已有的m2(m2≤m0)个旧节点生成一条新的超边。选取旧节点的概率为节点的超度与原始超网络中所有节点超度之和的比值。

3)超网络统一演化模型[11]:文献[11]建立了统一的均匀超网络模型,开始网络中有较少的m0个节点及包含这些节点数的一条超边,当有m1个新节点加入网络中时,这m1个节点与网络中已有的m2(m2≤m0)个旧节点生成一条新超边,总共生成m(m≤m0)条超边,且不出现重边。选取旧节点的概率为节点的超度与原始超网络中所有节点超度之和的比值。

2.2 随机超网络演化模型

在超图理论中,除了均匀超图以外,还有随机超图。随机超图是指超图中每条超边所包含的节点数是不相同的,对应到超网络中即为随机超网络。日常生活中的很多超网络都是随机超网络,因此对随机超网络进行研究具有现实意义。文献[21]主要描述了以下3种随机超网络模型:

1)等概率生成的随机超网络演化模型:开始网络中只有较少的m0个节点和包含这m0个节点的一条超边,在每个时间间隔t内给网络中添加一个新节点,从0到m0-1之间等概率的取一个随机正整数n(0≤n≤m0-1),将添加的一个新节点与这n个旧节点生成一条新的超边。选取这n个旧节点的概率为节点的超度与原始超网络中所有节点超度之和的比值。

上述3种超网络模型是通过网络的拓扑结构而构建的,根据不同结构构建的基于超图结构的超网络模型,且均匀超网络模型和随机超网络模型都是通过优先连接策略构建得到的。

3 优先连接策略

优先选择原理为:每次选取连接节点i的概率∏dH(i)为节点i的超度dH(i)与原始超网络中已有节点j的超度之和的比值,可表示为:

(1)

在超网络模型构建方法中,通过改变超网络模型演化过程中节点的增加与选择,构建出不同的超网络演化模型。近年来,对超网络模型演化过程中节点的增加方式研究较多,而对如何实现在演化过程中的优先连接没有具体说明。下文对在超网络模型演化中实现优先连接策略的赌轮法和链表法进行介绍。

3.1 赌轮法

赌轮法又称轮盘赌法,是遗传算法中常用的概念,基本思想是个体被选中的概率与其适应度函数成正比关系,可表示为:

(2)

赌轮法的过程是假设群体中全部个体都是适当性分数,由一张饼图构成,群体中每一个个体为饼图中指定的小块,块的大小与个体的适应性分数成比例,适应性分数越高,则其在饼图中对应的小块面积越大。在对个体进行选择时,旋转该轮子直至轮盘停止,看指针停在哪一块,就选中与之对应的个体。

由式(1)、式(2)可知,超网络模型演化时的优先选择是可以通过赌轮法实现的。通过实例详细说明采用赌轮法实现优先连接的过程。假设一个网络中总共有5个节点,每个节点的度分别为d1=4,d2=1,d3=2,d4=2,d5=1,则可计算出每个节点被选择的概率分别为w1=0.4,w2=0.1,w3=0.2,w4=0.2,w5=0.1。

图1(a)为上述5个节点在一个轮盘上的概率分布,图1(b)为累积概率之和分布。将图1(a)转化为图1(b)是相当于将5个节点的累积概率之和放在一个坐标轴上。从图1(a)可以看出,当有一个新节点加入到网络中时,它连接到节点1的概率为0.4,连接到节点2的概率为0.1,连接到节点3的概率为0.2,连接到节点4的概率为0.2,连接到节点5的概率为0.1。新节点连接网络中的已有节点是随机的,但是概率与已有节点的度成正比,即度越大,则越可能被连接。例如,如果由系统产生一个0～1之间的随机数,比如0.6,则选择新的节点与节点3相连。

图1 赌轮法示意图Fig.1 Schematic diagram of the roulette method

赌轮法核心伪代码如下:

1)利用赌轮法从已有的节点中随机选择m个节点与新加入的节点相连。

for i←1 to m do

b←0

random_data←rand(1,1)

aa←find(pp≥random_data)

jj←aa(1)

b←length(find(exist==jj))

2)已经被选择过的旧节点不能再被重新选择。

if b > 0

while b > 0

random_data←rand(1,1)

aa←find(pp≥random_data)

jj←aa(1)

b←length(find(exist==jj))

end while

end if

end for

3.2 链表法

链表法是将节点储存到链表中,节点的度为多少则在链表中将该节点储存几次,然后随机从链表中抽取一个节点作为旧节点。为了方便理解,用一个实例来说明链表法的实现过程。假设一个网络中总共有5个节点,每个节点的度分别为d1=4,d2=1,d3=2,d4=2,d5=1,并将其储存在链表中,如图2所示。其中,节点1的度为4,则节点1在链表中储存4次,但是这4个节点1的位置不一定是连续的。采取随机选择策略时,显然节点1被选择的概率远大于其他节点。

图2 链表法示意图
Fig.2 Schematic diagram of the linked list method

链表法核心伪代码如下:

1)利用链表法从已有的节点中随机选择m个节点与新加入的节点相连。

for i←1 to m0 do

list(i)←i;

end for

d←m0;

e←2;

cs←0;

for n←m0+1;n≤N;n←n+n0 do

t←d+cs*(n0+m);

cs←cs + 1;

if n≤N

if n+add_meici>N

n0←N-n+1;

else

n0←n0

end if

for i←1:n0

list(t+i)←n+(i-1)

sf((n+i-1),e)←1

k←1

exist←zeros(1,m)

while (k

B←randint(1,1,[1,t])

p(k)←B(1,1)

if p(k)>0 & p(k)<(t+1)

b←length(find(exist==list(p(k))))

exist(1,k)←list(p(k))

2)控制已经被选择过的旧节点不能再被重新选择。

if b > 0

while b > 0

B←randint(1,1,[1,t])

p(k)←B(1,1)

b←length(find(exist==list(p(k))))

end while

exist(1,k)←list(p(k))

end if

list(t+n0+k)←list(p(k))

sf(list(p(k)),e)←1

k←k+1

end if

end while

end for

end for

4 超网络仿真实验

分别采用赌轮法和链表法的优先连接策略,构建均匀超网络演化模型和随机超网络演化模型。G(G0,m,n,N)表示一个超网络,G0为初始网络中的节点个数,m为选择的旧节点个数,n为新增节点个数,N为最终网络中节点的总数量,即网络规模。在构建均匀超网络模型时,旧节点不可以被重复选择,在不可重复策略中,旧节点的选择数量一定要小于初始节点数量。在构建随机超网络模型时,旧节点可被重复选择,在可重复选择策略中,旧节点的选择数量可以大于初始节点,这是因为初始节点可被多次选择。为了得到超度分布幂律值的某些规律,本文将每次重复实验50次,以确保斜率和参数值之间的关系不会出现波动。

图3～图5为采用赌轮法和链表法构建的均匀超网络模型在双对数坐标系下的超度分布图。图3是在G0=5、n=2、N=1 000不变的情况下,改变旧节点选择数量m(m=1,2,3)时的超度分布。图4是在G0=5、m=2、N=1 000不变的情况下,改变新增节点个数n(n=1,3,5)时的超度分布。图5是在G0=5、m=2、n=1不变的情况下,改变网络规模N(N=500,1 500,3 000)时的超度分布。

图3 均匀超网络中旧节点选择数量的影响Fig.3 Influence of the number of old nodes selected in uniform hypernetwork

图4 均匀超网络中新节点添加数量的影响Fig.4 Influence of the number of new nodes added in uniform hypernetwork

图5 均匀超网络中网络规模的影响Fig.5 Influence of the network scale in uniform hypernetwork

从图3～图5可以看出,在均匀超网络中,采用赌轮法和链表法拟合出的直线斜率相差不大,且在双对数坐标系下呈不断下降趋势,数据波动较大,少数点的数值较高,多数点数值都较低,均呈幂律分布,表现出无标度特征。其中,在图3中,当改变旧节点选择数量m时,随着旧节点选择数量m的增加,拟合直线的斜率也随之增加。在图4中,当改变新节点添加数量n时,随着新节点添加数量n的增加,拟合直线的斜率逐渐变小。在图5中,当改变最终网络规模N时,拟合直线的斜率略微波动,影响不大。

图6～图8为采用赌轮法和链表法构建的随机超网络模型在双对数坐标系下的超度分布图。其中,图6是在G0=5、n=2、N=1 000不变的情况下,当改变选择旧节点的数量m(m=1,2,3)时的超度分布。图7是在G0=5、m=2、N=1 000不变的情况下,改变新节点添加数量n(n=1,3,5)时的超度分布。图8是在G0=5、m=2、n=1不变的情况下,改变最终网络规模N(N=500,1 500,3 000)时的超度分布。从图6～图8可以看出,在随机超网络中,采用赌轮法和链表法拟合出的直线斜率相差不大,这是因为构建模型时采用优先连接策略,导致在双对数坐标系下数据波动较大,少数点的数值较高,多数点的数值都很低,且呈幂律分布,表现出无标度特征。其中,在图6中,当改变选择旧节点m的数量时,随着旧节点选择数量m的增加,拟合直线的斜率也随之增加。在图7中,当改变新节点添加数量n时,随着新节点添加数量n的增加,拟合直线的斜率反而变小。在图8中,当改变最终网络规模N时,拟合直线的斜率略微波动,影响不大。

图6 随机超网络中旧节点选择数量的影响Fig.6 Influence of the number of old nodes selected in random hypernetwork

图7 随机超网络中新节点添加数量的影响Fig.7 Influence of the number of new nodes added in random hypernetwork

图8 随机超网络中网络规模的影响Fig.8 Influence of the network scale in random hypernetwork

通过以上对比发现,利用赌轮法和链表法构建的均匀超网络和随机超网络的超度在双对数坐标系下均呈幂律分布,且表现出无标度特征。不论是均匀超网络还是随机超网络,在相同实验条件下,赌轮法和链表法的实验结果基本相同,且相差不大。

在当今大数据时代,超网络规模越来越大,为了在有限时间内得到更多的有效网络信息,高效的优先连接机制方法愈发重要。因此,通过本文实验分析发现,链表法比赌轮法更适合网络规模较大的超网络模型构建。

表1为均匀超网络和随机超网络采用赌轮法及链表法仿真的幂律分布斜率绝对值。从表1可以看出,当改变均匀超网络和随机超网络选择旧节点个数时,幂律分布斜率绝对值随着选择旧节点个数的增加而降低,即幂律分布斜率绝对值与选择旧节点个数成反比关系;当改变均匀超网络和随机超网络新节点个数时,幂律分布斜率绝对值随着新节点个数的增加而升高,即幂律分布斜率绝对值与新节点个数成正比关系;当改变均匀超网络和随机超网络最终网络规模时,幂律分布斜率绝对值变化不大且无规律,即幂律分布斜率绝对值与最终网络规模无关。

表1 幂律分布斜率绝对值结果Table 1 Results of the absolute value of the slope of the power law distribution

5 运行时间对比

表2为利用赌轮法和链表法构建均匀超网络及随机超网络的用时统计。从表2可以看出,不论是构建均匀超网络还是随机超网络,赌轮法优先选择策略用时都远多于链表法优先选择策略。赌轮法用时最少约为38 s,而链表法用时最多约为18 s;当超网络模型的最终网络规模为3 000时,赌轮法用时约为70 000 s即19 h,而采用链表法用时仅约为17 s。究其原因,从理论上分析,赌轮法每一次进行节点选择都要从头开始计算累计和,而链表法每一次进行节点选择时只需要将节点放入链表即可,不需要计算累计和,大大缩减了构建时间。因此,构建超网络模型时,采用链表法能够大大缩短实验时间。

通过表2还可以看出,当改变均匀超网络和随机超网络旧节点个数时,随着旧节点个数的增加,超网络的构建时间也随之增加;当改变均匀超网络和随机超网络新节点个数时,随着新节点个数的增加,超网络的构建时间反而缩短;当改变均匀超网络和随机超网络最终的网络规模时,随着最终网络规模的增加,超网络的构建时间大幅增长。

表2 超网络模型构建时间对比Table 2 Comparison of construction time of hypernetwork model s

6 结束语

本文采用赌轮法和链表法详细阐述了超网络模型演化的优先选择过程,利用这2种方法构建均匀超网络和随机超网络模型,并对其特性进行分析。赌轮法和链表法构建的超网络模型超度分布呈幂律分布,且显示无标度特性,说明赌轮法和链表法构建超网络模型是可行的。实验结果表明,合理设置构建超网络模型时的新旧节点个数,可得到任意标度指数的无标度超网络。通过超网络模型构建时间对比发现,对于均匀超网络与随机超网络,链表法构建时间均远小于赌轮法。为了更适应实际应用,下一步将采用逻辑回归模型的方式对超网络进行连接。