景興利，趙彩紅，凌 翔

(1.濟(jì)源職業(yè)技術(shù)學(xué)院，河南 濟(jì)源 454650；2.合肥工業(yè)大學(xué)汽車與交通工程學(xué)院，合肥 230009)

0 引言

1 加權(quán)網(wǎng)絡(luò)上的隨機(jī)行走

接下來(lái)對(duì)加權(quán)網(wǎng)絡(luò)上的隨機(jī)行走進(jìn)行分析。在加權(quán)網(wǎng)絡(luò)上，每個(gè)時(shí)間步，一個(gè)隨機(jī)行走粒子從當(dāng)前位置以概率pij=wij/si進(jìn)行帶偏隨機(jī)行走，即：每個(gè)時(shí)間步隨機(jī)行走粒子從節(jié)點(diǎn)i向節(jié)點(diǎn)j以概率pij進(jìn)行傳輸選擇。令P表示網(wǎng)絡(luò)G上隨機(jī)行走的傳輸概率矩陣，則

P=S-1W

(1)

顯然地，當(dāng)G為規(guī)則網(wǎng)絡(luò)時(shí)P為對(duì)稱矩陣，否則P為非對(duì)稱矩陣。令：

(2)

令λ1,λ2,…,λN表示矩陣Γ在G上相應(yīng)的N個(gè)特征向量，重新整理為1=λ1>λ2≥…≥λN≥-1，其相應(yīng)的標(biāo)準(zhǔn)化、正交特征向量表示為ψ1,ψ2,…,ψN，其中ψi=(ψi1,ψi2,…,ψiN)表示Ψ的第i列向量。則

ΨTΨ=ΨΨT=E

(3)

令E表示N階單位矩陣。根據(jù)實(shí)對(duì)稱矩陣的性質(zhì)有：

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

(4)

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

(5)

通過(guò)上邊的分析，可以將矩陣P進(jìn)一步表示為

(6)

以上對(duì)加權(quán)網(wǎng)絡(luò)上隨機(jī)行走模型及特性進(jìn)行了分析，得到了傳輸概率矩陣P關(guān)于Ψ和S的關(guān)系式，接下來(lái)利用這些性質(zhì)對(duì)加權(quán)網(wǎng)絡(luò)上隨機(jī)行走效率進(jìn)行分析。

2 加權(quán)網(wǎng)絡(luò)上的平均首到達(dá)時(shí)間與平均吸收時(shí)間

本節(jié)通過(guò)圖譜理論方法計(jì)算含有N個(gè)節(jié)點(diǎn)的加權(quán)網(wǎng)絡(luò)G上的任意兩節(jié)點(diǎn)間的MFPT。為了方便起見，將G的N個(gè)節(jié)點(diǎn)標(biāo)注為1,2,…,N。不失一般性地，令TiN表示從任一節(jié)點(diǎn)i到任一節(jié)點(diǎn)N的MFPT。在給出TiN后我們將進(jìn)一步分析特殊節(jié)點(diǎn)的平均吸收時(shí)間(Average Trapping Time,ATT)。令TN表示節(jié)點(diǎn)N的ATT，即假定在網(wǎng)絡(luò)G上有一特殊吸收節(jié)點(diǎn)N，TN為網(wǎng)絡(luò)G上所有節(jié)點(diǎn)i到達(dá)節(jié)點(diǎn)N的MFPT的平均值。ATT在復(fù)雜網(wǎng)絡(luò)上隨機(jī)行走研究中具有非常重要的意義。

加權(quán)網(wǎng)絡(luò)G上的隨機(jī)行走是馬爾科夫過(guò)程[22]，從節(jié)點(diǎn)i到節(jié)點(diǎn)N的MFPT(TiN)可以被精確通過(guò)基礎(chǔ)矩陣Z中的一系列元素ziN描述，矩陣Z被定義為

Z=(E-P+R)-1

(7)

其中,R為πΤ的行向量。則由文獻(xiàn)[23]知：

(8)

其中,πN是靜態(tài)矩陣為π=(π1，π2，…，πN)的一個(gè)列向量，其每個(gè)元素通過(guò)如下方式求得：令Pt表示P的t次冪，那么，一個(gè)隨機(jī)行走粒子從節(jié)點(diǎn)i出發(fā)經(jīng)過(guò)t個(gè)時(shí)間步到達(dá)節(jié)點(diǎn)N的概率為表示為(pt)iN，(pt)iN為Pt它的第i行第N列元素。由式(6)可得：

(9)

(10)

當(dāng)t→∞時(shí)，可得：

(11)

因此，加權(quán)網(wǎng)絡(luò)上隨機(jī)行走的靜態(tài)矩陣可進(jìn)一步表示為

(12)

進(jìn)而，由文獻(xiàn)[22]的關(guān)于靜態(tài)概率矩陣的定義得

(13)

為求TiN，需要先給出Z的表達(dá)式。而Z中的R與P對(duì)應(yīng)的式(6)與(13)均為關(guān)于Ψ與S的表達(dá)式。因此我們也將E也表示為關(guān)于Ψ和S的關(guān)系式，則由式(3)知

(14)

那么，將(6)(13)和(14)帶入式(7)得

(15)

其中，ziN可進(jìn)一步表示為

(16)

另外，Γ的一個(gè)特征值為λ1=1，假設(shè)對(duì)應(yīng)的特征向量為ψ1。從式(2)(13)及P1=1,可得

(17)

那么通過(guò)上邊的分析，TiN可表示為

(18)

式(18)的形式和文獻(xiàn)[17]相同，但從另外一個(gè)角度給出了加權(quán)網(wǎng)絡(luò)上MFPT解析公式，且當(dāng)w0=1時(shí)，含義與文獻(xiàn)[17]相同，但本文的結(jié)果更具廣泛性。從式(18)知MFPT(TiN)的大小與目的地節(jié)點(diǎn)權(quán)重及邊權(quán)系數(shù)等有關(guān)。結(jié)合度不相關(guān)加權(quán)網(wǎng)絡(luò)的點(diǎn)權(quán)和總點(diǎn)權(quán)的數(shù)學(xué)表達(dá)式，進(jìn)一步對(duì)式(18)進(jìn)行處理得：

(19)

從式(19)可看出，在度不相關(guān)加權(quán)網(wǎng)絡(luò)上影響MFPT的網(wǎng)絡(luò)結(jié)構(gòu)的重要因素有網(wǎng)絡(luò)大小，網(wǎng)絡(luò)邊權(quán)控制系數(shù)θ。而網(wǎng)絡(luò)邊權(quán)控制系數(shù)w0對(duì)網(wǎng)絡(luò)TiN的大小沒有影響。

ATT在認(rèn)識(shí)網(wǎng)絡(luò)上隨機(jī)行走特性中也具有非常重要的意義。在文獻(xiàn)[17]，[24]中已有呈現(xiàn)。根據(jù)ATT的定義，TN的表達(dá)式可表示為

(20)

考慮式(3)、(4)，式(20)可一步表示為

(21)

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

(22)

通過(guò)式(22)知，ATT的下界與吸收點(diǎn)權(quán)重及網(wǎng)絡(luò)總點(diǎn)權(quán)有關(guān)。進(jìn)一步分析，與網(wǎng)絡(luò)大小N及其平均度、吸收點(diǎn)度大小dN、網(wǎng)絡(luò)邊權(quán)控制系數(shù)θ有關(guān)，而與網(wǎng)絡(luò)邊權(quán)控制系數(shù)w0無(wú)關(guān)，這與任意兩個(gè)節(jié)點(diǎn)間的MFPT的性質(zhì)相同。

(23)

則將(23)代入(22)得

(24)

通過(guò)以上對(duì)〈dθ+1〉的分析知，在度不相關(guān)網(wǎng)絡(luò)上的隨機(jī)行走的節(jié)點(diǎn)的TN與度分布指數(shù)有密切關(guān)系。特別地，文獻(xiàn)[17]給出了網(wǎng)絡(luò)吸收節(jié)點(diǎn)度為dmax時(shí)TN的分析結(jié)果。

3 仿真分析

為了進(jìn)一步認(rèn)識(shí)度不相關(guān)加權(quán)網(wǎng)絡(luò)上隨機(jī)行走的特性，通過(guò)計(jì)算機(jī)仿真作進(jìn)一步探索。不失一般性地，對(duì)第1節(jié)提出的網(wǎng)絡(luò)模型，利用BA無(wú)標(biāo)度網(wǎng)絡(luò)模型建立加權(quán)網(wǎng)絡(luò)模型[25]，其度分布服從P(d)～d-3。首先，建立一個(gè)N=1 000，平均度〈d〉≈10的BA無(wú)權(quán)網(wǎng)絡(luò)；然后，根據(jù)第1節(jié)提出的方法即可產(chǎn)生一個(gè)度不相關(guān)加權(quán)網(wǎng)絡(luò)G。通過(guò)分析知，當(dāng)θ=0,w0=1時(shí)，G退化為BA無(wú)權(quán)網(wǎng)絡(luò)；當(dāng)w0=0時(shí)，G上所有邊的權(quán)重均為0，無(wú)意義。

下邊對(duì)G上隨機(jī)行走進(jìn)行計(jì)算機(jī)仿真。分析不同θ值下，網(wǎng)絡(luò)G上隨機(jī)行走ATT的特性，我們對(duì)其仿真，仿真結(jié)果見圖1，圖1為在雙對(duì)數(shù)坐標(biāo)系下表示的仿真及式(22)表示的TN的下界的結(jié)果。從圖1可以看出，ATT的大小與吸收節(jié)點(diǎn)的度大小有密切關(guān)系，當(dāng)θ>-1時(shí)，吸收點(diǎn)的度越大ATT越小，吸收點(diǎn)的度越小ATT越大，呈反比關(guān)系，隨著θ值的增大，不同大小度的節(jié)點(diǎn)的隨機(jī)行走效率差異擴(kuò)大；當(dāng)θ<-1時(shí)，吸收點(diǎn)的度的大小與相應(yīng)的ATT呈正比關(guān)系，隨著θ值的減小，不同大小度的節(jié)點(diǎn)的隨機(jī)行走效率差異擴(kuò)大；當(dāng)θ=-1時(shí)，所有節(jié)點(diǎn)的ATT大小相同。呈現(xiàn)這種仿真結(jié)果是由于ATT的大小與網(wǎng)絡(luò)結(jié)構(gòu)有著密切關(guān)系，θ取值改變了網(wǎng)絡(luò)中的節(jié)點(diǎn)的連通性，當(dāng)網(wǎng)絡(luò)的連通性較好時(shí)，到達(dá)吸收節(jié)點(diǎn)的概率就大，所用的時(shí)間就少，反之時(shí)間就多。顯然地，當(dāng)θ值不變時(shí)，w0的取值大小，對(duì)于所有邊權(quán)的改變是線性、同比例改變大，相對(duì)來(lái)說(shuō)沒有改變網(wǎng)絡(luò)節(jié)點(diǎn)之間的連通性，因此，網(wǎng)絡(luò)上節(jié)點(diǎn)的ATT無(wú)變化。由圖1可以看出，仿真結(jié)果與式(22)的解析結(jié)果的分析一致。

N=1 000，〈d〉≈10，w0=1，S和A分別對(duì)應(yīng)解析和仿真情況。圖1 在雙對(duì)數(shù)坐標(biāo)系上表示的網(wǎng)絡(luò)G上取不同的權(quán)重系數(shù)θ時(shí)，ATT與吸收節(jié)點(diǎn)度d的關(guān)系圖

根據(jù)式(22)知，ATT大小與網(wǎng)絡(luò)大小N有密切關(guān)系。為使結(jié)果更加直觀，在θ=0.5,w0=1的情況下，我們?cè)诜抡鏁r(shí)對(duì)網(wǎng)絡(luò)G大小進(jìn)行調(diào)節(jié)。網(wǎng)絡(luò)G大小分別取為N=500,1 000,2 000，〈d〉≈10。仿真結(jié)果見圖2。由圖2知，在節(jié)點(diǎn)度大小相等的情況下，相應(yīng)節(jié)點(diǎn)的ATT隨著網(wǎng)絡(luò)規(guī)模的增大而增大。

網(wǎng)絡(luò)的連通性對(duì)網(wǎng)絡(luò)上隨機(jī)行走的效率有著很大影響。圖3取不同網(wǎng)絡(luò)平均度〈d〉的相同網(wǎng)絡(luò)規(guī)模上的隨機(jī)行走就行了仿真，其中N=1 000，θ=0.3,w0=1，〈d〉分別取6,10,14。從仿真圖可以看出，在網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)相同時(shí)，網(wǎng)絡(luò)平均度越大，相同的節(jié)點(diǎn)度的ATT越小。這是由于在網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)相同時(shí)，網(wǎng)絡(luò)平均度〈d〉越大，網(wǎng)絡(luò)上節(jié)點(diǎn)之間的連通性越好，這樣在隨機(jī)行走時(shí)到達(dá)某個(gè)節(jié)點(diǎn)的概率就會(huì)隨之增大。因此，在網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)相同時(shí)，網(wǎng)絡(luò)平均度越大，則其節(jié)點(diǎn)的ATT普遍較網(wǎng)絡(luò)平均度小的相同度的節(jié)點(diǎn)的ATT小，隨機(jī)行走效率越高。

〈d〉≈10，θ=0.5,w0=1圖2 在雙對(duì)數(shù)坐標(biāo)系表示的不同網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)(N)的網(wǎng)絡(luò)G上，ATT與吸收節(jié)點(diǎn)度d的關(guān)系仿真圖

N=1 000，θ=0.3,w0=1圖3 在雙對(duì)數(shù)坐標(biāo)系表示的不同大小的網(wǎng)絡(luò)平均度〈d〉的網(wǎng)絡(luò)G上，ATT與吸收節(jié)點(diǎn)度d的關(guān)系仿真圖

4 結(jié)論

本文運(yùn)用圖譜理論的方法研究了度不相關(guān)加權(quán)網(wǎng)絡(luò)上的隨機(jī)行走過(guò)程。與文獻(xiàn)[11]關(guān)注的加權(quán)網(wǎng)絡(luò)上隨機(jī)行走的MFRT指標(biāo)不同，本文對(duì)MFPT、ATT兩個(gè)重要刻畫指標(biāo)進(jìn)行了分析。通過(guò)分析，我們發(fā)現(xiàn)網(wǎng)絡(luò)的權(quán)重系數(shù)θ、吸收點(diǎn)度的大小、網(wǎng)絡(luò)大小和網(wǎng)絡(luò)平均度指標(biāo)值的大小有關(guān)，而權(quán)重系數(shù)w0與兩個(gè)指標(biāo)值的大小無(wú)關(guān)。這主要是因?yàn)棣戎档拇笮「淖兞司W(wǎng)絡(luò)節(jié)點(diǎn)的連通性，而w0沒有。對(duì)上述分析結(jié)果本文進(jìn)行了計(jì)算機(jī)仿真驗(yàn)證，解析結(jié)果與仿真結(jié)果一致。本文的研究對(duì)進(jìn)一步了解加權(quán)網(wǎng)絡(luò)上的隨機(jī)行走行為和相關(guān)網(wǎng)絡(luò)動(dòng)力學(xué)有意義。