超网络中有寿命节点的进入、老化与退出机制

马涛

（上海工程技术大学管理学院，上海 201620）

0 引言

增长与择优连接是BA 模型的两个特征，该模型认为网络可以无限增长，而且认为节点的寿命也是无限的，不考虑节点寿命长短。然而，现实中的许多网络中，节点是具有寿命的，不同节点的寿命有长短区别，新节点进入到网络后，都会经历这个过程，包括：成长、老化和死亡，例如：市场营销渠道网络中会有新公司进入，也会有公司退出，离开该网络；产业链网络中有的企业可能由于一些原因而被淘汰，也会有企业作为新的一员加入到该产业链中；科学家合作网的节点是有寿命的；电影演员合作网的节点是有寿命的；WWW 网基本上每时每刻都有新的网页进入该系统，也会有网页离开；在自然界中有新的物种出现，也会有一些物种消失。

目前，国内外学者对复杂网络中节点老化现象进行了较多的研究，Moinet 等人[1]描述了网络中节点的老化现象；Goldberg 等人[2]提出节点老化需要在引文网络模型中得到体现，并使用一些数据对模型进行测试，来验证模型是否正确；Dorogovtsev 等人[3]也对节点老化模型进行了研究，认为随着节点寿命的增加，择优性会衰减；Luo等人[4]在进化的传感器网络的拓扑结构中，考虑了能量意识机制，还讨论了网络中的节点和链接的变化；Sarshar等人[5]提出了一种日益增长的网络研究模型，主要包括：新节点和链接的进入，现有链接的重组，以及节点的退出和补偿连接机制。此外，目前也有对复杂网络中的有寿命节点的进入退出机制进行研究的文献，包括：节点具有寿命的企业生产物流系统复杂网络模型[6]和M-G-P 型复杂网络中有寿命节点的进入退出机制[7]。

综上所述，对超网络中有寿命节点的进入、老化与退出机制分析和描述的文献很少。目前，刘艳等人[8]构建了一种基于超图的复杂网络的动态演化模型，在该模型演化过程中，既有新节点和新边增加，也有旧节点和旧边离开，而且不仅新添加的节点可生成新边，网络中的旧节点之间也可生成新边。然而，文献[8]的研究中没有考虑节点的寿命，也没有考虑节点的老化问题。因此，为了更好地理解真实网络的变化，本文考虑到网络中节点是有寿命的，在文献[8]的基础上提出了超网络中有寿命节点的进入、老化与退出机制，新节点被增加到网络之后，都要经历成长、老化和死亡，即新节点进入、进入的节点会老化、老的节点会退出网络。

1 基于超图的超网络

超网络是一般网络的一种自然推广，超网络可以被认为是一种特殊的复杂网络。超网络分为两类：基于超图的超网络和基于网络的超网络。本文研究的是基于超图的超网络。超图的图形如图1 所示。

图1 超图示例

超图表示为：H=(V,E)，共有两个集。V 是一个有限集，V={v1,v2,…,vn} 为节点集；E 为超边集，E={E1,E2,…,Em} ，设Ei≠∅(i=1,2,…,m)，超图示例如图1 所示，节点集V={v1,v2,v3,v4,v5,v6,v7} ，超边集E={E1,E2,E3} ，其 中 ，E1={v1,v2,v3} ,E2={v4,v5} ,E3={v6,v7} 。

基于超图的超网络拓扑结构特征的研究中，对超网络拓扑结构进行衡量的指标包括：节点的度、节点超度、超边度、超边超度及其分布、集聚系数、平均距离等。中心性被用来测量网络中节点处于中心位置的程度。超网络中节点中心性的测量包括：度中心性、介数中心性和接近中心性等。

2 超网络中有寿命节点的进入、老化与退出机制

本文建立了Poisson 连续时间增长节点具有寿命的超网络模型的新节点进入、节点老化和老节点退出的机制。机制的建立描述了超网络的动态变化过程，对用超网络刻画的复杂系统的描述具有借鉴意义。因此，以BA 模型为基础，我们提出了一个节点具有寿命的超网络模型，即节点是具有寿命的，新的节点进入网络、进入的节点会逐渐老化、老的节点会退出网络。超网络中新节点的进入可以形成新的超边，超网络中的旧节点之间的超边可能消失，也可能会产生新的超边。超网络结构在不断地变化，使得超网络表现为一种动态而复杂的网状结构。本文中旧节点和老节点的含义是不一样的，超网络中已有的节点被称为旧节点，而随着节点的老化，该老节点可能被删除。

通过上述分析可知，超网络表现出明显的复杂性和动态性。为了有效研究超网络，我们进行抽象化描述，新的节点进入网络中，还会有新的连边生成，而且，新进入的节点会老化，已存在于网络中的一些老节点也会以一定概率被删除，退出系统。新进入系统的节点在选择旧节点形成新超边时，会有某种倾向性存在，具有连接的偏好特性。旧节点之间的旧超边可能消失，同样旧节点之间连接形成新超边时，在旧节点的选取上，也具有某种倾向性。根据假设条件，我们对Poisson 连续时间增长节点具有寿命的超网络模型的新节点进入、老化与退出的机制描述如下。

2.1 新节点进入和节点老化

（1）泊松增长：网络从少量的节点数量m0开始。在这个过程中，节点以批次的形式分批到达网络，新节点批的到达过程是一个具有强度为λ的Poisson 过程。在时刻t，当一批新节点到达超网络时，从服从分布F(η)的正整数中提取ηN(t)，ηN(t)是一个可变化的值，这ηN(t)个新节点与超网络中已有的m1个旧节点形成一条新超边，新超边包含的节点中有m1个旧节点，ηN(t)个新节点。如果m1=0，新超边中的所有节点都是新节点；如果ηN(t)=0，新超边中的所有节点都是旧节点。每一条新超边中包含的旧节点数m1是变化的，所包含的新节点数ηN(t)也是一个变化的值。

（2）择优连接：为新节点选择连接时，假设新节点连接到旧节点vi的概率∏(dH(vi))取决于旧节点vi的超度dH(vi)和它的年龄τi，即满足：

其中，ti是节点vi进入网络的时刻，τi=t-ti为节点vi的年龄。

上面公式（1）说明，随着节点年龄的增长，其择优性在减弱。随着时间的增加，节点逐渐老化，则被新节点选择的概率会降低。当节点达到一定的年龄（老龄化）时，新进入的节点将不再连接它。

2.2 老节点退出

删除网络中的某个老节点vl的概率为p(dH(vl))。删除老节点依据概率：

选择节点vl，dH(vl)是节点vl的超度；n≥0，称为饱和因子，n 是与节点的年龄(t-ti)有关的，(t-ti)越大，n 越大，节点被删除的可能性越大。

3 超网络中有寿命节点的进入、老化与退出的演化模型

Barabasi 和 Albert［9］对 BA 模型进行了推广，构建了一个更具有一般性的无标度网络，即网络不仅由于添加新节点而产生新边外，网络中的旧节点之间的连接既可能消失也可能会建立新的连接。在很多现实网络中，边可以通过连接新节点的方式增加，也可以在网络中的旧节点之间创建新的连接。例如：在演员合作网络中，节点表示演员，连边表示影片。一部新的影片可以通过一些新演员和已有演员之间的合作来完成，也可以通过已有演员之间的合作来完成。

本文根据第3 部分的超网络中的有寿命节点的进入、老化与退出机制，构建了基于超图的超网络动态变化模型：在变化过程中，不仅有新节点和新超边进入超网络，节点也会老化，也有老节点退出超网络，除了新添加的节点与旧节点可以生成新超边之外，并且超网络中的旧节点之间也可以生成新的超边，旧超边也可能退出超网络。在图2 的六种动态模型中，前三种主要来自文献[8]，后三种是本文在文献[8]的基础上首次提出。初始时假设超网络有m0个节点。m 是新超边含有的节点数，m1是新超边中包含的旧节点数，ηN(t)是新超边中包含的新节点数，m2是被删除的老节点数[9]。图2 模拟了当m=3，m2=1 时，超网络动态演化过程，其中（a）是基础图，（1）-（6）为超网络演化过程示意图。图 2 中的（1）-（6）是分别在基础图形（a）上做演化所得到的。在每个时间步内，下面6 种操作选其一。实际中，超网络的演化过程有很多种形式，下面的6 种操作只是超网络演化过程的部分举例。图2 中，旧节点用黑色实心圆点表示，新进入超网络的节点用黑色空心圆点表示，旧超边用实线圆圈表示，新超边用虚线圆圈表示。

（1）在原有连接的基础上，以概率p 增加一条新超边。从超网络的已有节点中根据概率择优选择m 个旧节点，生成一条新超边，每次选取的旧节点vi的概率根据公式（1），如图 2（1）所示。

（2）在原有连接的基础上，以概率q 增加一条新超边。首先从超网络中随机删除一条旧超边，再从超网络已有节点中根据概率择优选择m 个节点，生成一条新超边，每次选取旧节点vi的概率根据公式（1），如图2（2）所示。

（3）以概率r增加ηN(t)个新节点和一条新超边。这ηN(t)个新节点与超网络中已有的m1个旧节点结合生成一条新超边。当选择旧节点vi与新节点相连时，旧节点vi根据择优概率（1）式选取，如图 2（3）所示。

（4）在原有连边的基础上，以概率s 增加一条新超边。删除超网络中m2个老节点，删除老节点的概率依据公式（2），然后从超网络已有节点中根据概率优先选取m 个节点，生成一条新超边。每次旧节点vi根据择优概率（1）式选取，如图 2（4）所示。

（5）在原有连边的基础上，以概率w 增加一条新超边。首先从超网络中随机删除一条旧超边，同时删除已有超网络中m2个老节点，删除老节点的概率依据公式（2），再从现有超网络节点中根据概率优先选取m 个节点，生成一条新超边。每次旧节点vi根据择优概率（1）式选取，如图 2（5）所示。

（6）以概率1-p-q-r-s-w 增加ηN(t)个新节点和一条新超边，同时删除超网络中m2个老节点，删除老节点的概率依据公式（2）。这ηN(t)个新节点与已有超网络中的m1个旧节点结合生成一条新超边。当选择旧节点vi与新节点相连时，旧节点vi根据择优概率（1）式选取，如图 2（6）所示。

4 实例分析

企业科技创新团队合作申请专利超网络中，节点代表的是企业科技创新团队人员，超边代表的是科技创新团队合作申请专利关系。该超网络中的节点是有寿命的，这里的寿命不是人的自然寿命，而是指人员合作申请专利的寿命。在企业科技创新团队合作申请专利超网络中，可能会有新的人员加入超网络中，长期不更新专业知识的人员会老化，即节点老化抽象为人员不更新专业知识，所导致的人员老化问题，超网络中的已有的人员可能由于某些原因离开超网络，超边所表示的现有的科技创新团队可能解散，也可能现有人员之间形成新的科技创新团队，或者有新的人员加入与已有的人员组成新的科技创新团队。因此，企业科技创新团队合作申请专利的过程可以用图2 描述。如图3 所示是某高新技术企业科技创新团队合作申请专利超网络模型的演化过程图[10]。

企业科技创新团队合作申请专利超网络最开始的初始时间是t=0，该超网络随着时间逐步演化，图3 超网络演化过程分为6 个时间点，从t=1 到t=6。图3 是整体超网络随着时间发展所进行的逐步演化。图3 中每一步的演化都是根据图2 基于超图的超网络演化过程示意图中的6 种操作来完成的。图3 中，每条新超边中的节点数都是3，m2是被删除的老节点数，被删除的老节点数都是1，每条新超边中的新节点数、老节点数是变化的。

图 3 中，t=1 时，以概率 p 在旧节点 v1、v4、v19之间增加一条新超边E8，每次选取的旧节点vi的概率根据公式（1）；t=2 时，首先从超网络中随机删除一条旧超边E4，再从超网络已有节点中根据概率择优选择3 个节点 v8、v9、v10，以概率 q 增加一条新超边 E9，每次选取的旧节点vi的概率根据公式（1）；t=3 时，以概率 r 增加 2 个新节点和1 条新超边。这2 个新节点v15、v16与超网络中已有的1 个旧节点v12结合生成一条新超边E10。当选择旧节点vi与新节点相连时，旧节点vi根据择优概率（1）式选取；t=4 时，删除超网络中 1 个老节点 v4，删除老节点的概率依据公式（2），然后从超网络已有节点中根据概率优先选取 3 个节点 v11、v15、v16，以概率 s 增加一条新超边E11，每次旧节点vi根据择优概率（1）式选取；t=5 时，首先从超网络中随机删除一条旧超边E6，同时删除已有超网络中1 个老节点v13，删除老节点的概率依据公式（2），再从现有超网络节点中根据概率优先选取 3 个节点 v7、v12、v15，以概率 w 增加一条新超边 E12，每次旧节点vi根据择优概率（1）式选取；t=6 时，以概率1-p-q-r-s-w 增加2 个新节点和1 条新超边，同时删除超网络中1 个老节点v5，删除老节点的概率依据公式（2）。这 2 个新节点 v17、v18与已有超网络中的 1 个旧节点v16结合生成一条新超边E13。当选择旧节点vi与新节点相连时，旧节点vi根据择优概率（1）式选取。

图3 企业科技创新团队合作申请专利超网络模型演化过程图

通过图3 可知，t=0 时，该企业科技创新团队合作申请专利超网络中的节点数是15，超边数是7，经过5个步骤，t=6 时，该企业科技创新团队合作申请专利超网络中的节点数是16，超边数是11，超网络图形更加复杂，超网络的密度增加，以及平均距离减小。从t=1到t=6，超网络中节点数和超边数都是变化的，该企业科技创新团队合作申请专利超网络是处于动态变化过程中的，以上体现了该企业科技创新团队合作申请专利的演化过程。通过该演化过程，我们可以知道该超网络中的人员和科技创新团队的数量是动态变化的。因此，企业需要关注科技创新团队人员以及科技创新团队的变化，采取相应的措施来激励人员更多地参与到科技创新团队中，加强对人员的培训，延长团队人员的合作申请专利的寿命，同时在企业科技创新团队的组建过程中，对人员的引进、选择等方面也要进行充分地考量。

5 结语

本文基于现实网络的特点，在超图理论的基础上，提出Poisson 连续时间增长的超网络模型中有寿命节点的进入、老化与退出机制，包含：新节点的加入、节点老化和老节点退出。新的节点进入网络中，还会有新的连边生成，旧节点之间形成的超边可能消失，旧节点之间也可能会产生新超边。本文构建了一种基于超图的超网络动态演化模型，最后以某高新技术企业进行实例分析，进一步验证了前面的假设。近年来，基于现实世界的超网络特性的研究成果比较少，关于超网络的演化还需要进一步开展相应研究。由于数据的缺少，所以实证研究需要进一步加强，超网络演化模型的实证研究是需要继续研究的问题。