基于边迭代的复杂网络平均路径长度分析研究①
2020-05-18施艳昭
施艳昭
(安徽电子信息职业技术学院 经济管理系，安徽 蚌埠233000)
0 引 言
复杂网络的核心问题是研究其动态行为如何受到基础拓扑特征的影响，而复杂网络的最重要属性之一是平均路径长度，它描述了所有顶点对之间最短路径的平均长度。平均路径长度在许多与现实生活网络有关的领域中都是相关的，例如疾病的传播或建筑设计中的路线[1-2]。但是，计算庞大复杂网络的平均路径长度仍然是一项艰巨的任务，推导出平均路径长度的解析式仍然具有挑战性。研究首先阐述了两种基于边迭代复杂网络模型的构建机理，然后着重分析最短路径长度并获得相应的分析结论。
1 边迭代复杂网络的构建
为了方便起见，后文将Farey图(Farey Graph，FG)表示为F(t)，其中t是指FG递归生成的步骤。FG的定义如下所示：假设有顶点集V(t)和边集E(t)，Farey图F(t)=(V(t),E(t))，t≥0的构造步骤如下所示[3]：对于t=0，F(0)有两个初始顶点和一条边。对于t>0，通过在步骤t-1引入的每个边上添加一个与该边的端点相邻的新顶点，便能从F(t-1)中得到F(t)。图1显示了从t=0到t=1的生成步骤：两个初始顶点是FG的中心节点，FG是通过将新顶点添加到活动边来构造的，然后将新顶点连接到活动边的两个末端顶点。
图1 FG构造过程
如果改变FG的构建机制，可以推导出Edge Iterations Network(EIN)网络[4]。用Ni(t)表示EIN网络，其构造方式如下：对于t=0，N(0)是一个三角形，三个节点相互连接。对于t>0，通过在步骤t-1中创建的图中的每个边添加一个新顶点并将其连接到边的两个节点上[5]。图2显示了从t=0到t=2的生成步骤。EIN从三角形的三个边开始构建，而FG从单个边开始进行构建。因此，FG等价于EIN的三分之一。EIN从三角形的三个边缘开始，而FG从单个边缘生成。 因此，FG是等效EIN的三分之一。如图3所示，通过合并三个FG(F1(t)、F2(t)以及F3(t))，便能得到一个EIN。
2 平均路径长度分析
2.1 FG平均路径长度分析
在步骤t中，新添加到FG图的边的数量为ΔnFG,t=2t-1，此时FG顶点数量为
nFG,t=2t+1
(1)
图2 EIN构造过程
图3 由FG合并得到EIN过程
(2)
接下来，有
(3)
以及
(4)
(5)
(6)
对于以下的迭代式
(7)
将初始条件D0=2代入上式，得到
DFG,t+1=
(8)
因此，FG的平均路径长度为
dFG,t=
(9)
图4显示了平均路径长度与网络顶点数量的关系。
图4 FG平均路径长度与网络顶点数量的关系
2.2 EIN平均路径长度分析
EIN中顶点的数量可以表示为
nEIN,t=3×2t+3
(10)
如图5所示，通过将G(t)中的顶点Xt和G(k)中的顶点Yk合并成为顶点Z，能得到网络Gtk。
(11)
图5 顶点合并
(12)
(13)
因此，网络Gtk的总最短路径如下所示：
(14)
基于上面的边和顶点聚合的两种模式，并假设在EIN中最短路径的总和为DEIN,t，因此有：
(15)
DEIN,t==DFG,t+1+DFG,t+2+(nFG,t+1-2)×
(16)
将初始值DEIN,0=6带入(16)，能得到
DEIN,t=3×[(2t+1)×22t+2t]
(17)
因此，EIN的平均路径长度为：
(18)
图6 边合并
图7显示了平均路径长度与网络顶点数量的关系。
图7 EIN平均路径长度与网络顶点数量的关系
3 结 论
基于边迭代的网络具有相似但不完全相同的构建机制，因此不同的边迭代网络具有不同的拓扑特性。以FG和EIN网络为研究对象，分析和对比了基于边迭代网络的平均路径长度。由研究结果可知， FG和EIN的平均路径长度会随着网络顶点数量呈现对数式的增长。
