加权网络上随机行走的平均首到达时间与平均吸收时间

景兴利，赵彩红，凌 翔

(1.济源职业技术学院，河南 济源 454650；2.合肥工业大学汽车与交通工程学院，合肥 230009)

0 引言

1 加权网络上的随机行走

接下来对加权网络上的随机行走进行分析。在加权网络上，每个时间步，一个随机行走粒子从当前位置以概率pij=wij/si进行带偏随机行走，即：每个时间步随机行走粒子从节点i向节点j以概率pij进行传输选择。令P表示网络G上随机行走的传输概率矩阵，则

P=S-1W

(1)

显然地，当G为规则网络时P为对称矩阵，否则P为非对称矩阵。令：

(2)

令λ1,λ2,…,λN表示矩阵Γ在G上相应的N个特征向量，重新整理为1=λ1>λ2≥…≥λN≥-1，其相应的标准化、正交特征向量表示为ψ1,ψ2,…,ψN，其中ψi=(ψi1,ψi2,…,ψiN)表示Ψ的第i列向量。则

ΨTΨ=ΨΨT=E

(3)

令E表示N阶单位矩阵。根据实对称矩阵的性质有：

ΨTΓΨ=diag[λ1,λ2,…,λN]

(4)

Γ=Ψdiag[λ1,λ2,…,λN]ΨT

(5)

通过上边的分析，可以将矩阵P进一步表示为

(6)

以上对加权网络上随机行走模型及特性进行了分析，得到了传输概率矩阵P关于Ψ和S的关系式，接下来利用这些性质对加权网络上随机行走效率进行分析。

2 加权网络上的平均首到达时间与平均吸收时间

本节通过图谱理论方法计算含有N个节点的加权网络G上的任意两节点间的MFPT。为了方便起见，将G的N个节点标注为1,2,…,N。不失一般性地，令TiN表示从任一节点i到任一节点N的MFPT。在给出TiN后我们将进一步分析特殊节点的平均吸收时间(Average Trapping Time,ATT)。令TN表示节点N的ATT，即假定在网络G上有一特殊吸收节点N，TN为网络G上所有节点i到达节点N的MFPT的平均值。ATT在复杂网络上随机行走研究中具有非常重要的意义。

加权网络G上的随机行走是马尔科夫过程[22]，从节点i到节点N的MFPT(TiN)可以被精确通过基础矩阵Z中的一系列元素ziN描述，矩阵Z被定义为

Z=(E-P+R)-1

(7)

其中,R为πΤ的行向量。则由文献[23]知：

(8)

其中,πN是静态矩阵为π=(π1，π2，…，πN)的一个列向量，其每个元素通过如下方式求得：令Pt表示P的t次幂，那么，一个随机行走粒子从节点i出发经过t个时间步到达节点N的概率为表示为(pt)iN，(pt)iN为Pt它的第i行第N列元素。由式(6)可得：

(9)

(10)

当t→∞时，可得：

(11)

因此，加权网络上随机行走的静态矩阵可进一步表示为

(12)

进而，由文献[22]的关于静态概率矩阵的定义得

(13)

为求TiN，需要先给出Z的表达式。而Z中的R与P对应的式(6)与(13)均为关于Ψ与S的表达式。因此我们也将E也表示为关于Ψ和S的关系式，则由式(3)知

(14)

那么，将(6)(13)和(14)带入式(7)得

(15)

其中，ziN可进一步表示为

(16)

另外，Γ的一个特征值为λ1=1，假设对应的特征向量为ψ1。从式(2)(13)及P1=1,可得

(17)

那么通过上边的分析，TiN可表示为

(18)

式(18)的形式和文献[17]相同，但从另外一个角度给出了加权网络上MFPT解析公式，且当w0=1时，含义与文献[17]相同，但本文的结果更具广泛性。从式(18)知MFPT(TiN)的大小与目的地节点权重及边权系数等有关。结合度不相关加权网络的点权和总点权的数学表达式，进一步对式(18)进行处理得：

(19)

从式(19)可看出，在度不相关加权网络上影响MFPT的网络结构的重要因素有网络大小，网络边权控制系数θ。而网络边权控制系数w0对网络TiN的大小没有影响。

ATT在认识网络上随机行走特性中也具有非常重要的意义。在文献[17]，[24]中已有呈现。根据ATT的定义，TN的表达式可表示为

(20)

考虑式(3)、(4)，式(20)可一步表示为

(21)

利用柯西不等式，可得TN的下界为

(22)

通过式(22)知，ATT的下界与吸收点权重及网络总点权有关。进一步分析，与网络大小N及其平均度、吸收点度大小dN、网络边权控制系数θ有关，而与网络边权控制系数w0无关，这与任意两个节点间的MFPT的性质相同。

(23)

则将(23)代入(22)得

(24)

通过以上对〈dθ+1〉的分析知，在度不相关网络上的随机行走的节点的TN与度分布指数有密切关系。特别地，文献[17]给出了网络吸收节点度为dmax时TN的分析结果。

3 仿真分析

为了进一步认识度不相关加权网络上随机行走的特性，通过计算机仿真作进一步探索。不失一般性地，对第1节提出的网络模型，利用BA无标度网络模型建立加权网络模型[25]，其度分布服从P(d)～d-3。首先，建立一个N=1 000，平均度〈d〉≈10的BA无权网络；然后，根据第1节提出的方法即可产生一个度不相关加权网络G。通过分析知，当θ=0,w0=1时，G退化为BA无权网络；当w0=0时，G上所有边的权重均为0，无意义。

下边对G上随机行走进行计算机仿真。分析不同θ值下，网络G上随机行走ATT的特性，我们对其仿真，仿真结果见图1，图1为在双对数坐标系下表示的仿真及式(22)表示的TN的下界的结果。从图1可以看出，ATT的大小与吸收节点的度大小有密切关系，当θ>-1时，吸收点的度越大ATT越小，吸收点的度越小ATT越大，呈反比关系，随着θ值的增大，不同大小度的节点的随机行走效率差异扩大；当θ<-1时，吸收点的度的大小与相应的ATT呈正比关系，随着θ值的减小，不同大小度的节点的随机行走效率差异扩大；当θ=-1时，所有节点的ATT大小相同。呈现这种仿真结果是由于ATT的大小与网络结构有着密切关系，θ取值改变了网络中的节点的连通性，当网络的连通性较好时，到达吸收节点的概率就大，所用的时间就少，反之时间就多。显然地，当θ值不变时，w0的取值大小，对于所有边权的改变是线性、同比例改变大，相对来说没有改变网络节点之间的连通性，因此，网络上节点的ATT无变化。由图1可以看出，仿真结果与式(22)的解析结果的分析一致。

N=1 000，〈d〉≈10，w0=1，S和A分别对应解析和仿真情况。图1 在双对数坐标系上表示的网络G上取不同的权重系数θ时，ATT与吸收节点度d的关系图

根据式(22)知，ATT大小与网络大小N有密切关系。为使结果更加直观，在θ=0.5,w0=1的情况下，我们在仿真时对网络G大小进行调节。网络G大小分别取为N=500,1 000,2 000，〈d〉≈10。仿真结果见图2。由图2知，在节点度大小相等的情况下，相应节点的ATT随着网络规模的增大而增大。

网络的连通性对网络上随机行走的效率有着很大影响。图3取不同网络平均度〈d〉的相同网络规模上的随机行走就行了仿真，其中N=1 000，θ=0.3,w0=1，〈d〉分别取6,10,14。从仿真图可以看出，在网络节点总数相同时，网络平均度越大，相同的节点度的ATT越小。这是由于在网络节点总数相同时，网络平均度〈d〉越大，网络上节点之间的连通性越好，这样在随机行走时到达某个节点的概率就会随之增大。因此，在网络节点总数相同时，网络平均度越大，则其节点的ATT普遍较网络平均度小的相同度的节点的ATT小，随机行走效率越高。

〈d〉≈10，θ=0.5,w0=1图2 在双对数坐标系表示的不同网络节点数(N)的网络G上，ATT与吸收节点度d的关系仿真图

N=1 000，θ=0.3,w0=1图3 在双对数坐标系表示的不同大小的网络平均度〈d〉的网络G上，ATT与吸收节点度d的关系仿真图

4 结论

本文运用图谱理论的方法研究了度不相关加权网络上的随机行走过程。与文献[11]关注的加权网络上随机行走的MFRT指标不同，本文对MFPT、ATT两个重要刻画指标进行了分析。通过分析，我们发现网络的权重系数θ、吸收点度的大小、网络大小和网络平均度指标值的大小有关，而权重系数w0与两个指标值的大小无关。这主要是因为θ值的大小改变了网络节点的连通性，而w0没有。对上述分析结果本文进行了计算机仿真验证，解析结果与仿真结果一致。本文的研究对进一步了解加权网络上的随机行走行为和相关网络动力学有意义。