最近邻演化网络模型

徐玉章

最近邻演化网络模型

徐玉章

江苏省自然科学基金项目：BK20141071

徐玉章 朱 磊

中国人民解放军理工大学通信工程学院

我们生活在一个充满复杂系统的社会中，其中很多系统的结构都可以用复杂网络来刻画。20世纪末，科学家们建立了两个重要的复杂网络模型。其中一个模型是WS小世界网络模型，该模型融合了规则网络的大聚类特性和随机图网络平均路径长度较小的特性，可以说，WS小世界网络模型是一种介于规则网络和完全随机网络之间的网络模型。但随着复杂网络研究的深入，人们发现越来越多的真实生活中的网络呈现出无标度（节点的度即与节点相连的边的数量）的特点，即网络中节点的度服从幂律分布，在双对数坐标下是一条斜线，而不是单峰曲线，另一种重要的复杂网络模型应运而生。1999年，Barabási和Albert成功地提出了BA无标度网络模型，他们在该模型中解释了复杂网络无标度性质的一种可能形成机制：增长和随机连接。BA无标度网络模型被认为是最著名的复杂网络模型之一。

在以往的复杂网络模型的研究中很少考虑区域和距离的因素。然而，很多真实的网络受限于节点的位置和节点间的距离，例如，现代物流网络和大型集会中的临时通信网络，人际关系网络中也有区域的限制。假设存在若干区域，每块区域中有一个“骨干节点”。每个骨干节点和其邻近的骨干节点相连，新加入的节点选择其附近的节点进行连接。节点代表了通信节点、物流中心等实际场景，边代表了节点之间的联系。在这种情况下，节点和边的连接遵循就近原则，即节点更倾向于与最近的邻居相连。上述情况在我们的生活中几乎时时刻刻都在发生，我们该如何构建与之相符的模型来描述这种情况呢？如何得出模型的关键指标？新模型将具有哪些特性？为此，本文提出了“最近邻演化网络模型”。

1 最近邻演化网络模型的构建

本文在BA无标度网络的构建算法的基础上引入区域和距离的限制，邻近的节点将会位于同一簇中。最近邻演化网络模型的构建算法如下。

（1）初始状态：具有m0个节点的最近邻耦合网络。每个节点和邻近的左右两侧各K/2（K为偶数）个节点相连，称这m0个初始节点为“骨干节点”。

（2）归属节点和节点簇：当一个新节点加入网络后，距该节点最近（距离以边数衡量，最近即最短路径上的边数最少）的骨干节点称为该节点的“归属节点”（如果几个骨干节点与新节点的距离相同且均是最少，则从中随机选取一个作为节点i的归属节点）。具有同一归属节点的节点构成一个“节点簇”。

（3）增长：每次只允许一个节点加入网络。新节点加入时，首先选择2个相邻的节点簇，再从这两个节点簇中选择m（m＞=2）个节点进行连接。（在初始阶段，节点簇中的节点数一般会小于m，所以规定新加入的节点只和其选择的节点簇中2个节点连接）

（4）优先连接：新节点在选择节点进行连接时，采用优先连接的机制，即新节点和节点i相连的概率与节点i的度ki有关，度越大，连接概率越大，按如下公式计算：

其中，Pclusters表示选择的节点簇中包含节点i的概率，

2 最近邻演化网络模型的基本指标

复杂网络研究中刻画网络特性的三个基本指标为：度分布、聚类系数和平均路径长度。度分布指网络中节点度的分布，节点的度（如前述，即与该节点相连的边的数目）可以衡量一个节点的重要程度，充分了解网络的度分布，可以使我们对网络拓扑有一个直观的把握，并进一步帮助人们更深入地了解复杂系统。聚类系数是衡量网络中邻近节点联系紧密程度的指标，网络的聚类特性在某种程度上可以概括为社会关系网络中“物以类聚，人以群分”的特性。平均路径长度可用来衡量网络中节点间距离的大小，如果网络的平均路径长度的增加速度至多与网络规模的对数成正比，就说这个网络具有小世界效应。

度分布

将公式（2）带入公式（1）得到

长时间后，每个节点簇中的节点数将远大于m，所以公式（3）中的约等于号成立。

利用主方程法，得到稳态度分布为：

该公式表明最近邻演化网络模型和BA无标度网络模型具有相同的度分布。实验结果和理论值吻合地较好。双对数坐标系下的斜线表明该网络在具有众多小度数节点的同时，仍在存在少量的大度节点，这也是网络增长过程中择优连接的一个必然产物。

聚类系数

聚类系数指节点i的ki个邻居节点之间实际存在的连边数Ei与这ki节点所有可能的连边数目之比，衡量了网络中邻近节点间的紧密程度，用Ci表示，即

这里“i”既是节点的代号，又是节点加入网络的时间点。利用平均场理论，得到最近邻演化网络的聚类系数（随时间变化）为：

当ti远小于t（即节点i加入网络后又过了较长时间）时，Ci（t）可作如下近似，

平均路径长度

网络中两节点i和j之间的距离dij定义为连接这两个节点的最短路径的边数。网络的平均路径长度L定义为任意两个节点之间的距离的平均值，即

其中N为网络节点个数，因为每一时刻网络中有且只有一个节点加入，所以若不考虑网络的初始规模，该处的N等价于t。

给出了无标度网络平均路径长度的尺度，

如表1所示，通过仿真，本文得到了最近邻演化网络的平均路径长度L，L的增长速度介于公式（9）和lnN之间。随网络规模的增加，平均路径长度的增长十分缓慢，表明该网络具有较明显的“小世界效应”。

表1 最近邻演化网络模型的平均路径长度

3 总结与展望

现实生活中很多网络与区域和距离因素息息相关，而以往的复杂网络模型对区域和距离的因素考虑较少。本文将区域的概念引入无标度网络，建立了最近邻演化网络模型，并深入分析了该模型的度分布、聚类系数和平均路径长度。结果表明，最近邻演化网络模型具有与BA无标度网络相同的度分布，此外，在保持较小的平均路径长度的同时，该模型显示出更好的聚类特性，即邻近节点间的联系更加紧密。下一步，我们将进一步探究该模型的抗毁性。此外，在无标度网络的构建中，人们专注于择优连接以求获得无标度特性，忽略了随机连边对网络特性的影响，在复杂网络模型研究中引入随机连边机制也将具有潜在重要意义。

10.3969/j.issn.1001-8972.2015.02.050