一种无标度超网络动态模型的建立与分析

邹灵果，周志东

(1.厦门海洋职业技术学院 公共教育学院，福建 厦门 361009；2.广西师范大学 数学与统计学院，广西 桂林 541006)

自20世纪末Watts-Strogatz[1]模型和arBabsi-Albert[2]模型的提出以来，学术界掀起了对复杂网络研究的热潮。在过去的十年中，复杂网络理论作为一种有效描述复杂自然系统和社会系统的有用工具，引起了学者们的广泛关注，成为物理学、生物学、计算机科学、社会学、经济学和管理学等领域的研究热点。在复杂网络中，通常用节点来表示实际系统中的不同个体，用边来表示节点之间的关系，每条边只能与两个节点关联。此外，增长和优先连接被认为是复杂网络的两种基本机制。随着现实网络的发展，边和节点的数量越多，边和节点的类型就越多样化，网络结构也就越复杂。因此，复杂网络已不能完全描述复杂系统的特征。例如，在科学协作网络中，一条边只能描述两个作者之间的协作，但是我们不知道两个或更多的作者是否是同一篇论文的共同作者。此外，Lv等人[3]和G.Ghoshal等人[4]讨论了由用户、资源和标签推荐三种节点组成的系统，这是复杂网络难以描述的。为了解决这个问题，表示这些系统的一种自然方法是使用超图的泛化，[5-6]即超网络。Berge[7]提出了超图理论的基本概念和性质，其中超边包含两个以上节点。基于超图理论的超网络可以有效地揭示各种节点和边缘的影响和相互作用，并有效地描述这些真实系统。例如，在科学协作超网络中，作者和论文分别被视为节点和超边。超网络与复杂网络的区别在于，后者的每条边只能连接两个节点，而超网络中的边可以连接两个以上的节点，因此称为超边。方认为超网络是网络科学研究中最先进的课题之一，具有重要的研究意义和价值[8]。Park等将超网络的概念应用到细胞生物分子系统中，发现超网络结构对于发现多变量高阶交互作用的构建模块非常有帮助。[9]此外，Park等人将超网络模型应用于癌症诊断的微阵列数据分析。Akram和Dudek[10]开发了超网络的应用，明确地将直觉模糊理论与超网络概念相结合，并定义了几种比经典模型更灵活的直觉模糊结构等等。超边缘增长和超边优先连接是超网络研究的重点。在我们的生活中经常会有这样的一些现象，比如导演拍摄一部新的电视剧，往往想要选择成熟和著名的演员。一个新的网页总是倾向于链接到一个著名的或流行的网页。一份手稿总是引用该领域更权威的来源等等。这些现象具有固有的优先连接规则，允许这些系统发展。基于这些现象，Barabasi和Albert抽象了复杂网络中的无标度演化机理模型。受BA模型配方的启发，众多学者研究了演化超网络的拓扑性质和生成机制。张等[11]基于用户的背景知识、对象和标签建立了双优先依恋机制增长模型。王等在文献[12]提出了一种基于增长和优先附加机制的进化模型，即在每一个时间步，增加m个新节点，选择一个旧节点和这m个节点构建一条新的超边。Hu等人[13]提出了另一种进化模型，即在每一个时间步上增加一个新节点，一个新的超边包含该新节点和m个已有节点。Guo等人[14]生成了超网络与复杂网络的组合模型，其中新一批m1个节点与m2个旧节点组成m条超边。上述进化的超网络模型均为节点和仅随递增的超边。然而，在许多现实网络中，不仅新节点和超边会被淹没，旧节点和超边也会消失。这种动态的增减进化过程比以上纯增长超网络模型更广泛，更符合适者生存的自然进化规律。例如，在科学合作的超网络中，相当规模的论文都是由已发表论文的作者完成的，此时超网络中不添加节点，只添加超边。随着时间的推移，一些作者的合作关系消失或与其他作者形成新的合作关系。这种现象可以理解为：在超网络早期，超边更有可能以连接新节点的形式增加，随着时间的推移，旧节点之间会产生越来越多的超边。在超网络的后期，节点和超边会随着协作的结束而减少，或者超边会随着其他作者的协作而重新连接，形成新的超边。显然，它可能不适合用于上述进化中的超网络表示。那么我们该如何表示这类问题呢。为了解决这个问题，基于超网络理论，在本文中，我们引入一个节点和超边有增有减的进化超网络模型，将新节点的加入可以生成新的超边，超网络中旧节点之间可能会消失或重新连接。根据这些过程的相对频率，一个新的演化超网络会出现，其中不仅有新的节点和新的超边的增长，而且旧的节点和旧的超边也在消失。除了通过增加新节点来增长超边之外，网络中旧节点之间也有可能构造新的超边。与文献[12-14]中仅增加节点和超边的超网络模型相比，这种节点和超边增加和减少的演化超网络模型更真实地描述了现实系统。利用泊松过程理论和连续化技术，得到了该超网络的稳态平均超度分布。分析结果表明，演化超网络服从广义幂律分布，具有“倾向性地依附”的现象，通过设置适当的参数，演化超网络模型具有广泛的一般性。对稳态平均超度分布和度分布的理论预测与数值模拟结果吻合较好。

1 超网络的基本概念及拓扑特征量

超网络分为基于网络的超网络和基于超图的超网络。基于网络的超网络(Supernetworks)是指由网络组成的网络，其概念最早是由Denning[15]提出的。Nagurney等[16]将规模巨大、连接复杂的网络，或网络中嵌套网络的大型网络称为超网络。他们在处理物流网络、资金网络和信息网络相交织的问题时，将 “高于而又超于现存网络”的网络用超网络来描述。其特点是网络节点本身可以是一个复杂网络，不具有同质性，而具有多层、多级、多维、多属性等特性。基于超图(Hypergraph)的超网络(Hypernetwork)，Berge最早给出了超图理论的基本概念和性。Estrada和Rodrigues[17-18]认为，凡是可以用超图表示的网络就是超网络。超图的数学定义为[19]：在图中，一条边只连接两个节点，而超图中的一条边可以包含两个以上的节点，这些节点具有不同的特性，因此我们称之为超边。超图的数学定义为：设V={v1,v2,...,vn}是一个有限集，Ei={vi1,vi2,...,vik}(vij∈V,j=1,2,...,k)，Eh={E1,E2,...,Em}是V的子集。则称二元关系H=(V,Eh)叫做超图，简单表示为(V,Eh)或H。V的元素称为超图的节点，Eh中的元素Ei(i=1,2,...,m)是V的非空子集叫做超边。在超图中，如果两个节点属于同一个超边，则它们是相邻的；如果两个超边的交点不为空，则称这两个超边是相邻的。如果V的基数|V|和Eh的基数|Eh|是有限的, 则H是一个有限超图。如果|Ei|=k(i=1,2,...,m)，那么H是一个k-均匀超图。如果|Ei|=2(i=1,2,...,m)，那么H退化为图。通过以上超图的定义，我们可以给出数学中基于超图的超网络定义，设Ω={(V,Eh)|(V,Eh)是有限超图}且G是从T=[0,+)到G的映射，对任意给定的t≥0，G(t)=(V(t),Eh(t))是一个有限超图。指数t通常被解释为时间，设N*(t)表示时刻t时超图的总节点数，如果{N*(t),t≥0}是一个随机过程, 对于充分大的时间t，我们称{Gh(t)=(V(t),Eh(t))}是一个超网络。假设(有限或无限)，其中E[N(t)]表示时刻t时超网络中的平均节点数。因此，超网络是复杂网络的延伸。对于任何给定的有限超图(V,Eh)和t≥0，记G(t)=(V,Eh)。可见，超网络是超图的推广。复杂网络的底层结构是图，而超网络的底层结构是超图。不同于超图理论侧重于静态结构的讨论，超网络更多的关注于动态演化过程。复杂网络可以视为超网络中的一个特例“2-均匀超网络”(即每条超边只关联两个节点)。由于超图中的超边基数在演化过程中允许动态变化，使得它更适合刻画复杂多变的要素关系，为刻画复杂动态系统提供了新工具。此外，超网络是超图的泛化。常见的表示形式有矩阵形式(包括邻接矩阵、关联矩阵和拉普拉斯矩阵)和图示化形式。如图1所示，当超边中的节点只有两个时，用直线连接；当节点为1个或3个以上时，则用一条包含所有节点的简单闭合曲线表示。超图的相关概念还包括链、路、环；局域超图、子超图、对偶超图、均匀超图、正则超图等。

图1 超图的图示化表示

在进化的超网络模型中，我们关注节点超度这个拓扑特征量，vi的超度定义为连接到节点vi的超边数。在进化机制中，我们的目标是研究超网络的稳态平均超度分布。

2 超网络模型的描述和分析

设N(t)表示时刻t节点的批次总数。假设新节点批次按照泊松进程N(t)到达系统，速率为m1。利用泊松过程理论[20]，得到E[N(t)]=m1。符号tn用于表示第n批节点进入超网络的时间，hj(t,ti)表示第i批的第j个节点的超度。超网络模型演化规则定义如下:

1)超网络从一个初始节点M0和一个小数目E0的超边开始，节点以速率m1按照泊松过程到达系统。图2中描述了演进模型的一个示例。

2)选择第i批次的第j个节点形成超边的概率hj(t,ti)与超度hj(t,ti)的次线性函数成正比，因此

(1)

其中hj(t,ti)表示第i批次的第j个节点在时刻t的超度，ti表示i批节点进入超网络的时间，也就是说第i批节点的诞生时间为ti。在每个时间步骤中，我们执行以下三个操作之一(参见图2)。

图2

(i)基于概率P，我们添加m(mM0)条不重复的超边：为此，我们根据概率优先连接从现有节点中选择m0个节点，并生成超边，结合新超边优先指向具有高连接数目的流行节点的事实[2]。选取第i批第j个节点形成超边的概率根据公式(1)，此过程重复m次。

(ii)以概率q重新连接m条超边：我们随机选择一个节点j和一个包含节点j的超边。接下来，我们删除这条超边，然后根据概率优先连接从现有节点中选择m0个节点生成新的超边。每次根据公式(1)选择第i批第j个节点，此过程重复m次。

(iii)在时间t时，以1-p-q的概率向超网络中新添加一批m1个节点，然后将这批m1个节点与之前已有的m2(m1+m2=m0)连接起来，形成一个新的超边。共形成m条新的不重复的超边且mm2M0。在时刻t，根据公式(1)，新一批节点连接到第i批第j个节点的概率∏(hj(t,ti))与该节点的超度hj(t,ti)成正比。

图2(a)初始时刻t=0时初始节点M0=7，每条超边含有m0=3个节点和初始超边为E0=2的进化超网络模型的进化示例图。在下一个时间步骤(t=1)，出现如下的三种可能时间之一。

(i)以概率P增加m=3条超边。其中一条新的超边是随机选择的, 其他超边是按照优先连接(1)式选择节点形成的。新形成的超边用虚线绘制。

(ii)以概率q重连m=3条超边。

(iii)以概率1-p-q增加m1=2新节点与原有网络中的m2=1个节点利用优先连接机制形成m=3条不重复的新超边。

我们假设hj(t,ti)连续变化，且∏(hj(t,ti))的变化概率可以解释为hj(t,ti)的变化速率。因此，过程(i)-(iii) 都对hj(t,ti)有贡献，在连续系统理论中，每一个的贡献如下：

(I)以概率P，我们添加m(mM0)条不重复的超边：在时刻t我们从现有的节点中选择m0个节点形成一条新的超边以及第i批第j个节点被选中的概率为

m0[∏(hj(t,ti))]1[1-∏(hj(t,ti))]m0-1

≈m0∏(hj(t,ti))，因此，我们有

(2)

其中右边的m等于新生成的超边。

(II)以概率q重新连接m条超边：

(3)

其中N是系统的大小。第一项表示删除超边的节点的连接性减少，第二项表示重建超边的节点的连通性增加，这类似于 (I)。在重构过程中，总连通性不发生变化，但可以通过分离两个过程来计算，这个过程重复m次。

(III)以1-p-q的概率向超网络中新添加一批m1个节点形成m条不重复的超边：

(4)

这批m1节点与之前已有的m2连接起来，形成一个新的超边，第i批第j个节点被选到的概率为m2∏(hj(t,ti))。通过添加上述三个过程(2-4)的贡献，我们可以得到

(5)

在(5)式中系统的大小N和总的超度∑ijhj(t,ti)根据N(t)=M0+(1-p-q)m1t和 ∑ijhj(t,ti)=m0E0+m(m1+m2)pt+m(m1+m2)(1-p-q)t+[M0+(1-p-q)m1t]随时间的变化，这表明对于大的t，我们可以忽略初始常数M0和E0的值相比于随时间线性增长的项。因此，我们有

(6)

(6)式的解hj(t,ti)，结合在ti时添加的第i批节点的初始条件下的连通性满足hj(ti,ti)=m，有

(7)

其中

(8)

(9)

节点具有连接性的概率hj(t,ti)小于k，即P[hj(t,ti)

P[hj(t,ti)tC*)

(10)

所以时间ti服从参数为(i,m1)的伽马分布，因而有

P(ti

(11)

由(10)式我们可以得到

P[hj(t,ti)≥k]=P(titC*)

(12)

对任意给定的k≥m,i,n,t>0和ti

P[hj(t,ti)≥k]

=P[hj(t,tn)≥k]

(13)

不等式(13)表明超网络存在着一种“倾向性地依附”的现象，并且超网络演化模型有一个中心节点集。下面，我们证明在超网络演化模型中稳态平均超度分布的存在性。由(12)式我们可以得到

(14)

(15)

不等式(13)式和(15)式呈现出进化超网络的无标度性质，稳态平均超度分布具有以下广义幂律形式

P(k)∝(k+κ*)-γ*

(16)

其中

(17)

(18)

把(8)式代入(18)式，我们可以得到超度分布的指数为

(19)

通过对演化超网络模型的分析，我们发现当我们设置不同的参数时所构建的演化超网络模型具有广泛的一般性。例如当设p=q=0,m=1,m0=2,m1=1和m2=1时，超网络模型退化为[2]中的BA模型，平均超度分布的指数为γ*=3；结合条件m0=m1+m2，设p=q=0,m=1和m1=1，则超网络模型为[13]中的模型；当p=q=0，超网络模型为[14]中的模型；当m1=1和m2=1，超网络模型是局部事件模型[16](注意：这里m0=1，因为在这种情况时第i批的第j个节点被选中一次的概率为1×∏(hj(t,ti))，即m0=1)。由此可见，我们的超网络模型统一了[12,14]中的超网络模型和[13,21]中的复杂网络模型。

3 超网络模型的数值模拟与分析

在接下来的仿真中，通过数值仿真对演进的超网络模型进行计算机仿真。为了消除噪声，对累积超度分布和度分布进行了仿真。仿真结果显示在双对数轴上。图中蓝色圆圈为仿真结果，绿色星号分别为理论计算形式(15)式。根据模型的进化机制，在选择节点加入超边时，遵循概率优先连接机制。因此，节点获取新超边的能力是不相等的。随着新节点的出现，它们倾向于连接到最有吸引力的节点，因此随着时间的推移，这些节点会比那些吸引力较小的节点获得更多的超边。

这一过程通常有利于最具吸引力的节点，结果是最具吸引力的节点中的一小部分将获得一定数量的超边。通过对参数t,M0,E0,m,m0,m1,m2,p,q取适当的值。分析表明，只要这些合适的值满足演化超网络模型所建立的条件，且条件p+q<1可保证新的批处理节点进入超网络，则所有的超度分布都呈现幂律形式。例如，如图3设

图3 数值模拟结果与稳态平均超度分布P(k)理论预测结果的比较

t=100000,M0=200,E0=10,m=3,m0=5,m1=3,m2=2,p=0.4,q=0.2

和如图4设

图4 数值模拟结果与稳态平均超度分布P(k)理论预测结果的比较

t=100000,M0=30,E0=6,m=2,m0=6,m1=3,m2=3,p=0.1,q=0.1。

可知，理论计算的超度P(k)结果与仿真结果吻合较好。

在模拟中设置t=100000,M0=200,E0=10,m=3,m0=5,m1=3,m2=2,p=0.4,q=0.2。蓝色圆圈为仿真结果，绿色星形为公式(15)的理论计算结果。

这里设置t=100000,M0=30,E0=6,m=2,m0=6,m1=3,m2=3,p=0.1,q=0.1。蓝色圆圈为仿真结果，绿色星形为公式(15)的理论计算结果。

4 结论

本文提出了具有加减运算的进化超网络模型，该模型中不仅新节点和新超边在增长，而且还有旧节点和旧超边的消失。除了通过增加新节点来增长超边之外，网络中旧节点之间也有可能构造新的超边。这种同时增加和减少的进化超网络模型比仅增加节点和超边的模型更具有现实性。通过对现实网络的研究，我们发现获得新的超边的概率取决于允许这些系统成长的优先连通性的内在规则，优先机制能更好地反映进化过程。通过理论分析，得到了该超网络的稳态平均超度分布，超度分布的解析表达式。分析结果表明，超网络服从广义幂律分布，幂指数为γ*且存在“倾向性地依附”的现象。数值模拟验证了平均超度分布的理论预测，与实际模拟结果吻合较好。通过设置适当的参数，该模型可以退化为BA模型、复杂网络中的BA-局部事件模型和无标度超网络模型，证明了该模型的普遍性。本文的目的是为超网络的发展提供一种方法和一些有意义的参考。目前对超网络拓扑特征和演化机制的研究刚刚起步。虽然已有学者对超网络的拓扑性质进行了研究，但对超网络进行实证研究的文献仍然很少。此外，已有的研究简化了节点和超边的关系和特征。加权超网络、定向超网络、老化超网络、超网络与退出机制的结合等问题有待于进一步研究。演化超图的研究是未来多学科研究的必要内容。这些进化超图在现实系统研究中的应用也值得进一步研究。我们期望我们的结果能够帮助我们加速进化超图的发展。从这个角度来看，本文提出的模型可以作为对进化超网络进行真实建模的一个起点。