确定性层次网络建模方法及特性分析

李 锴， 吴 纬， 刘福胜

(1.陆军装甲兵学院装备保障与再制造系， 北京 100072； 2. 北京特种车辆研究所， 北京 100072)

近年来，利用复杂网络理论研究现实世界中的复杂巨系统是研究热点之一[1-3]，如武器装备体系网络[4]、生物网络[5]和邮件网络[6]等。构建符合复杂巨系统的网络模型是问题研究的关键，现阶段的主要网络模型有ER随机网络模型[7]、WS小世界网络模型[8]和BA无标度网络模型[9]等。小世界效应和无标度特性为许多实际复杂网络共同的全局拓扑特性，但全局拓扑特性相似的复杂网络往往具备不同的局部拓扑特性，因此分析研究网络局部拓扑特性也十分重要。模块(module)是指由少部分网络节点按照一定拓扑结构组成、并在网络中复制出现的节点组合[10]。从本质上来讲，模块是在网络中大量重复出现的、具有特定拓扑结构的小规模子图(如食物链网[11]和交通网[12]等均发现模块的存在)，这些子图从局部层面上描述了网络内部结构的连接方式。因此，虽然网络模块往往具备不同的局部拓扑结构，但网络模型在整体层面上表现出一致的层次模块性(hierarchical modularity)。

构建确定性层次网络(Deterministic Hierarchical Network,DHN)模型的方法有多种[13]，而层次网络模型大都是针对特定应用背景而提出的，如：RAVASZ等[10]对复杂网络中的层次模块性进行了分析，说明无标度特性和层次模块性是许多实际复杂网络的基本特性；WANG等[14]构建了具备“局部偏好连接”特性的层次网络模型，并分析了其无标度特性和层次模块性，证明该模型具备合理性；袁铭[15]对层次网络中的级联效应进行了分析，在不完全信息和负载重分配的模式下，对复杂网络的可靠性进行了研究，并对层次网络的可靠性优化提出了合理建议；DONG等[16]建立了树状加权层次网络模型，并对社交网络进行进一步分析，计算结果说明社交网络具备小世界效应和无标度特性。

武器装备体系网络中，网络节点代表装备实体，网络链路表示装备实体间物质流、能量流和信息流的交换，以及装备实体彼此之间指挥控制和协同保障等多种复杂关系[4]。在体系对抗过程中，武器装备体系需要持续的信息获取和快捷的信息传输，同时指挥控制系统作为体系网络中的“神经中枢”负责一系列作战任务，该类节点作为“偏好连接”的目标节点成为体系网络中的Hub节点，这说明武器装备体系网络具备小世界效应和无标度特性。分析武器装备体系网络层次模块性，可以将体系网络自上而下分为体系层、系统层、平台层和单元层，从而可以准确表示体系网络中不同层次结构的交互关系。由低层次向高层次逐步聚合时，往往会发生宏观特性的变化。

为进一步分析武器装备体系网络的拓扑特性，构建满足体系网络特性的理论模型，CHEN等[17]提出了网络模块尺寸为2的树状DHN模型的构建方法，但该方法对应的层次网络模型缺乏普遍性，不能对一般情形下的层次网络模型进行研究。基于此，笔者构建以任意正整数m(m>1)为网络模块尺寸的DHN模型，并对该模型的小世界效应、无标度特性和层次模块性进行理论分析和数值仿真证明。

1 DHN模型的构建及拓扑特征

1.1 DHN模型的构建

对于实际复杂网络，“增长”(growth)和“偏好连接”(preferential attachment)是2个非常重要的特性。当网络中出现“马太效应”时，其度分布函数会表现出明显的幂律特征[18]，层次网络模型主要通过网络模块复制并迭代的方式构成，利用网络模块结构识别网络局部连接模式，可以对复杂网络模型进行简化，容易对网络的全局拓扑特性及动态演化性作进一步分析。综合以上分析，本文DHN(n,m)模型构建方法如下：

1) 初始时刻。规定网络层数n=0，网络中仅存在一个孤立节点，定义为DHN模型的根节点。

2) 网络增长。逐层增加网络节点，第n(n>0)层中的网络节点数目为mn，其中m为网络模块尺寸，满足m>1。

3) 偏好连接。第n(n>0)层中所有节点的度值为n，分别连接每个节点对应的第0至n-1层中的n个父节点。

在DHN(n,m)模型中，网络模块通过复制并迭代的方式彼此相互连接，“偏好连接”的目标节点为自身对应的父节点，网络模型中每次迭代的新增链路数目与新增节点的层级数相关，并不是固定的常数。

图1为n=4，m=3时的DHN(n,m)模型拓扑结构图。图中：节点的颜色共有5种，表示网络的层为n+1=5层；DHN(n,m)模型中的根节点作为整个网络的连接中心点，除根节点后的剩余子网络可近似分为3部分，表明每个网络模块中父节点包含的子节点数为3。

1.2 DHN模型的拓扑特征

假定DHN(n,m)模型的层数为n+1，网络模型中第n层的节点数mn，各层节点数目满足等比数列，则DHN(n,m)模型中的节点总数

(1)

网络中的链路总数E满足

(2)

化简后可得

(3)

网络模型中节点的平均度值

(4)

对于DHN(n,m)模型中第i(0≤i≤n)层中的第j(1≤j≤mi)个节点vi-j，其度值ki-j满足

ki-j=kout+kin，

(5)

式中：kout为节点vi-j作为子节点时连接父节点的数目，kin为节点vi-j作为父节点时连接子节点的数目，即

(6)

联立式(5)、(6)可得

(7)

在DHN(n,m)模型中，对于i=0层的根节点和i=n层的叶节点，ki-j分别取

(8)

kmin=n。

(9)

2 小世界效应分析

WATTS等[8]在规则网络的基础上，通过“随机重连”链路方式得到WS小世界网络模型，他们发现：尽管复杂网络本身包含较大的网络节点总数，但网络中任意2个节点之间的路径长度相对较小。小世界效应主要包含较小的平均路径长度L和较大的平均聚类系数C两个特征，本节分别对这2个特征进行分析。

1) 平均路径长度L

在DHN(n,m)模型中，节点vi-j与模型中剩余节点的路径长度之和

(10)

其中：第1项表示vi-j的邻居节点与vi-j直接连接，路径长度为1；第2项表示对于非邻居的其他任意节点，都通过根节点与vi-j连接，路径长度为2。

将式(10)化简可得

(11)

对整个DHN(n,m)模型进行分析，则平均路径长度

(12)

当网络层数n→+∞时，平均路径长度L≈2，说明网络中的大部分节点均通过根节点进行相互连接。

图2为3种网络模型中L与N的关系曲线。可以看出：WS网络和BA网络模型的路径长度L随节点总数N增加而逐渐增大，DHN(n,m)模型则满足L→2。DHN(n,m)模型具备较小的平均路径长度，说明在网络连通性和网络效率方面比WS网络和BA网络模型更好。

2) 平均聚类系数C

1) 节点vi-j的父节点之间直接相连：

2) 节点vi-j的父节点与子节点直接相连：

3) 节点vi-j的子节点彼此相连：

其中E3中不包括第i层节点与第i+1层节点之间的链路。

节点vi-j的聚类系数

2mi(1-m)(1-mn-i)+2[(m-1)(n-1)-

m]mn-i+1+2m2}/[ki-j(ki-j-1)(m-1)2],

(13)

DHN(n,m)模型的聚类系数为所有节点聚类系数的平均值，即

(14)

图3为3种网络模型中C与N的关系曲线。可以看出：与WS网络和BA网络模型相比，DHN(n,m)模型中的C明显较大；BA网络模型中的C随N增大而减小，WS网络和DHN(n,m)模型中的C与N则不具备相关性；当N→104时，DHN(n,m)模型的聚类系数满足C≈1，说明DHN(n,m)模型中节点与其邻居节点构成紧密的团簇形式，三角拓扑结构在网络中的比重较大，整个网络模型具备严密的组织结构。

综合分析DHN(n,m)模型的平均路径长度和平均聚类系数的理论计算与数值仿真结果，充分说明DHN(n,m)模型具备小世界效应。

3 无标度特性分析

无标度特性是许多实际复杂网络具备的共同特性，主要是指网络中大部分节点的链路数很少，存在少量的Hub节点但拥有大量的链路，度分布表现为幂律分布的形式，即p(k)～k-γ。BARABASI等[9]证明BA网络模型度分布满足p(k)=2m2k-3，符合幂律分布规律。

对于DHN(n,m)模型，节点vi-j的度ki-j与节点的位置i有关，任意选取一个节点，则该节点位于第i层的概率

(15)

DHN(n,m)模型的度分布函数p(k)应满足以下2个条件：

联立式(1)、(15)，可得

(16)

需要构建p(k)，使得p(k)=p(i)成立，则由条件2)可得

(17)

联立式(16)、(17)得到

(18)

对式(18)进行归一性分析，则有

(19)

由式(19)可知：p(k)满足归一性。

对于DHN(n,m)模型，度分布函数

(20)

说明DHN(n,m)模型满足无标度特性。

图4为DHN(n,m)模型和BA模型的p(k)计算结果。可以看出：在双对数坐标系下，当k>30时，DHN(n,m)模型的p(k)曲线近似为一条斜率为负值的直线，但BA网络模型对应直线斜率的绝对值更大。这是因为：BA网络模型的度分布满足p(k)～k-3，而DHN(n,m)模型的度分布为p(k)∝k-1，2种网络模型的度分布指数存在差异性。

图5为不同参数下DHN(n,m)模型的p(k)计算结果。可以看出：在双对数坐标系下，当DHN(n,m)模型的网络参数n和m不同时，对应的p(k)曲线几乎完全重合，且当n→+∞时，p(k)曲线可近似为一条斜率等于-1的直线。这说明网络参数n和m与网络模型的无标度特性不具备相关性，而是网络模型自身的拓扑特性。

4 层次模块性分析

RAVASZ等[10]通过分析发现：复杂网络中层次模块性的重要特征是聚-度关联性(clustering-degree correlations)满足幂律分布。通常用C(k)表示度值为k的所有节点的平均聚类系数，C(k)与k满足C(k)～k-α，其中α为分布指数。在理论网络模型中，ER随机网络和WS小世界网络的度分布函数p(k)满足泊松分布，整个网络表现为均匀网络的形式，C(k)与度值k无相关性；BA无标度网络度分布函数p(k)满足幂律分布，但C(k)→0，不满足C(k)～k-α[10]。

对于DHN(n,m)模型，联立式(7)、(13)可得

(21)

当n→+∞时，则有

(22)

此时，式(21)中第2项近似等于0，得到

(23)

由式(23)可知：对于任意节点vi-j，其度值ki-j与其系数Ci-j满足幂律分布。因此，可得C(k)∝k-1,说明DHN(n,m)模型具备层次模块性。

图6为DHN(n,m)模型中聚-度曲线。可以看出：

1)对于不同网络参数n和m，C(k)曲线基本都表现为斜率近似等于-1的直线，说明DHN(n,m)模型具备层次模块性，网络参数n和m与C(k)不具备相关性；2)C(k)，说明节点聚类系数C(k)随节点度值k的增大而减小，度值很小的节点具备较大的聚类系数并属于不同的网络模块，而Hub节点的聚类系数较小，仅发挥连接网络模块的作用。在DHN(n,m)模型中，网络模块内部连接紧密，而模块彼此之间松散关联，从而通过复制迭代构成更大的网络拓扑结构。

5 结论

笔者基于“增长”和“偏好连接”的复杂网络特性，通过网络模块复制并逐步迭代的方式，提出符合一般情形下的DHN(n,m)模型构建方法，并通过理论分析和数值仿真证明该网络模型满足小世界效应、无标度特性和层次模块性。结果说明：DHN(n,m)模型的网络连通性优于WS小世界模型和BA无标度模型；度分布函数p(k)和聚-度C(k)曲线在双对数坐标系下集中体现为斜率等于-1的直线，说明DHN(n,m)模型的无标度特性和层次模块性与网络参数不具备相关性。

对于网络理论模型本身，DHN(n,m)模型中的“偏好连接”针对全局网络中的父节点，下一步可分析局部“偏好连接”增长方式对网络拓扑特性的影响，同时引入“随机重连”和“随机增边”方法，构建更加复杂的层次网络模型。