賈鳴明，陳含爽，張海峰

（安徽大學(xué)1.數(shù)學(xué)科學(xué)學(xué)院，2.物理與材料科學(xué)學(xué)院，安徽合肥230601）

隨機(jī)游走是研究隨機(jī)過程的一類重要模型[1]。早在1905 年，Karl Perason 在《Nature》雜志上就提出了隨機(jī)游走這個名詞[2]。同年，Albert Einstein發(fā)表了一篇研究懸浮在液體中的布朗粒子隨機(jī)運(yùn)動的文章，并導(dǎo)出了著名的漲落耗散定理[3]。至此，隨機(jī)游走的理論研究不僅推動了許多學(xué)科的發(fā)展，如概率論、計算科學(xué)、統(tǒng)計物理等，而且應(yīng)用到了很多實際問題中，如動物的遷徙和覓食[4]，神經(jīng)元放電動力學(xué)[5]，高分子、細(xì)胞等生命組織在復(fù)雜環(huán)境中的擴(kuò)散過程[6]，PaegRank排序算法[7]，金融市場的模擬等[8]。復(fù)雜網(wǎng)絡(luò)是描述自然界大量復(fù)雜系統(tǒng)的有用模型，如社交網(wǎng)絡(luò)、萬維網(wǎng)和蛋白質(zhì)相互作用網(wǎng)絡(luò)等[9]。復(fù)雜網(wǎng)絡(luò)上隨機(jī)游走的研究日益增多[10]，不僅包括在任意網(wǎng)絡(luò)上穩(wěn)態(tài)占據(jù)概率和平均首達(dá)時間等重要量的推導(dǎo)，以及標(biāo)度行為和圖譜特性的關(guān)系等[11-13]，還包括在網(wǎng)絡(luò)實際問題中的應(yīng)用研究，如計算機(jī)網(wǎng)絡(luò)上路由策略[14]、社團(tuán)結(jié)構(gòu)[15]、核心邊緣結(jié)構(gòu)[16]等中尺度結(jié)構(gòu)劃分，排序[17]、鏈路預(yù)測[18]、傳播[19]、觀點動力學(xué)等問題[20]。

目前，大部分研究關(guān)注的是無記憶的馬爾可夫游走過程，即游走者下一時刻的位置只依賴當(dāng)前位置而與之前所處的位置無關(guān)。然而，基于對人類出行、船運(yùn)等實證數(shù)據(jù)的研究都表明，實際的擴(kuò)散過程是非馬爾可夫的[21-22]。本文研究一類特殊的非馬爾可夫隨機(jī)游走模型——非回溯隨機(jī)游走。該模型中游走者具有短期記憶效應(yīng)，他能夠記住上一時刻所處節(jié)點并要求不能立刻返回該節(jié)點。通過定義二階節(jié)點（即網(wǎng)絡(luò)中一條有向邊），可以將該模型轉(zhuǎn)為馬爾可夫過程來研究。在這個二階馬爾可夫模型中，游走者的轉(zhuǎn)移概率是依賴于網(wǎng)絡(luò)的非回溯矩陣。

1 模型定義

在一般的隨機(jī)游走（RW）模型中，定義t時刻一個游走者處于節(jié)點i，在t+1時刻該游走者隨機(jī)擴(kuò)散到的節(jié)點i的一個近鄰節(jié)點j，該隨機(jī)過程屬于馬爾可夫過程。而在非回溯隨機(jī)游走中（NRM），游走者從他所在的節(jié)點隨機(jī)游走到一個近鄰節(jié)點，但不能立刻返回。例如，t-1時刻游走者處于節(jié)點i，t時刻游走者從節(jié)點i游走到節(jié)點j，t+1時刻該游走者隨機(jī)游走到節(jié)點j的一個近鄰節(jié)點，但不包括節(jié)點i，該隨機(jī)過程是非馬爾可夫的。該模型可以利用二階馬爾可夫模型來代替[23]，如圖1所示。為此，定義二階節(jié)點為ij，即表示在相鄰的時刻粒子從節(jié)點i游走到節(jié)點j。記粒子的轉(zhuǎn)移概率為Wij,lk，即表示在相鄰時刻游走者從二階節(jié)點ij轉(zhuǎn)移到二階節(jié)點lk的概率。對非回溯隨機(jī)游走，

其中，Bij,lk是網(wǎng)絡(luò)的非回溯矩陣元，已在網(wǎng)絡(luò)滲流[24]、中心性[25]和社團(tuán)劃分[26]等問題中發(fā)揮著重要的作用，其定義為Bij,lk=δjl( )1-δik，其中，δij為克羅內(nèi)克符號：當(dāng)i=j 時，δij=1；當(dāng)i ≠j 時，δij=0。因此，僅當(dāng)j=l和i ≠k時，非回溯矩陣元Bij,lk=1；否則，Bij,lk=0。dj是節(jié)點j的度，即節(jié)點j的最近鄰的鄰居數(shù)目。

圖1 非回溯隨機(jī)游走的二階馬爾可夫表示圖

2 結(jié)果分析

定義Pij( t )為t時刻游走者處于二階節(jié)點ij的占據(jù)概率。Pij( t )滿足主方程：矩陣形式：P( t+1 )=P( t )W，其中，P={ Pij}為2×E 維行向量，E 為網(wǎng)絡(luò)的邊數(shù)目。當(dāng)t →∞，占據(jù)概率達(dá)到穩(wěn)態(tài)，Ps=P( ∞)，滿足方程P( ∞ )=P( ∞)W。可以看出，Ps是轉(zhuǎn)移矩陣W的特征值為1時所對應(yīng)的左特征向量。不難驗證，轉(zhuǎn)移矩陣W滿足行和、列和都為1（雙隨機(jī)矩陣），特征值1對應(yīng)的左特征向量為( 1,1,1,…,1 )，歸一化得。定義Pis為節(jié)點i的穩(wěn)態(tài)占據(jù)概率，

這個結(jié)論和一般的隨機(jī)游走是相同的，即穩(wěn)態(tài)時占據(jù)某一節(jié)點的概率正比于該節(jié)點的度[11]。為了驗證這一結(jié)論，我們在不同的網(wǎng)絡(luò)上模擬非回溯隨機(jī)游走，并統(tǒng)計每個節(jié)點的占據(jù)概率。我們使用了兩個Barabasi-Albert（BA）網(wǎng)絡(luò)和兩個無標(biāo)度網(wǎng)絡(luò)（SFN），其中后者通過配置模型生成[9]。對BA網(wǎng)絡(luò)，平均度=4，網(wǎng)絡(luò)大小分別為N=1000和N=5 000。對SFN，最小度kmin=2，網(wǎng)絡(luò)大小N=10 000，度分布冪律指數(shù)分別為γ=2.5和γ=3.5。圖2展示了理論結(jié)果（線）和模擬結(jié)果（點），可以看出，模擬和理論完全吻合。

在隨機(jī)游走的研究中，一個重要的物理量是首達(dá)時間，即游走者從節(jié)點i出發(fā)，第一次到達(dá)節(jié)點j的時間稱為從節(jié)點i 到節(jié)點j 的首達(dá)時間。顯然，首達(dá)時間是一個隨機(jī)量，它的期望值就是平均首達(dá)時間（MFPT）。從節(jié)點i到節(jié)點j的平均首達(dá)時間記為Ti,j。類似地，定義Tmi,j為從二階節(jié)點mi出發(fā)，首次到達(dá)節(jié)點j的平均時間。Tmi,j滿足遞歸方程

進(jìn)一步，得到從節(jié)點i出發(fā)，首次到達(dá)節(jié)點j( j ≠i)的平均時間

和從節(jié)點i出發(fā)、首次返回到節(jié)點i的平均時間

圖3給出了一個平均度為4，節(jié)點數(shù)目N=30的BA無標(biāo)度網(wǎng)絡(luò)（圖3（a））上非回溯隨機(jī)游走的平均首達(dá)時間的理論結(jié)果和模擬結(jié)果（圖3（b））?？梢钥闯觯碚摻Y(jié)果和模擬結(jié)果吻合得非常好，平均首達(dá)時間按到達(dá)節(jié)點的度呈現(xiàn)臺階的分布。也就是說，平均首達(dá)時間主要依賴于到達(dá)節(jié)點的度，到達(dá)節(jié)點的度越大，平均首達(dá)時間一般也越短。為比較起見，圖3（c）給出了一般隨機(jī)游走的平均首達(dá)時間的理論和模擬結(jié)果。與非回溯隨機(jī)游走相比，一般隨機(jī)游走的平均首達(dá)時間要更長，同樣呈現(xiàn)類似的臺階分布，但漲落變大了。

圖3 (a)BA網(wǎng)絡(luò)；(b)非回溯隨機(jī)游走的平均首達(dá)時間；(c)一般隨機(jī)游走的平均首達(dá)時間

下面計算全局平均首達(dá)時間（GMFPT），即平均首達(dá)時間對出發(fā)節(jié)點穩(wěn)態(tài)占據(jù)概率的統(tǒng)計平均，其定義為

圖4給出了前述4個網(wǎng)絡(luò)上非回溯隨機(jī)游走和一般隨機(jī)游走的全局平均首達(dá)時間隨節(jié)點度的分布圖。一方面，無論哪種網(wǎng)絡(luò)非回溯隨機(jī)游走的全局平均首達(dá)時間都要比一般隨機(jī)游走的全局平均首達(dá)時間短，這意味著非回溯隨機(jī)游走的搜索效率更高。另一方面，對度大小相同的節(jié)點，非回溯隨機(jī)游走全局平均首達(dá)時間漲落非常小，也就是說，非回溯隨機(jī)游走中全局平均首達(dá)時間更嚴(yán)格地依賴于到達(dá)節(jié)點的度。而對一般隨機(jī)游走，度相同的節(jié)點的全局平均首達(dá)時間的漲落比較大。對度相同節(jié)點的全局平均首達(dá)時間作平均，在雙對數(shù)坐標(biāo)下全局平均首達(dá)時間隨節(jié)點度可以很好地擬合成一條直線。我們發(fā)現(xiàn)兩種情況下，直線的斜率都為-1，即全局平均首達(dá)時間按～k-1j的規(guī)律變化。

圖4 非回溯隨機(jī)游走和一般隨機(jī)游走的全局平均首達(dá)時間隨節(jié)點度的變化圖

非回溯隨機(jī)游走和一般隨機(jī)游走的覆蓋時間定義為從某個節(jié)點出發(fā)，遍歷網(wǎng)絡(luò)所有節(jié)點的時間，記C(i)為從節(jié)點i 出發(fā)的覆蓋時間。覆蓋時間C(i)多次隨機(jī)游走的平均，稱為平均覆蓋時間，記為。圖5 給出了前述4 種不同網(wǎng)絡(luò)中非回溯隨機(jī)游走和一般隨機(jī)游走的平均覆蓋時間隨節(jié)點的變化，可以看出：（1）平均覆蓋時間不顯著依賴出發(fā)節(jié)點；（2）非回溯隨機(jī)游走的平均覆蓋時間要比一般隨機(jī)游走的少。將平均覆蓋時間對節(jié)點的占據(jù)概率做平均，即得到網(wǎng)絡(luò)平均覆蓋時間的期望值，如圖5中橫線所示。

圖5 非回溯隨機(jī)游走和一般隨機(jī)游走的平均覆蓋時間隨節(jié)點編號的變化圖

3 結(jié)束語

本文通過定義二階節(jié)點的方法，將具有短期記憶效應(yīng)的非回溯隨機(jī)游走模型轉(zhuǎn)化為馬爾可夫過程來研究，嚴(yán)格推導(dǎo)出非回溯隨機(jī)游走的穩(wěn)態(tài)占據(jù)概率的表達(dá)式，表明了穩(wěn)態(tài)占據(jù)概率與節(jié)點度成正比的結(jié)論，這與一般隨機(jī)游走的結(jié)論是一致的；推導(dǎo)出任意兩個節(jié)點之間平均首達(dá)時間的計算公式。與一般隨機(jī)游走比較，非回溯隨機(jī)游走的平均首達(dá)時間要短，且更依賴于到達(dá)節(jié)點的度。最后計算了全局平均首達(dá)時間和平均覆蓋時間，無論是非回溯隨機(jī)游走還是一般隨機(jī)游走，全局平均首達(dá)時間都是按節(jié)點度的負(fù)一次方衰減，平均覆蓋時間不依賴于節(jié)點的度。我們的研究表明，非回溯隨機(jī)游走比一般的隨機(jī)游走具有更高的搜索效率。因此，非回溯隨機(jī)游走在網(wǎng)絡(luò)路由、搜索和分類問題中具有潛在的應(yīng)用價值。