具有双峰特性的双层超网络模型*

卢文 赵海兴 孟磊 胡枫‡

1) (陕西师范大学计算机科学学院,西安 710119)

2) (青海师范大学计算机学院,西宁 810008)

3) (青海省藏文信息处理与机器翻译重点实验室,西宁 810008)

4) (藏文信息处理教育部重点实验室,西宁 810008)

随着社会经济的快速发展,社会成员及群体之间的关系呈现出了更复杂、更多元化的特点.超网络作为一种描述复杂多元关系的网络,已在不同领域中得到了广泛的应用.服从泊松度分布的随机网络是研究复杂网络的开创性模型之一,而在现有的超网络研究中,基于ER随机图的超网络模型尚属空白.本文首先在基于超图的超网络结构中引入ER随机图理论,提出了一种ER随机超网络模型,对超网络中的节点超度分布进行了理论分析,并通过计算机仿真了在不同超边连接概率条件下的节点超度分布情况,结果表明节点超度分布服从泊松分布,符合随机网络特征并且与理论推导相一致.进一步,为更准确有效地描述现实生活中的多层、异质关系,本文构建了节点超度分布具有双峰特性,层间采用随机方式连接,层内分别为ER-ER,BA-BA和BA-ER三种不同类型的双层超网络模型,理论分析得到了三种双层超网络节点超度分布的解析表达式,三种双层超网络在仿真实验中的节点超度分布均具有双峰特性.

1 引 言

复杂网络作为描述和分析现实生活中真实网络的网络系统,在不同领域中得到了广泛的应用并取得了丰硕的成果[1-8].随着社会经济的快速发展,现实生活中的网络呈现出了关系更复杂、节点属性更多元化的特点,而一般的复杂网络难以全面、准确地刻画现实网络的特征.鉴于超网络具有大数据、复杂性、多维性和多层次等特点,使得描述和分析关系更复杂、节点属性更多元化的网络具有一定的实际应用价值[9-12].例如,在航空超网络和铁路超网络之间根据乘客换乘行为依次连接机场和铁路站点,形成“航空-铁路”双层超网络模型并在此网络模型的结构基础之上,利用超图理论优化交通规划和乘客换乘行为.如图1所示,第一层超网络为航空超网络,其中超边A1表示航班,包含的节点a1,a2和a3表示该航班经过的三个机场； 第二层超网络为铁路超网络,其中超边R1为铁路运营线路,

包含的节点b1,b2,b3,b4,b5,b6和b7表示该趟列车途经的站点.两层超网络之间的超边C1表示乘客乘坐动车在b4站下车后可以选择a2或a3机场换乘飞机,超边C2表示若乘客乘坐动车在b20或b21站下车,如果打算继续换乘飞机那么就只能选择a6机场.

近年来,基于超图的超网络研究主要分为超网络的实际应用和模型构建两个方面.Estrada等[13]对超网络的子图中心度和聚集系数进行了系统研究,并采用超网络描述了马来西亚热带雨林中的食物网络,通过分析得到了食物竞争关系.Ghoshal等[14]提出并利用随机三部超图对社会化标签网络中的资源、用户和标签三类节点的度分布进行了理论分析,得到了一些重要的结果.Zlatić等[15]在三部随机超图的基础之上,扩展了超度分布、节点相似性和节点间最短路径等拓扑指标的定义,为进一步研究社会化标签网络提供了一个标准工具.Zhang和Liu[16]提出了一种社会化标签网络的三部超图演化模型,研究了该模型的超度、聚集系数和平均路径长度等拓扑特性,并与实证数据做了对比.Wang等[17]和胡枫等[18]构建了基于超图理论的无标度超网络演化模型,理论分析了该超网络模型的节点超度分布服从幂律分布,并通过仿真实验验证了理论分析结果.郭进利等[19,20]将文献[17]和文献[18]提出的超网络模型进行了统一,分析了该统一超网络的无标度特性演化机理和拓扑特性.Zhou等[21]构建了一种同时考虑新超边增加和已存在超边消失的超网络模型.李甍娜等[22]以唐诗为节点,以韵母为超边构建了唐诗超网络,发现该超网络服从无标度分布且具有较高的聚集性和异配性.胡枫等[23]构建了蛋白复合物超网络模型,并分析得出了识别关键蛋白的方法.与此同时,多层超网络的发展也极为迅速.方锦清等[24,25]从多角度出发思考和探索了多层超网络,提出了三层超网络演化模型,定义了两种层次交叉度,并用其描述了层间节点的合作竞争关系和超网络的鲁棒性.Boccaletti等[26]详细描述了多层网络,并从基本结构入手分析了多层网络的动态变化过程.蒋文君等[27]就多层网络级联失效的预防和级联失效后的恢复做了整体性讨论.杨喜艳等[28]基于马尔科夫链方法建立了双层谣言传播网络模型,并提出了一种能够有效阻止多层社交网络谣言传播的动态控制策略.

图1 “航空-铁路”双层超网络模型Fig.1.Airline-Railway double-layer hyper network.

网络模型既可以刻画网络的结构特征,也可分析网络的动力学.ER随机网络模型是由匈牙利数学家Erdös和Rényi在[29]20世纪50年代末提出的,是复杂网络和现实生活中最为常用的一种随机网络模型.近年来,ER随机网络在不同领域得到了广泛的研究与应用,Xu[30]在ER随机网络模型中研究了经典的量子游走问题,结果表明,量子在游走过程中的返回概率,即在初始节点找到量子的概率正比于ER随机网络的边连接概率,且当ER随机网络趋于全连通时,其返回概率会出现激增的现象.Xue[31]在ER随机网络中利用大数定律改进了SIR传播模型.Lima等[32]在有向ER随机网络上研究了多数投票模型,通过蒙特卡罗模拟得到了“有序-无序”相变的关键参数.Zehmakan[33]将社会网络抽象为ER随机网络,发现了社会成员的观念在网络连通性达到某个阈值时会发生改变.李炎等[34]研究了ER随机网络中的Achlioptas爆炸渗流模型的相变性质,结果表明,ER随机网络中的爆炸渗流相变是一种奇异相变,它既不是标准的不连续相变,又与常规随机渗流表现出的连续相变处于不同的普适类.在经济快速发展和“大数据”时代的社会背景下,超网络已经成为了网络科学的重要研究方向之一,为更好地应用超网络,超网络模型的构建是不能忽略的.目前,超网络模型的研究成果主要集中在无标度超网络模型的构建中,对基于ER随机图理论的ER随机超网络模型研究尚属空白.本文针对此问题,首先提出了一种ER随机超网络模型的构建方法,并分析得出了节点超度分布的解析表达式,仿真实验结果表明,本文提出的ER随机超网络的节点超度分布服从泊松分布,符合随机网络特征并与理论推导一致.为描述更为复杂的多层、异质关系的网络,进一步构建了节点超度分布具有双峰特性,层间采用随机方式连接,层内分别为 ER-ER,BA-BA 和 BA-ER 三种不同类型的双层超网络模型,理论分析得到了三种双层超网络节点超度分布的解析表达式,并通过仿真实验对其进行了验证.

2 ER 随机超网络

2.1 ER随机超网络模型的构建方法

在超图结构中引入ER随机图理论,提出了一种ER随机超网络模型,记为H(N,p) ,构建过程如下：

1)初始化： 给定节点数量N和超边连接概率p,p∈[0,1]；

2)在N个节点中任意选择r个不相同的节点,r≤N；

3) 生成一个随机数s,s∈(0,1) ；

4)如果s＜p,将第2步中选择的r个节点组成一条超边；

5)重复2)—4)步,直至所有的r个不相同的节点都被选择一次.

在以上的构建过程中,由于每次选择r个节点形成一条超边,因此本模型构建的超网络为r均匀超网络.最终生成的超边数量

2.2 ER随机超网络节点超度分布理论分析

在本文提出的ER随机超网络中,一个节点与其他r-1 个节点组成一条超边的概率为pk(1-p)F-k,其中则网络中一个给定节点超度为k的概率分布为：

网络节点的平均超度为

所以,当ER随机超网络的节点数N较大并且超边连接概率p较小时,节点超度为k的二项分布近似为泊松分布：

其中,〈λ〉=p×F.

2.3 仿真实验

图2 为N=500 ,r=3 时,在超边连接概率p=0.004,p=0.006 ,p=0.008 和p=0.01 四种不同条件下取100次平均值的节点超度分布情况.

图2 500 个节点的随机 3 均匀超网络在不同连接概率 p 值时的节点超度分布 (a) p =0.004 ； (b) p =0.006 ； (c) p =0.008 ；(d)p=0.01Fig.2.The hyper degree distribution of 3-uniform random hyper networks under different p： (a) p =0.004 ； (b) p =0.006 ；(c) p =0.008 ； (d) p =0.01 .

从图2(a)—图2(d)可以看出,本文提出的ER随机超网络模型的节点超度分布在四种不同超边连接概率条件下均服从泊松分布并与理论分析结果一致,符合随机网络特征.

3 双层超网络模型

超网络在描述复杂多元关系的系统时有着较强的优势,而随着一些实际研究工作的展开,我们发现单层超网络在描述多层异质关系时会略显不足.例如在交通网络中,如何准确地描述航空超网络和铁路超网络之间的关系等.针对此类问题,本文构建了节点超度分布具有双峰特性的双层超网络模型,层间采用随机方式连接,层内分别为ERER,BA-BA和BA-ER三种不同类型的双层超网络模型(简记为EE,BB和BE,其中E代表本文提出的ER随机超网络； B代表BA 无标度超网络).本文以双层3均匀超网络为例,分析三种不同类型的双层超网络模型.

3.1 EE双层3均匀超网络

EE双层3均匀超网络包含两层ER随机3均匀超网络,层与层之间采用随机连接方式.

3.1.1 构建方法

EE双层3均匀超网络模型的构建过程如下：

1) 采用本文提出的ER随机超网络模型H(N,p)构建第一层和第二层超网络H1(N1,p1) 和H2(N2,p2) ；

2) 层间连接： 采用随机方式连接层间,即第一层中的任意一个节点与第二层中的任意两个不相同节点以概率p12组合生成一条超边,直至层间形成条超边为止.

3.1.2 理论分析

根据以上构建方法中的第2步可知,EE双层超网络的节点平均超度〈k〉由第一层超网络的节点平均超度〈k1〉和第二层超网络的节点平均超度〈k2〉决定.其中,EE双层超网络中第一层网络中的任意一个节点与层内其他任意两个节点形成超边的数量为与第二层超网络中的任意两个节点形成超边的数量为同理,第二层超网络中任意一个节点在层内形成的超边数量为第二层超网络中任意两个节点与第一层超网络中任意一个节点形成超边的数量为N2(N2-1)p12,故第一层和第二层超网络节点平均超度的计算表达式为：

式中,N1和N2分别为第一层和第二层超网络的节点数,p1和p2分别为第一层和第二层超网络的层内超边连接概率,p12为层间超边连接概率.由(4)式和(5)式可得

EE双层超网络的节点超度分布由第一层超网络的节点超度分布p1st(k) 和第二层超网络的节点超度分布p2nd(k) 组成.第一层超网络中任意一个节点与其他两个节点组成一条超边的概率为p1i(1-p1)F1-i,其中与第二层超网络中的任意两个节点组成一条超边的概率为(1-p12)Q1-(k-i),其中由此可以得出第一层超网络中节点超度为k的概率分布为

同理,第二层超网络中节点超度为k的概率分布为

3.1.3 仿真实验

在EE双层超网络节点超度分布仿真实验中,N1和N2取值为 500,层内连接概率p1和p2为 0.006,层间连接概率p12分别为0.001和0.01,为了结果的合理有效,实验结果取了100次的平均值.

表1为EE双层超网络节点超度分布实验的统计信息,其中N代表双层网络的总节点数,M为层间的超边数量.实验结果表明,EE双层超网络的节点超度分布在不同层间超边连接概率条件下均具有双峰特性,如图3(a)和图3(b)所示.

表1 EE 双层 3 均匀超网络实验统计Table 1.Experimental statistics of EE hyper network.

图3 双层3均匀EE超网络在不同层间超边连接概率时的节点超度分布 (a) p 12=0.001 ； (b)p12=0.01Fig.3.The EE hyper degree distribution of double-layer 3-uniform hyper network under different p 12 ： (a) p 12=0.001 ；(b) p 12=0.01 .

3.2 BB双层3均匀超网络

BB双层3均匀超网络包含两层3均匀无标度超网络,层与层之间采用随机连接方式.在构建3均匀无标度超网络时,采用文献[17]提出的均匀无标度超网络模型构建方法,记为H(m0,m) .该超网络模型的节点超度分布服从幂律分布,符合无标度网络特征.H(m0,m) 模型的构建过程如下：

1) 初始化： 给定初始m0个节点{v1,v2,v3,···,vm0}与一条包含这些节点的超边E0={v1,v2,v3,···,vm0}；

2) 超边增长： 每个时间步t添加m个节点{vt1,vt2,vt3,···,vtm}与一个已存在的节点vi组合成一条新的超边Et={vt1,vt2,vt3,···,vtm,vi}.这个已存在节点的选取方式为“超度优先连接”,即节点vi被选中的概率正比于这个节点的超度,定义为：

式中,分子dH(vi) 为节点vi的超度,分母表示当前网络中所有节点超度之和.在该均匀无标度超网络中,一个给定节点超度为k的概率分布为[18]

式中,m为每次添加新节点的个数,当m=2 时,该超网络为3均匀无标度超网络.

3.2.1 构建方法

BB双层3均匀超网络模型的构建过程如下：

1) 采用H(m0,m) 模型构建第一层和第二层3均匀无标度超网络H1(m10,m1) 和H2(m20,m2) ；

2) 层间连接： 采用随机方式连接层间,即第一层中的任意一个节点与第二层中的任意两个不相同节点以概率p12组合生成一条超边,直至形成条超边为止.

3.2.2 理论分析

由于第一层与第二层超网络均为3均匀无标度超网络,每次增加2个新节点与1个已存在节点组合生成一条超边,所以在层间连接之前,各层超网络的节点平均超度约为 3 /2 .由此可得,第一层超网络的节点平均超度〈k1〉和第二层超网络的节点平均超度〈k2〉分别为：

其中,N2为第二层超网络的节点数,则BB超网络的节点平均超度.

在具有N个节点的3均匀无标度超网络中,超度为1的节点数M(1) 的上下界为N/2+1≤M(1)≤N-1,超度为 2 的节点数M(2) 的上界为M(2)≤N/2.所以,BB 双层超网络的第一层超网络中节点超度为k的概率分布为

同理,第二层超网络中节点超度为k的概率分布为

3.2.3 仿真实验

在BB双层超网络节点超度分布的仿真实验中,第一层与第二层超网络的节点数N1=m10+m1和N2=m20+m2取值为500,其中各层初始节点m10和m20均为 3,层间连接概率p12分别为 0.001和0.01,为了结果的合理有效,实验结果取了100次的平均值.

表2为BB超网络节点超度分布实验的统计信息.与EE双层超网络的结果相同,BB双层超网络的节点超度分布在不同层间超边连接概率条件下均具有双峰特性,如图4(a)和图4(b)所示.

3.3 BE双层3均匀超网络

BE双层3均匀超网络由第一层3均匀无标度超网络和第二层ER随机3均匀超网络组成,层与层之间采用随机连接方式.

表2 BB 双层 3 均匀超网络实验统计Table 2.Experimental statistics of BB hyper network.

3.3.1 构建方法

BE双层3均匀超网络模型的构建过程如下：

1)采用H(m0,m) 模型构建第一层超网络H1(m10,m1)；

2)采用H(N,p) 模型构建第二层超网络H2(N2,p2)；

3) 层间连接： 采用随机方式连接层间,即第一层中的任意一个节点与第二层中的任意两个不相同节点以概率p12组合生成一条超边,直至形成条超边为止.

3.3.2 理论分析

BE双层超网络的节点平均超度〈k〉由第一层无标度超网络的节点平均超度〈k1〉和第二层ER随机超网络的节点平均超度〈k2〉决定,分别为：

其中,N2为第二层超网络的节点数,p2为第二层超网络的层内超边连接概率,p12为层间超边连接概率,则〈k〉=(〈k1〉×N1+〈k2〉×N2)/(N1+N2) .

BE双层超网络的节点超度分布与EE双层超网络和BB双层超网络类似,由第一层无标度超网络的节点超度分布和第二层ER随机超网络的节点超度分布组成.第一层超网络中节点超度为k的概率分布为

第二层超网络中节点超度为k的概率分布为

3.3.3 仿真实验

在BE双层超网络的节点超度分布实验中,第一层与第二层超网络的节点数N1=m10+m1和N2取值为500,其中第一层超网络的初始节点m10为3,第二层超网络的超边连接概率p2为0.006,层间连接概率p12分别为0.001和0.01,为了结果的合理有效,实验结果取了100次的平均值.

表3为BE超网络节点超度分布实验的统计信息.BE双层超网络的节点超度分布与以上两种类型的双层超网络情况相同,在不同的层间超边连接概率的条件下,节点超度分布均具有双峰特性,如图5(a)和图5(b)所示.

图4 双层 3 均匀 BB 超网络节点超度分布 (a)p12=0.001； (b)p12=0.01Fig.4.The BB hyper degree distribution of double-layer 3-uniform hyper network under different p 12 ： (a) p 12=0.001 ；(b) p 12=0.01 .

图5 双层3均匀BE超网络模型节点超度分布 (a)p12=0.001； (b)p12=0.01Fig.5.The BE hyper degree distribution of double-layer 3-uniform hyper network under different p 12 ： (a) p 12=0.001 ；(b) p 12=0.01 .

表3 BE 双层 3 均匀超网络实验统计Table 3.Experimental statistics of BE hyper network.

4 结 论

本文基于经典的ER随机模型构建了基于超图的ER随机超网络模型,通过理论分析得到了该模型的节点超度分布其中泊松分布的期望值λ与超边连接概率p有关,计算机仿真实验结果与理论分析一致.与普通的ER随机网络相比,本文提出的ER随机超网络模型对于描述和分析关系更复杂、节点属性更多元化的随机社会网络具有一定的实际应用价值.同时,在ER随机超网络模型的基础之上,构建了 ER-ER,BABA和BA-ER三种不同类型的双层超网络模型.理论分析发现,三种双层超网络的节点平均超度与层间超边连接概率密切相关,随着层间超边连接概率的增大网络节点的平均超度也随之增大； 仿真实验结果表明,三种模型的节点超度分布在不同的层间超边连接概率条件下均具有双峰特性.

本文提出的ER随机超网络模型和双层超网络模型对今后进一步研究此类超网络的熵、超网络动力学、超网络表示学习、超网络链路预测和交通超网络优化等提供了理论基础,对研究多层超网络的演化具有一定的借鉴意义.