基于稀疏貝葉斯算法的演化博弈網(wǎng)絡(luò)重構(gòu)

趙麗娜，張亞楠，肖玉柱

(長安大學(xué)理學(xué)院，陜西 西安 710064)

0 引 言

網(wǎng)絡(luò)重構(gòu)是復(fù)雜網(wǎng)絡(luò)系統(tǒng)研究中的逆問題，即根據(jù)大量系統(tǒng)觀測數(shù)據(jù)，如依據(jù)個體的時間演變狀態(tài)等個體信息，去推斷節(jié)點之間的相互作用關(guān)系，從而獲得整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。復(fù)雜網(wǎng)絡(luò)重構(gòu)的研究涉及了數(shù)學(xué)、計算機科學(xué)、社會學(xué)、生物學(xué)等不同領(lǐng)域的學(xué)科[1-4]，典型的例子包括重構(gòu)社會人際關(guān)系網(wǎng)絡(luò)、基因調(diào)控網(wǎng)絡(luò)、金融機構(gòu)之間的借貸網(wǎng)絡(luò)、計算機網(wǎng)絡(luò)等[5-7]。隨著網(wǎng)絡(luò)科學(xué)研究的深入，科學(xué)界越來越認(rèn)識到網(wǎng)絡(luò)結(jié)構(gòu)對網(wǎng)絡(luò)的行為起著重要作用。然而，實際中的網(wǎng)絡(luò)結(jié)構(gòu)往往是未知的，因此基于數(shù)據(jù)的復(fù)雜網(wǎng)絡(luò)的重建問題引起了持續(xù)關(guān)注。學(xué)者們已經(jīng)發(fā)展了一些基于統(tǒng)計物理、信息論和逆向工程的網(wǎng)絡(luò)重構(gòu)方法，如Wang等人[8]利用壓縮感知理論重構(gòu)了復(fù)雜耦合振子網(wǎng)絡(luò)；Mantegna[9]利用相關(guān)性和互信息的方法獲得了股票之間的層級結(jié)構(gòu)信息；Luo等人[10]利用Granger因果關(guān)系重構(gòu)了基因網(wǎng)絡(luò)等。

演化博弈是自然和社會系統(tǒng)中一種常見的互動類型，探知演化博弈網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是理解其功能和集體行為的基礎(chǔ)[11]。對于演化博弈網(wǎng)絡(luò)，個體的博弈行為通常難以用動力學(xué)方程進行描述，而且相關(guān)的時序信息一般數(shù)量有限并且是離散的。因此，如何基于少量離散的個體博弈時序信息，挖掘出潛在的節(jié)點間連接關(guān)系并重構(gòu)成網(wǎng)絡(luò)具有重要意義。基于壓縮感知的復(fù)雜網(wǎng)絡(luò)重構(gòu)方法已經(jīng)被用來求解演化博弈網(wǎng)絡(luò)重構(gòu)問題，該方法能夠以相對于網(wǎng)絡(luò)規(guī)模很少量的數(shù)據(jù)實現(xiàn)網(wǎng)絡(luò)連接的重構(gòu)[5]。壓縮感知重構(gòu)算法[12]主要有2類：一類是用凸優(yōu)化模型求解[13]，這類重構(gòu)算法所需要的測量數(shù)據(jù)少但計算復(fù)雜度較高；另一類是用貪婪算法進行求解[14]，此類算法計算速度快，但是精度低。此外，這2類算法都不能在噪聲較大的情況下獲得好的重構(gòu)效果。

稀疏貝葉斯學(xué)習(xí)(Sparse Bayesian Learning, SBL)算法作為一種基于概率統(tǒng)計的稀疏重構(gòu)方法，給稀疏信號處理提供了新的求解思路[15]。該算法考慮了因測量系統(tǒng)誤差或加性噪聲帶來的不確定性影響，已經(jīng)被廣泛應(yīng)用于醫(yī)學(xué)成像[16-17]、地震探查[18]、信號的無線傳輸[19]等領(lǐng)域，并取得了優(yōu)于傳統(tǒng)方法的求解結(jié)果。本文嘗試將SBL重構(gòu)算法應(yīng)用于演化博弈網(wǎng)絡(luò)的重構(gòu)，解決傳統(tǒng)壓縮感知重構(gòu)算法復(fù)雜度高以及對噪聲魯棒性差的問題。研究表明在典型的雪堆博弈[20]和囚徒博弈[21]中，即使每個博弈個體的策略和收益的可用信息有限，該方法也能夠以更快速的方式識別節(jié)點間的連接情況，并且在有噪聲的情況下具有更好的重構(gòu)性能。

1 博弈網(wǎng)絡(luò)重構(gòu)算法

1.1 博弈模型

在囚徒困境博弈(PDG)和雪堆博弈(SG)中，假設(shè)博弈個體兩兩進行博弈，任何時候一個博弈方可以選擇2種策略(S)中的一種：合作(C)或背叛(D)。當(dāng)博弈個體選擇合作時策略可以表示為向量S(C)=(1,0)T，選擇背叛時策略可表示為向量S(D)=(0,1)T。博弈中2個博弈方的收益由他們的策略和給定博弈收益矩陣決定。對于PDG和SG，收益矩陣分別為：

(1)

其中，b(1

(2)

其中，Si和Sj分別表示博弈個體i和j的策略，Γi表示個體i的所有鄰居的集合。獲得收益后，所有個體會根據(jù)其自身和鄰居的收益更新博弈策略，試圖在下一回合獲得最大收益。在演化博弈動力學(xué)研究中常使用費米規(guī)則[22]作為更新策略，即個體i在下一回合學(xué)習(xí)個體j的策略的概率為：

(3)

其中，參數(shù)κ>0為噪音，表示博弈動力學(xué)中的隨機不確定性，一般是一個很小的值，常取0.1。κ=0意味著博弈個體是絕對理性的，即當(dāng)鄰居j的收益大于自己時，個體i以概率1采取個體j的策略作為自己下一輪的策略；當(dāng)鄰居j的收益小于自己的收益時，個體i以概率0采取個體j的策略作為自己下一輪的策略，即在下一輪的博弈中仍然保持自己當(dāng)前的策略。κ→∞代表參與者完全隨機決策。

1.2 博弈網(wǎng)絡(luò)重構(gòu)

博弈網(wǎng)絡(luò)重構(gòu)問題的關(guān)鍵在于建立個體收益和策略之間的關(guān)系。假設(shè)博弈網(wǎng)絡(luò)的節(jié)點數(shù)為N,節(jié)點之間的連接情況可以用一個N×N的鄰接矩陣A來表示。如果個體i和j是進行博弈的鄰居節(jié)點，那么鄰接矩陣A的元素aij=1，否則aij=0。根據(jù)式(2)可得博弈個體x在t時刻(回合)的收益為：

(4)

Gx=Φx·Ax

(5)

其中，Ax=(ax,1,…,ax,x-1,ax,x+1,…,ax,N)T描述個體x與網(wǎng)絡(luò)的其他節(jié)點的連接情況，Φx為m×(N-1)維矩陣：

(6)

通過求解式(5)可以獲得向量Ax，從而可以獲得x與其他節(jié)點的連接情況。以類似的方式可獲得其他節(jié)點的連接情況，最終完成整個網(wǎng)絡(luò)結(jié)構(gòu)的重構(gòu)。由于實際中多數(shù)網(wǎng)絡(luò)的連接是稀疏的，即Ax中的大部分元素為0，因此可以在m

1.3 重構(gòu)算法

壓縮感知是近年來提出的一種數(shù)據(jù)獲取和信息采集方式，通過挖掘信號內(nèi)在的稀疏特征，從遠小于信號維度的壓縮數(shù)據(jù)中重構(gòu)原信號[23]。即通過少量測量y∈RM恢復(fù)信號x∈RN并滿足：

y=Φx

(7)

其中，Φ為M×N的觀測矩陣。當(dāng)方程個數(shù)遠少于未知數(shù)個數(shù)(M?N)時，式(7)是欠定的，因此方程組沒有唯一解，無法實現(xiàn)信號重構(gòu)。如果加上稀疏約束，則信號重構(gòu)問題可以表示為：

min‖x‖0s.t.y=Φx

(8)

其中，L0范數(shù)‖x‖0表示x中非零元素的個數(shù)。由于對式(8)直接求解是NP問題，常見的求解思路是使用L1范數(shù)替代L0范數(shù),即求解凸優(yōu)化問題：

min‖x‖1s.t.y=Φx

(9)

稀疏貝葉斯學(xué)習(xí)(SBL)方法最初作為一種機器學(xué)習(xí)算法，后被引入稀疏信號的重構(gòu)[25]。SBL重構(gòu)算法的總體目標(biāo)是從以下數(shù)學(xué)模型中估計稀疏信號x：

y=Φx+ω

(10)

其中，ω為噪聲。假定x中的每個分量相互獨立且服從均值為0、方差為γi的高斯分布，即：

(11)

其中，xi(i=1,…,N)表示x中的第i個分量，γi是未知參數(shù)，由算法自動估計出來。在SBL的框架中，假設(shè)噪聲服從均值為0、方差為δ2I的高斯分布，即：

p(ω|δ2)=N(0,δ2I)

(12)

根據(jù)以上假設(shè)可以得到y(tǒng)的后驗分布為：

(13)

由全概率公式可得觀測變量y的邊緣概率密度函數(shù)為：

(14)

其中，Σy=δ2I+ΦΓΦT,Γ?diag(γ)。利用貝葉斯基本定理可得到x的后驗分布：

p(x|y,γ,δ2)=N(μ,Σx)

(15)

其中，μ=(δ2)-1ΣxΦTy,Σx=((δ2)-1ΦTΦ+Γ-1)-1。通過EM算法估計參數(shù)γ和δ2，參數(shù)γ在第k次的迭代估計為：

(16)

參數(shù)δ2在第k次的迭代估計為：

(17)

與廣泛使用的基于L1的優(yōu)化算法相比，SBL算法具有以下優(yōu)勢：1)SBL算法在優(yōu)化求解過程中自動保證了x的稀疏性而無需人為設(shè)置參數(shù)，且算法復(fù)雜度低，收斂速度快；2)基于SBL重構(gòu)算法在建模中考慮了對噪聲影響，因而相對非貝葉斯算法具有較好的抗噪性能。因此，本文將嘗試應(yīng)用SBL算法研究博弈網(wǎng)絡(luò)的重構(gòu)問題，進一步提高重構(gòu)算法的收斂速度,以及對噪聲的魯棒性。

2 數(shù)值模擬

本章將采用MATLAB實驗平臺，以隨機網(wǎng)絡(luò)[26]和小世界網(wǎng)絡(luò)[27]為例對本文基于SBL的重構(gòu)方法進行模擬驗證，并和基于l1-magic軟件包的重構(gòu)結(jié)果從以下3方面進行比較：1)重構(gòu)所需數(shù)據(jù)量；2)算法的收斂性能；3)算法對噪聲的魯棒性。為了量化重構(gòu)方法的重構(gòu)性能，引入存在鏈接重構(gòu)成功率(SREL)和不存在鏈接重構(gòu)成功率(SRNL)。對于給定的節(jié)點，SREL定義為成功預(yù)測的鄰居數(shù)與實際鄰居數(shù)的比值，SRNL定義為成功預(yù)測的非鄰居數(shù)與實際的非鄰居數(shù)的比值，整個網(wǎng)絡(luò)的SREL和SRNL由網(wǎng)絡(luò)所有節(jié)點SREL和SRNL的平均值定義。將存在和不存在鏈接分開處理的原因在于復(fù)雜網(wǎng)絡(luò)的稀疏性，即不存在鏈接的數(shù)量通常比存在鏈接的數(shù)量大得多。由于在實際求解中，鄰接矩陣A中的元素不可能精確等于1或0，因此，在實驗中指定一個較小的閾值0.1，這樣存在鏈接的范圍為1±0.1，不存在鏈接的范圍是0±0.1，這2個區(qū)間之外的任何值都被認(rèn)為是預(yù)測失敗。

2.1 隨機網(wǎng)絡(luò)

給定網(wǎng)格節(jié)點數(shù)N=100，網(wǎng)絡(luò)中任意2點以概率p=0.1相連接(2個參數(shù)共同反映了網(wǎng)絡(luò)的疏密程度，本實驗中參數(shù)的取值保證了網(wǎng)絡(luò)的稀疏性)。有研究表明，隨機網(wǎng)絡(luò)模型與現(xiàn)實世界有很大相關(guān)性，例如社交媒體平臺形成的網(wǎng)絡(luò)結(jié)構(gòu)特征類似于隨機網(wǎng)絡(luò)。因此，研究隨機網(wǎng)絡(luò)有助于人們理解小型社交網(wǎng)絡(luò)的結(jié)構(gòu)。2種博弈類型在隨機網(wǎng)絡(luò)的重構(gòu)成功率如圖1和圖2所示。PDG和SG的收益矩陣中的參數(shù)分別為b=1.2和r=0.7(在參數(shù)的取值范圍內(nèi)測試了其他數(shù)值，取得了類似的成功率)，噪聲參數(shù)κ=0.1。Data表示測量值的數(shù)量與網(wǎng)絡(luò)節(jié)點數(shù)N的比值。Success rate表示存在/不存在鏈接預(yù)測的成功率。對于不同的博弈類型，只要極少量的數(shù)據(jù)就可以獲得完美的成功率。例如，對于囚徒困境博弈，實現(xiàn)100%成功率所需的數(shù)據(jù)長度在0.4左右。從圖1和圖2可以看出SBL求解方法和L1算法在成功重構(gòu)網(wǎng)絡(luò)時所需的最小數(shù)據(jù)量是相近的。L1算法和SBL算法成功重構(gòu)囚徒博弈網(wǎng)絡(luò)所需的最小數(shù)據(jù)量分別為0.40和0.44；重構(gòu)雪堆博弈網(wǎng)絡(luò)所需最小數(shù)據(jù)量分別為0.39和0.46。

(a) L1重構(gòu)

(a) L1重構(gòu)

為了進一步測試本文算法的求解速度，與L1算法進行收斂性能的比較。采用囚徒博弈數(shù)據(jù)在節(jié)點數(shù)為N=100的隨機網(wǎng)絡(luò)上進行實驗(見圖3)。從算法收斂時間可以看出，SBL算法的收斂速度要優(yōu)于L1優(yōu)化算法，尤其是在數(shù)據(jù)量比較充足的情況下，可以進行更高效的求解。

圖3 隨機網(wǎng)絡(luò)中算法收斂時間比較

在現(xiàn)實生活中，噪聲是無處不在的，很難得到?jīng)]有噪聲的數(shù)據(jù)集。因此，在觀測數(shù)據(jù)受噪聲污染的情況下測試了2種重構(gòu)算法的抗噪性能。實驗中，參數(shù)設(shè)置與本文第1個實驗中重構(gòu)PDG網(wǎng)絡(luò)參數(shù)設(shè)置相同。在PDG的收益數(shù)據(jù)中分別加入不同信噪比(Signal to Noise Ratio, SNR)的高斯白噪聲，圖4～圖6給出了2種算法在SNR分別為10 dB、5 dB和1 dB的重構(gòu)情況(在不同信噪比仿真實驗中，過小的噪聲對2種算法的重構(gòu)效果影響不大，而很大的噪聲則使得2種算法均不能完全重構(gòu)，因此選取了噪聲由小到大的3組有代表性的結(jié)果，在大量的仿真實驗均表明了以下的結(jié)論)。實驗表明，在噪聲大小和觀測數(shù)據(jù)量相同時，SBL可以獲得更高的重構(gòu)精度。例如SNR=5 dB時，使用0.4的數(shù)據(jù)量進行重構(gòu)，SBL算法求解的存在鏈接預(yù)測成功率為0.9左右，而L1算法僅為0.65左右。另一方面，隨著噪聲的增大，二者重構(gòu)效果逐漸變差，但SBL重構(gòu)方法依舊可以在數(shù)據(jù)量相對充足的情況下進行重構(gòu)。綜合可以看出在噪聲環(huán)境中，SBL重構(gòu)方法具有更好的穩(wěn)健性。

(a) L1重構(gòu)

(a) L1重構(gòu)

(a) L1重構(gòu)

2.2 小世界網(wǎng)絡(luò)

小世界網(wǎng)絡(luò)最早是由Watts等人[27]在1998年引進的一種斷邊重連的構(gòu)造網(wǎng)絡(luò)的方法。從規(guī)則網(wǎng)絡(luò)入手，隨機以某個概率p斷掉規(guī)則網(wǎng)絡(luò)的邊并且隨機選擇網(wǎng)絡(luò)中的頂點進行重連。小世界網(wǎng)絡(luò)是一種既具有較高的集聚又具有很短的平均最短路徑的網(wǎng)絡(luò)結(jié)構(gòu)。它連通了規(guī)則和完全隨機2個極端的性質(zhì)，能夠更好地刻畫實際網(wǎng)絡(luò)的結(jié)構(gòu)性質(zhì)。一些研究表明，生物學(xué)、物理學(xué)、社會學(xué)中大多數(shù)網(wǎng)絡(luò)都具有小世界網(wǎng)絡(luò)的特征[28-29]，因此研究小世界網(wǎng)絡(luò)具有廣泛的現(xiàn)實意義。

本文中以節(jié)點數(shù)N=100，每個節(jié)點的連接邊數(shù)k=8(該參數(shù)反映了網(wǎng)絡(luò)的疏密程度)，重新連接概率p=0.1(當(dāng)重連概率較小時，網(wǎng)絡(luò)既具有較短的平均路徑長度又具有較高的聚集系數(shù)，與各種社會網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)及生物網(wǎng)絡(luò)等有較高的擬合性)產(chǎn)生小世界網(wǎng)絡(luò)，網(wǎng)絡(luò)中的其他參數(shù)設(shè)置與1.1節(jié)中的隨機網(wǎng)絡(luò)相同。計算結(jié)果表明在沒有噪聲影響的情況下,SBL方法和L1算法在成功重構(gòu)網(wǎng)絡(luò)時所需的最小數(shù)據(jù)量是相近的(見圖7和圖8)，L1算法和SBL算法成功重構(gòu)囚徒博弈網(wǎng)絡(luò)所需的最小數(shù)據(jù)量分別為0.35和0.38；重構(gòu)雪堆博弈網(wǎng)絡(luò)所需最小數(shù)據(jù)量分別為0.32和0.35。且SBL算法的收斂速度要優(yōu)于L1優(yōu)化算法(見圖9)。圖10～圖12給出了2種算法在SNR分別為15 dB、10 dB和5 dB的情況下，PGD網(wǎng)絡(luò)的重構(gòu)結(jié)果。實驗表明在噪聲情況下，SBL算法有更好的重構(gòu)性能。

(a) L1重構(gòu)

(a) L1重構(gòu)

圖9 小世界網(wǎng)絡(luò)中算法收斂時間比較

(a) L1重構(gòu)

(a) L1重構(gòu)

(a) L1重構(gòu)

3 結(jié)束語

演化博弈網(wǎng)絡(luò)是自然和社會系統(tǒng)中常見的一種互動類型，它在生物學(xué)、社會科學(xué)、經(jīng)濟學(xué)等領(lǐng)域有著重要的應(yīng)用，探知演化博弈網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是理解其功能和集體行為的基礎(chǔ)。基于稀疏貝葉斯學(xué)習(xí)算法，本文進一步發(fā)展了有限數(shù)據(jù)下演化博弈網(wǎng)絡(luò)的重構(gòu)方法。與先前的基于L1范數(shù)重構(gòu)方法相比較，稀疏貝葉斯學(xué)習(xí)方法同樣能在較少的博弈信息下重構(gòu)網(wǎng)路，且有更好的收斂性能，以及更強的噪聲魯棒性。本文的試驗數(shù)據(jù)基于理論模型通過數(shù)值模擬產(chǎn)生，將該方法應(yīng)用于實際數(shù)據(jù)分析和真實系統(tǒng)重構(gòu)是面臨的重大挑戰(zhàn)。