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]。

超图在数学中的定义为^[8]:设V={v₁, v₂, …, v_n}是一个有限集, 若E_i≠Ø(i=1, 2, …, e)且$\bigcup\limits_{i=1}^{e} E_{i}=V$, 则称二元关系H=(V, E)为超图。其中, V中的元素v₁, v₂, …, v_n称为超图的节点, 节点个数用V表示, E={E₁, E₂, …, E_e}是超图中所有超边的集合, 超边个数用E表示。节点v_i的超度定义为包含该节点v_i的超边个数, 记为d_H(v_i)。超边E_i的超度定义为该超边所邻接的其他超边的个数, 即与该超边有公共节点的超边个数, 记为d_H(E_i)。如果2个节点属于同一条超边, 则称这2个节点邻接; 如果2条超边的交集不为空, 则称这2条超边邻接; 如果V和E都是有限的, 则称H=(V, E)为有限超图; 如果每条超边中的节点数都相等, 则称H=(V, E)为均匀超图或一致超图。

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

2 超网络模型构建方法 2.1 均匀超网络演化模型

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

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

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

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

2.2 随机超网络演化模型

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

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

2) 泊松分布生成的随机超网络模型:开始网络中只有较少的m₀个节点和包含这m₀个节点的一条超边, 在每个时间间隔t内给网络中添加一个新节点, 由泊松分布概率p(k, λ)=$\frac{\lambda^{k}}{k!}$·e^-λ(k=0, 1, …)生成一个随机正整数n, 然后添加的一个新节点与这n个旧节点生成一条新的超边。选取这n个旧节点的概率为节点的超度与原始超网络中所有节点超度之和的比值。

3) 确定概率生成的随机超网络模型:开始网络中只有较少的m₀个节点和包含这m₀个节点的一条超边, 在每个时间间隔t内给网络中添加一条新的超边, 每条新的超边里面节点的个数i由概率p_i决定, 且$\sum\limits_{i=1}^{m} p_{i}=1$, 其中, m为最终的网络中超边的个数。每条新的超边里面包含原始网络中旧节点的个数为j(j=0, 1, …, n), 由概率q_j决定j的取值且$\sum\limits_{j=0}^{n} q_{j}=1$。其中, j=0表示选择了0个旧节点即超边中都是新节点; j=n表示超边中的节点都是旧节点。选取i个旧节点的概率为节点的超度与原始超网络中所有节点超度之和的比值。

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

3 优先连接策略

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

$\prod d_{H}(i)=\frac{d_{H}(i)}{\sum\limits_{j} d_{H}(j)} $

(1)

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

3.1 赌轮法

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

$P_{i}=\frac{F_{i}}{\sum\limits_{i=1}^{n} F_{i}} $

(2)

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

由式(1)、式(2)可知, 超网络模型演化时的优先选择是可以通过赌轮法实现的。通过实例详细说明采用赌轮法实现优先连接的过程。假设一个网络中总共有5个节点, 每个节点的度分别为d₁=4, d₂=1, d₃=2, d₄=2, d₅=1, 则可计算出每个节点被选择的概率分别为w₁=0.4, w₂=0.1, w₃=0.2, w₄=0.2, w₅=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) 利用赌轮法从已有的节点中随机选择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个节点, 每个节点的度分别为d₁=4, d₂=1, d₃=2, d₄=2, d₅=1, 并将其储存在链表中, 如图 2所示。其中, 节点1的度为4, 则节点1在链表中储存4次, 但是这4个节点1的位置不一定是连续的。采取随机选择策略时, 显然节点1被选择的概率远大于其他节点。

链表法核心伪代码如下:

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 < m+1)

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

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

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

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

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

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

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

5 运行时间对比

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

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

6 结束语

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