复杂网络在双曲空间的节点动态择优路径研究

杨琳

(武汉大学土木建筑工程学院工程管理系,湖北武汉 430072)

1 引言

复杂网络为日常生活中发生的许多物理过程提供了一个自然的抽象解释,遍及人类生活的方方面面.网络有大量的节点以及连接节点的边所组成,节点表示真实生活中的个体,边表示个体与个体之间的关系.复杂网络中一个最重要的功能就是传输功能,例如,以信息为载体的计算机网络、以人和货物为载体的运输交通网络、新闻或者社区信息传播的社会网络等等都是具有动力学特征的复杂网络.有一种广泛存在于社会各个领域的网络结构,其度分布服从幂律分布p(k)～k−γ(2<γ<3),这种网络有很强的异质性,少量节点占据大量的边,能够展现一个界限清晰的网络特质,这就是具有无标度的复杂网络[1].无标度网络区别于其他网络模型的最独特之处在于,它是一个不断增长和演化的网络模型,这与真实世界的复杂系统不断演化的特征极好的吻合,能够很好地刻画真实网络[2].

近几年来,复杂网络的研究集中在以下几个方面:复杂网络的节点影响力研究[3]、节点传输速率研究[4]、网络拓扑模型研究[5]、网络同步分析[6]以及无标度网络在交通运输网络[7]、计算机网络[8]以及无线传感网络[9]等领域的应用研究等.上述研究都是建立在一个网络节点不变的静态网络下进行的,而真实世界的网络节点之间构成一个动态网络.具有无标度的复杂网络拓扑具有两个典型的特征:节点的度分布服从幂律分布,且该网络有一个高的聚类系数,即在网络拓扑图中可以找到很多三角形[10].许多复杂网络的幂律分布是由实际网络的增长特性和优先连接特性所产生的,大量的网络节点数量不是一个定值,而是随着时间推移呈动态增长趋势[11].因而,在没有复杂网络全局视图只有节点位置信息的情况下,网络节点之间如何搭建清晰的动态连接路径是一个值得深思的问题.

Kleinberg首先对此进行了解释:他认为每一个节点都嵌套在欧几里德平面坐标空间的网格内,且每一个节点的坐标可以抽象为其位置信息,即可以代表该点的位置、相邻节点的位置以及相连接节点的位置,因而可以通过选择最邻近节点来设计贪婪路线[12–14].很显然,Kleinberg描述的贪婪路径规划算仅在网络拓扑与底空间完全重合才能有效实现,因为这种贪婪路径算法难以同样有效的应用在任意一个给定底空间的网络拓扑中.在此基础上,Krioukov提出了一个基于双曲空间的复杂网络模型,这个模型给出了一个服从幂律分布的复杂网络[15–19].Krioukov模型表明:贪婪路径算法实现了100%的可达性和优路径长度.而仅仅依靠位置信息,运用贪婪路径算法,一个节点可以找到其他任何节点,且一个节点选择相邻节点作为下一连接节点是通过计算最近的双曲距离来判断的[20].Krioukov模型的结论尤为重要,但是由于Krioukov模型是静态的,所以很难被用于现实复杂网络中.

本文针对该静态模型的提出及其存在的问题,创新地提出了网络节点动态双曲嵌套模型,通过模型分析和计算,深入分析复杂网络的节点动态连接路径和最优算法.

2 双曲空间的节点连接

在二维空间里,只有三种类型的各向同性坐标空间,即欧几里德坐标空间、球形空间以及双曲空间,每种空间的参数可见下表1.

表1:三种不同类型的各向同性坐标空间的参数比较

假定双曲空间内有N个节点,且圆半径为R,由于圆面积是2π(coshR−1),因此节点N服从指数分布,即N～eR,因而圆半径与网络大小N满足对数关系,即R～lnN.具有常负曲率的双曲空间不能被等距嵌入任何欧式空间,因为它比欧式空间更大.以给定点为中心,通过其Euler坐标值测量其表面曲率,形式上可以被定义为

其中l(R)表示以该点为中心,以R为半径的圆周长.如果l(R)=2πR,则表面是平的;如果l(R)比2πR短,则表面是正曲的;如果l(R)比2πR长,则表面是负曲的.双曲面的曲率不是恒定的,但是无限接近0.连接概率函数是一个极大熵分布[0,R],当双曲距离在x≤R时每对节点连接.因为传统的指数分布存在有界方差,当p(x)多项式快速衰减,当x→∞时,在概率密度演化图中对于极值创造出一个“肥尾”.双变量x和y通过幂次法则相关联,当y(x)=Ax−γ时,正数经常被称作指数,其中A和γ是正的常数.当概率密度函数是P(x)=Ax−γ,γ>1,且x>xmin时,则遵循幂次法则,即P(x)～k−3.复杂网络节点存在于潜在的网络拓扑空间,称其为隐藏度量空间.网络拓扑空间与隐藏度量空间的几何耦合遵循以下的方式:即两个节点之间的拓扑连接以一定的概率存在并依赖于两个节点之间的隐含几何距离.在这个假设前提下,真实的复杂网络中,每一个互相连接的节点均处于具有负曲率的隐藏空间,且仅仅基于位置信息就能计算得到每个节点的隐藏坐标.给定一个网络N,每个节点i首先被分配给一个隐藏变量hi,该变量服从某种概率分布,然后用连接概率p(i,j)连接节点对(i,j).隐藏空间的节点对的连接概率取决于双曲空间的距离大小.因此,该双曲网络空间可以通过节点的度分布、节点的连接概率和双曲曲率大小来描述一个无标度的复杂网络.根据双曲空间中定义的距离度量,如果这些网络中的节点距离越接近,则被连接入网络的可能性就越大.因此,首先要进行双曲空间的选择,然后确定节点的分布函数,最后选择连接概率,即选择节点之间双曲线距离函数.本模型中,选择[0,R]阶梯函数作为连接概率函数,给出目标节点数N和平均度,根据N=keR/2(k是一个参数用来优化),确定双曲线圆盘的半径为R,并赋予每个节点分配一个角坐标θ,均匀的分布在[0,2π)之间,用如下概率函数给每个节点分配一个径向坐标

假设任何时候相连的两个节点之间的双曲距离小于R,并定义两个节点的极坐标分别为(γ,θ)和(γ0,θ0),那么这两个节点之间的双曲距离x被定义为

其中∆θ=min(|θ−θ0|,2π−|θ−θ0|).利用这个模型,生成的复杂网络服从幂律度分布,通过P(k)～k−γ得出

一般来说,负曲率的双曲空间比一般的欧式空间增长速度更快,如果欧式空间呈线性增长的话,双曲空间会呈指数增长.这种关系表明,在切线方向的欧式距离对应着呈指数增长的双曲距离,因此复杂网络可以进行双曲空间的嵌套,网络节点通过双曲空间可以找到优化的动态路径.

3 复杂网络节点在双曲空间的动态择优过程

具有无标度的复杂网络在双曲空间建立节点路径,保证了复杂网络的拓扑结构与隐藏的双曲空间的一致性.但是真实的复杂网络往往是动态变化的,网络内的节点数量有可能随着时间的变化增加,因此需要一个随着双曲空间的增长而不断扩大的无标度网络模型.当网络内有新的节点进入的时候,应该增加网络的双曲半径,即令R=2ln(N/k).为了进一步表达动态过程,需要在新加入每一个节点之前就知道已存在的节点数量,需要一个全面覆盖的复杂网络.假设节点映射到一个半径为R的双曲圆盘上,R=2ln(Nmax/k),这里Nmax是网络中节点数量的最大值.此外,节点被放在距离圆盘中心的某些固定的位置上,见图1.

为了解释这一点,把双曲圆盘分割为环形NL(或者层),并且这些环形有外径Ri和内径Ri-1,在这里i∈{1,2,···,NL},并将其定义为

放置在每层i上的节点数量Ni是在圆盘区间上所期望得到的节点数,Ni是由分布函数ρ(γ)确定的,如下所示,

图1:半径为R的双曲平面及分层示意图

在该模型中,每一层i的节点Ni都沿着环形圆周放置在环形i的中间,节点Ni的半径为.因此在双曲平面极坐标中任一个节点p在平面i中的坐标p(γi,θi)为

节点p的坐标p(γi,θi)被表示为pi,k.根据公式(7)和(8)得到,一个节点的径向坐标γ和角坐标θ可以假设为离散的值,代表离散的位置信息,因此该模型可以被认为是离散化的模型.一旦一个新的节点进入双曲空间,它就连接到双曲距离小于的节点,也就是说所有节点都在红色阴影形状图1内.

4 网络节点双曲嵌套模型计算与分析

为了研究动态双曲空间节点动态择优网络的拓扑特征,首先计算位于环的节点的平均度k(i).为了简单起见,考虑一个节点pik放在水平i,角坐标定为(也就是k=0)在图1中蓝色阴影区域包含所有的点,从点pik到这些点的双向距离小于或等于R.节点pik的平均度由下式给出

式中,Nj是放在环j的节点的数量,fj是Nj的分数,从点pik到这些点的双向距离小于或等于R(也就是说所有这些节点都在蓝色阴影形状图1内),fj的一个简单公式可以这样给出,等于蓝色阴影区域内的圆形角的分数,如下公式

对于j和i+j≤NL+1,φi,j等于2π(也就是所有在水平j的点到点Pi,k的双向距离小于R).在其他情况下,它是由以下公式给出

因此

将公式(6)和(10)代入公式(9)中,得到

证明了对于每一个i,j,φi,j等于2π,如i+j≤NL+1,改写公式(13),

公式(14)中的第一个求和是一个有限的幂级数,如下

公式(15)显示了一个指数递减的趋势,意味着公式(12)中这一项的作用随着j接近NL值而递减,对应于最后的周长.这种现象很容易解释,是由于项相关于完全包含的环,而且随着目标点向NL水平移动,它的作用趋向于0.

复杂网络的度分布Pk是有着度k复杂网络的点的分数.为了获得动态双曲空间嵌套模型中的度分布Pk,需要得到每一个环i的两个值:1)环i的节点分布;2)环i的度.前者由比率Ni/Nmax得到,而后者由

计算得到.模型中忽略了对于Pk的分析描述,但是它遵循一个幂律,显示在无标度网络中,分析结果和实际情况吻合.

5 网络节点动态连接路径仿真

从上述分析过程可以得出,复杂网络中每个单点的位置在动态变化的过程中维持了度分布与模型的一致.在复杂网络动态双曲嵌套模型中,每个点的位置直接与它的度相关,在动态变化的过程中,节点的度分布与模型始终保持一致.只要这种情况能够得到保证,则随着时间的变化,即使无标度网络节点不断增多,该双曲嵌套模型仍然有效.在模型构建及分析过程中,任意选择一个节点,根据均匀分布函数,设角φ∈[0,2π],该角能够定义一个理想的点P=(R,φ),这个点位于自由的位置,有着最大的半径和随机角度,且距离P有着最小的距离.然后选择无标度网络的节点,该节点通过任意选择得到且不需要靠近理想点,但选择的节点要有足够的动力接近实际到达的理想点;此时,最接近的节点有着关于整个网络节点的总信息,这些节点的双曲距离小于R,能够有效的为新来的节点分配正确的位置;当新增加的节点得到的分配位置时,则该节点的位置信息被占据且能够与邻近节点形成新的无标度网络,形成了具有双曲平面特征的嵌套网络.为了保证新增加的网络节点在无标度双曲嵌套模型中是最新的,允许每一个点有着邻近点的全部信息(也就是点和自由位置存在于距离它的双向距离R内)是共享的.该网络中的每一个点与它邻近节点的当地信息保持最新.假设一个网络大小N=104,平均度分布=6.5,鉴于节点N和平均度分布,模拟仿真如下:首先,依据N=keR/2,修正半径为R的双曲平面,其中参数k用来调整平均度分布到目标度分布,其中N～∞;然后,给每个节点分配一个坐标r∈[0,R],且概率ρ(r)=αeαr(eαR−1)−1,α ∈[1/2,1];连接每两点之间的双曲距离小于R的节点对,其中双曲距离x通过坐标变换 (r,θ) 和r0,θ0,可得

图2:复杂网络双曲嵌套模型及节点连接路径仿真示意图

从图中可以看到网络的度分布、关联性及聚类状态等,该网络有很强的聚类系数,形成了大量的三角形.实际上,如果平面内的节点a与节点b紧邻,且节点b又同时与节点c紧邻,则依据三角形公理,节点a同样与节点c紧邻.因此整个网络的每三个节点组abc都与其他节点组相邻.为了验证该网络结构是否具有无标度特征,分别设定γ=2.1和γ=2.9,计算P(k)、和(k),如下图3所示.

通过比较在两种不同的幂次分布下无标度网络双曲嵌套模型的拓扑指标可以看出:由于网络服从幂律分布p(k)～k−γ(2<γ<3),网络中影响度分布的幂次γ越低,相连节点的聚类程度越高,网络的节点三角形越密集.对于γ=3这样一个极限值,该网络会对应一个平均路径长度的异常值α=1.0,每两个节点的连接只需要两次跳跃即可实现.即在真实网络世界里,不论该网络的大小,只要满足双曲嵌套模型的结构,则每一个节点都会连接到一个中心.

图3:不同幂次分布下网络拓扑指标变化图

6 结论

真实世界的网络往往具有很强的异质性,能够展现一个界限清晰的网络特质,且网络是随着时间的变化,其节点容量不断发生变化.本文鉴于复杂网络幂律分布是由实际网络的增长特性和优先连接特性所产生,大量网络节点数量随着时间推移呈动态增长趋势的动态演化特质,从复杂网络入手研究真实网络节点动态连接规律进而揭示网络动态演化机理具有重要意义和实用价值.

本文通过回顾克林伯格的欧氏空间网络拓扑模型及贪婪路径算法,以及克莱尔科夫提出的静态双曲网络模型,发现依靠节点的位置信息就可以找到其他节点这一重要结论,同时认为静态模型仅能作为网络物理特征的研究方法,难以应用到真实的复杂网络中,因此本文提出了基于双曲空间的节点动态择优路径研究.

本文首先比较了欧式空间、球面空间和双曲空间这三种各向同性空间的物理参数,认为隐藏空间中两两节点对的连接概率由双曲空间的距离确定,故而双曲空间可以通过网络节点的度分布、节点的连接概率和双曲曲率的大小描述无标度网络.根据双曲空间的距离度量,网络节点距离越接近,则被连接入网络的可能性就越大;并通过分析得到在切线方向的欧式距离对应着呈指数增长的双曲距离,因此具有无标度的复杂网络可以进行双曲空间的嵌套.然后,构建了双曲嵌套模型,通过分析模型中嵌套环的分布规律和嵌套区间内节点的度分布,验证模型符合无标度网络的幂律分布特征.最后,通过一个给定的真实网络,设定网络相关参数,对其进行网络节点动态连接仿真,仿真结果表明:网络中每个单点的位置在动态变化的过程中维持了度分布与模型的一致;在网络动态双曲嵌套模型中,每个点的位置直接与它度相关,在动态变化的过程中,节点的度分布与模型始终保持一致.

综上所述,本文建立了复杂网络双曲嵌套模型,通过改变原有静态模型依赖于连续双曲空间的现状,设计网络节点在双曲空间的优化路径,通过分析离散节点在双曲空间动态择优过程,建立复杂网络节点间最优路径算法,对真实世界复杂网络的动态演化机理提供了理论借鉴.下一步,针对节点之间的连接紧密性和动态连接速率,建立真实世界的网络容量有序增长模型,将是关注的重点.