一種雪堆博弈網(wǎng)絡(luò)重構(gòu)算法研究與仿真

摘 要： 針對演化博弈網(wǎng)絡(luò)拓?fù)潆y以事先確定的問題，提出一種基于壓縮感知理論的雪堆博弈復(fù)雜網(wǎng)絡(luò)重構(gòu)算法。通過個體博弈時序信息將網(wǎng)絡(luò)重構(gòu)問題轉(zhuǎn)化成壓縮感知理論可以處理的形式，同時運用雙曲正切函數(shù)和修正牛頓法對求解過程進(jìn)行進(jìn)一步優(yōu)化，從而實現(xiàn)對網(wǎng)絡(luò)拓?fù)涞挠行е貥?gòu)，并通過Matlab 7.0作為實驗平臺對算法進(jìn)行相應(yīng)的驗證與仿真實驗，實驗結(jié)果表明，只需要較少量的時序信息就可以快速準(zhǔn)確地完成重構(gòu)工作。

關(guān)鍵詞： 雪堆博弈； 時間序列； 壓縮感知； 修正牛頓法； 復(fù)雜網(wǎng)絡(luò)

中圖分類號： TN926?34； TP18 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2016）14?0073?04

Compressive sensing based algorithm of snowdrift game network reconstruction

YANG Aiyun1， LOU Hong2

（1. Department of Computer， Henan Institute of Engineering， Zhengzhou 451191， China；

2. College of Information Engineering， Zhongzhou University， Zhengzhou 450000， China）

Abstract： Since it is difficult to determine the network topology of evolutionary game in advance， a complex network reconstruction algorithm based on compressive sensing theory for snowdrift game is proposed in this paper. Network construction is converted into a form that can be handled by compressed sensing theory by means of time series information. The solving process is optimized with hyperbolic tangent function and revised Newton method， so as to realize the effective reconstruction of the network topology. By taking Matlab 7.0 as experimental platform， corresponding verification and simulation experiment were conducted for this algorithm. The experimental results show that the network construction can be completed quickly and accurately with less time series information.

Keywords： snowdrift game； time series； compressive sensing； revised Newton method； complex network

0 引 言

作為存在于自然界和人類社會中的普遍現(xiàn)象，個體的演化博弈行為獲得了生物學(xué)以及各種社會科學(xué)尤其是經(jīng)濟學(xué)學(xué)者極大的研究興趣[1]，而針對博弈個體（節(jié)點）間存在的錯綜復(fù)雜的利益關(guān)系，使得復(fù)雜網(wǎng)絡(luò)理論成為研究相互競爭的自私個體間博弈演化的有力工具[2]。但是在實際網(wǎng)絡(luò)研究中，人們往往無法直接或事先獲知所有節(jié)點間的鏈接情況（如恐怖組織），即網(wǎng)絡(luò)拓?fù)涫俏粗模鄬Ω嗟氖侵荒塬@得各個節(jié)點的相關(guān)時序信息。

如何基于個體行為及時序信息重構(gòu)網(wǎng)絡(luò)拓?fù)湟殉蔀榻陙韽?fù)雜網(wǎng)絡(luò)研究的熱點問題[3?5]，并已取得了一定成果；如文獻(xiàn)[6?7]利用基因表達(dá)數(shù)據(jù)重構(gòu)基因調(diào)控網(wǎng)絡(luò)；文獻(xiàn)[8]利用大腦活動數(shù)據(jù)提取腦功能網(wǎng)絡(luò)等。但是，當(dāng)前的大部分研究方法或者需要一定的關(guān)于目標(biāo)網(wǎng)絡(luò)動力學(xué)方程的先驗知識，或者要求節(jié)點的時序信息是長時并且連續(xù)的[9]。

對于演化博弈網(wǎng)絡(luò)，個體的博弈行為通常難以用動力學(xué)方程進(jìn)行描述，同時其相關(guān)時序信息一般數(shù)量有限并且是離散的；因此，如何基于少量的個體博弈離散時序信息，挖掘出潛在的節(jié)點鏈接關(guān)系并重構(gòu)成網(wǎng)絡(luò)，是本文所要解決的問題。文獻(xiàn)[9?11]提出一種基于壓縮感知[12]的復(fù)雜網(wǎng)絡(luò)重構(gòu)方法，能夠以相對于網(wǎng)絡(luò)規(guī)模很少量的數(shù)據(jù)實現(xiàn)拓?fù)渲貥?gòu)，并對非線性系統(tǒng)及振子混沌網(wǎng)絡(luò)等進(jìn)行了重構(gòu)嘗試，取得很好的效果。

本文以演化博弈中的經(jīng)典模型——雪堆博弈為研究對象，基于個體在雪堆博弈過程中產(chǎn)生的時序信息，利用壓縮感知方法確定節(jié)點間的拓?fù)潢P(guān)系，并針對傳統(tǒng)壓縮感知算法的運算效率問題，采用修正牛頓法進(jìn)行優(yōu)化求解，從而構(gòu)建出對應(yīng)的雪堆博弈網(wǎng)絡(luò)拓?fù)洹Ｔ诤竺娴膶嶒炛锌梢钥吹剑恍枰倭康臅r序信息，本文方法就可以快速準(zhǔn)確地完成對網(wǎng)絡(luò)的構(gòu)建工作。

1 相關(guān)背景

1.1 雪堆博弈模型

雪堆博弈[3]是一種兩人對稱博弈模型，描述了兩個人相遇時是彼此合作共同受益，還是彼此欺騙來相互報復(fù)。它揭示了個體理性和群體理性的矛盾對立。由于雪堆模型當(dāng)個體遇到背叛者時選擇合作的收益會高于雙方相互背叛的收益，因此該模型更多地應(yīng)用于研究如何在合作型事件中獲得更高的收益。

具體模型描述如下：設(shè)博弈個體i可以選擇的策略為S，分別為合作（C），設(shè)為[SC=1，0T]，以及背叛（D），設(shè)為[SD=0，1T]。個體i的收益由自身策略和對方博弈個體j的策略共同決定，其收益矩陣可以設(shè)為：

式中：b表示鏟雪的回報（即出現(xiàn)合作者）；c表示鏟雪的代價（由合作者均攤），b一般大于c。那么對于一個雪堆博弈網(wǎng)絡(luò)，節(jié)點i會同時與它的所有鄰居進(jìn)行博弈，其每一回合的收益Gi為：

式中：Ni表示節(jié)點i的鄰居集合。節(jié)點在每一回合博弈結(jié)束后，會根據(jù)自己和鄰居的收益調(diào)整自己的策略，以使得自己在后續(xù)的回合中獲得理想的收益，從而形成一個博弈演化過程。常見的策略演化規(guī)則有模仿最優(yōu)者、復(fù)制動力學(xué)、費米動力學(xué)等[14]。由于本文實驗部分會采用費米動力學(xué)規(guī)則進(jìn)行雪堆博弈演化，因此這里給出費米動力學(xué)的規(guī)則：節(jié)點i下回合學(xué)習(xí)節(jié)點j策略的概率為：

式中：G表示本回合收益；κ用來表示節(jié)點的理性程度，當(dāng)κ趨近于0時，節(jié)點只會學(xué)習(xí)本回合收益比自己高的鄰居的策略，而隨著κ的增大，節(jié)點學(xué)習(xí)低收益鄰居策略的概率則會增大。

由于演化博弈是個多次動態(tài)過程，因此當(dāng)前最優(yōu)策略發(fā)生動蕩的概率很大，增加一定的非理性噪聲有可能會獲得更好的收益。

1.2 壓縮感知

壓縮感知，又稱壓縮采樣、壓縮傳感。它作為一種新的信息獲取理論，通過開發(fā)信號的稀疏特性，能夠在遠(yuǎn)小于Nyquist 采樣率的條件下，基于隨機采樣獲取信號的離散樣本，利用非線性重建算法實現(xiàn)對信號的精確重建。壓縮感知理論的核心思想在于通過少量測量值[SS∈RM]恢復(fù)稀疏向量 [aa∈RN，]并滿足[S=D?a]。其中D是一個M×N維滿秩矩陣，而信號重建過程即為對以下優(yōu)化問題進(jìn)行求解，如式（4）所示。

式中，[a0]是向量a的L0范數(shù)。壓縮感知的優(yōu)勢在于，當(dāng)向量a稀疏并且D滿足約束條件時，M可以遠(yuǎn)小于N，并且a中非零元素的個數(shù)也小于M。

由于復(fù)雜網(wǎng)絡(luò)本身表現(xiàn)出的稀疏性，保證了向量a的稀疏性，那么只要把復(fù)雜網(wǎng)絡(luò)重構(gòu)問題轉(zhuǎn)化成壓縮感知理論能夠處理的形式，就可以利用這一方法基于少量的時序信息準(zhǔn)確重構(gòu)網(wǎng)絡(luò)拓?fù)洹Ｍ瑫r，由于對式（4）直接求解十分困難，所以常見的求解思路是將式（4）用基于L1范數(shù)最小化的凸優(yōu)化模型替代，如梯度投影法、基追蹤法等，但是這類算法的計算復(fù)雜度較高；另一種思路是用貪婪算法對式（4）進(jìn)行近似求解，如梯度追蹤法（GP）[16]，子空間追蹤法（SP）[7]，正交匹配追蹤法（OMP）[8]等，這類算法求解精度低于前一類算法。本文則通過選取光滑函數(shù)[9]來實現(xiàn)對L0范數(shù)的近似，以提高算法的求解精度，并利用修正牛頓法進(jìn)一步提高算法的收斂速度。

2 雪堆博弈網(wǎng)絡(luò)重建算法

設(shè)博弈網(wǎng)絡(luò)中節(jié)點個數(shù)為n，各個節(jié)點間的鏈接情況可以用一個n階鄰接矩陣A表示，若節(jié)點j是與節(jié)點i進(jìn)行博弈的鄰居，則矩陣元素[aij=1]，反之[aij=0]。那么根據(jù)式（2），節(jié)點i在時刻（回合）t的收益Gi（t）可以進(jìn)一步用式（5）來表示。

式（5）可以涵蓋節(jié)點i與網(wǎng)絡(luò)中所有節(jié)點（除節(jié)點i）進(jìn)行博弈的所有可能情況。

設(shè)[ai=ai1，ai2，…，aij，…，ainT]，由于復(fù)雜網(wǎng)絡(luò)中鏈接是稀疏的，節(jié)點i實際只與少數(shù)鄰居節(jié)點進(jìn)行博弈，即ai中大部分元素等于0，ai的這種稀疏性保證了可以利用壓縮感知理論對其進(jìn)行求解。設(shè)已知m個時刻的博弈時序信息，即已知各個節(jié)點在這m個時刻所選擇的策略和獲得的收益。若設(shè)節(jié)點i的收益向量[Si=Git1，Git2，…，GitmT]，并給出感知矩陣Di如式（6）所示：

根據(jù)式（5）可以看到，此時[Si=Di?ai]已經(jīng)轉(zhuǎn)化成了壓縮感知理論可以進(jìn)行處理的[S=D?a]的形式。通過求解出ai，就可以得知節(jié)點i與其他節(jié)點的鏈接情況，進(jìn)行得出鄰接矩陣A實現(xiàn)網(wǎng)絡(luò)重構(gòu)。由于傳統(tǒng)的L0范數(shù)逼近求解方法在精度上存在不足，本文選取雙曲正切函數(shù)來更好地提高逼近性能，如式（7）所示：

式中：ax表示向量ai的分量；σ為調(diào)整參數(shù)，由于在σ趨近于0的情況下，當(dāng)ax等于0時，[fσax]的極限值也等于0；而當(dāng)ax不等于0時，[fσax]的極限值則等于1。那么若設(shè)[Fσai=x=1nfσax]，其函數(shù)值則會近似于向量ai中非0分量的個數(shù)，即逼近于L0范數(shù)。由于σ只能無限趨近而無法等于0，因此實際求解過程是逐漸縮小σ的值，并從中迭代出使得[Fσai]函數(shù)值達(dá)到最小所對應(yīng)的向量ai。在迭代過程中，常見的最速下降法在搜索中容易出現(xiàn)鋸齒現(xiàn)象，因而收斂速度較慢，本文通過對所選雙曲正切函數(shù)的下降方向進(jìn)行牛頓修正，以加快算法的收斂速度。由于針對[Fσai]的牛頓方向d中的Hesse矩陣不是正定矩陣，如式（8）所示，這會極大地影響d的下降效果。

為了解決這一問題，本文通過構(gòu)造一個修正矩陣U來保證其正定性，如式（9）所示：

[U=?2Fσai+εxI] （9）

式中：I為單位矩陣；εx為修正系數(shù)，計算方法如式（10）所示：

[εx=16ax2σ4eax22σ2eax22σ2+e-ax22σ2] （10）

此時經(jīng)過正定性修正的牛頓方向d為：

[d=-U-1?Fσai] （11）

具體迭代求解流程描述如下：

（1） 首先設(shè)定余量r0及參數(shù)σ的初始值，并根據(jù)[ai=DiT?Si]求得ai的初始解；

（2） 利用牛頓修正法得出[ai=ai+d]，再通過梯度投影過程得到ai的新解，計算對應(yīng)的[Fσai]值，并利用新解求得新余量[r=Si-Di?ai]；

（3） 當(dāng)[r-r02]的值滿足要求時，減小σ的值，進(jìn)入新的迭代，否則在當(dāng)前σ值下繼續(xù)迭代，并使[r0=r]；

（4） 當(dāng)σ值減小到目標(biāo)值時，迭代結(jié)束。使用[Fσai]值最小所對應(yīng)的ai作為最優(yōu)解，并從中抽取出節(jié)點鏈接關(guān)系以構(gòu)建網(wǎng)絡(luò)拓?fù)洹?/p>

3 仿真實驗

實驗平臺為Matlab 7.0。測試的復(fù)雜網(wǎng)絡(luò)為足球聯(lián)盟網(wǎng)絡(luò)，網(wǎng)絡(luò)拓?fù)淙鐖D1所示。該網(wǎng)絡(luò)是Newman 根據(jù)2000年美國秋季足球常規(guī)賽季的比賽情況構(gòu)建的，共包含115個節(jié)點和616 條邊，節(jié)點代表球隊，邊代表兩個球隊間進(jìn)行過比賽，節(jié)點平均度為10.7。

通過編程使各個節(jié)點按費米動力學(xué)規(guī)則與其鄰居進(jìn)行雪堆博弈，以模擬網(wǎng)絡(luò)演化博弈過程，共進(jìn)行60回合，并記錄各節(jié)點每回合的策略和收益信息，即n=115，m=60。在參數(shù)設(shè)置上，b=1.7，c=1.4，κ=0.1，σ=1，r0=0。由于在實際求解中，鄰接矩陣A中的元素不可能精確等于1或0，因此本文實驗中界定當(dāng)元素值在[1±0.1]范圍內(nèi)時表示對應(yīng)節(jié)點間存在鏈接，當(dāng)元素值在[0±0.1]范圍內(nèi)時表示不存在鏈接。

同時為了測試本文算法對博弈時序信息的實際需求量。基于初始時序數(shù)據(jù)，從中隨機抽取不同數(shù)量比例的時序信息分別進(jìn)行網(wǎng)絡(luò)重構(gòu)求解，每個數(shù)據(jù)量下都實驗5次并統(tǒng)計其平均準(zhǔn)確率。

圖2和圖3給出了在不同時序信息量下，所求得網(wǎng)絡(luò)與真實網(wǎng)絡(luò)的連接匹配度。用兩種參數(shù)進(jìn)行評估，分別為節(jié)點間的非空鏈接和空鏈接。圖2中，Exist表示求得與圖1網(wǎng)絡(luò)不一致的鏈接數(shù)同求得鏈接數(shù)的比值，Non?exist表示求得與圖1網(wǎng)絡(luò)不一致的空鏈接數(shù)同求得空鏈接數(shù)的比值。圖3中，Exist表示求得與圖1網(wǎng)絡(luò)一致的鏈接數(shù)同圖1網(wǎng)絡(luò)實際鏈接數(shù)的比值，Non?exist表示求得與圖1網(wǎng)絡(luò)一致的空鏈接數(shù)同圖1網(wǎng)絡(luò)實際空鏈接數(shù)的比值。

從這兩個圖中可以看到，算法只需要使用50%左右的時間序列數(shù)據(jù)量，就可以得出與圖1一致的網(wǎng)絡(luò)拓?fù)洌磳崿F(xiàn)對圖1網(wǎng)絡(luò)的準(zhǔn)確重構(gòu)，這表明了壓縮感知算法在網(wǎng)絡(luò)重構(gòu)應(yīng)用上的有效性。

為了進(jìn)一步測試本文算法（OCS）的求解速度，分別與同類中經(jīng)典的GP，SP，OMP算法進(jìn)行了收斂性能比較，從圖4可看出，OCS的收斂速度要優(yōu)于其他算法，表明基于修正牛頓法的雙曲正切函數(shù)具有更好的L0范數(shù)逼近性能。

4 結(jié) 語

本文基于壓縮感知理論，嘗試?yán)蒙倭繒r間序列信息實現(xiàn)對雪堆博弈復(fù)雜網(wǎng)絡(luò)的重構(gòu)，并利用修正牛頓法對使用的壓縮感知算法進(jìn)行了優(yōu)化，以提高算法的求解性能。未來工作方向是對算法做進(jìn)一步拓展，以期能對其他社會網(wǎng)絡(luò)進(jìn)行有效重構(gòu)。

參考文獻(xiàn)

[1] 榮智海，吳枝喜，王文旭.共演博弈下網(wǎng)絡(luò)合作動力學(xué)研究進(jìn)展[J].電子科技大學(xué)學(xué)報，2013，42（1）：10?22.

[2] 楊涵新，汪秉宏.復(fù)雜網(wǎng)絡(luò)上的演化博弈研究[J].上海理工大學(xué)學(xué)報，2012，34（2）：166?171.

[3] BONGARD J， LIPSON H. Automated reverse engineering of nonlinear dynamical systems [J]. Proc natl acad sci， 2007， 104（24）： 9943?9948.

[4] 吳明輝，許愛強，周小程，等.基于時間序列分析的動調(diào)陀螺儀故障預(yù)測研究[J].計算機測量與控制，2014，22（2）：321?324.

[5] YU D， RIGHERO M， KOCAREV L. Estimating topology of networks [J]. Phys rev letters， 2006， 97（18）： 188701?1?4.

[6] GARDNER T S， d BERNARDO D， LORENZ D， et al. Inferring genetic networks and identifying compound mode of action via expression profiling [J]. Science， 2003， 301（5629）： 102?105.

[7] GEIER F， TIMMER J， FLECK C. Reconstructing gene?regulatory networks from time series， knock?out data， and prior knowledge [J]. BMC Syst Biol， 2007， 1（1）： 11?20.

[8] SUPEKAR K， MENON V， RUBIN D. Network analysis of intrinsic functional brain connectivity in Alzheimer’s disease [J]. PLoS Comput Biol， 2008， 4（6）： e1000100.

[9] WANG W X， LAI Y C， GREBOGI C， et al. Network reconstruction based on evolutionary?game data via compressive sensing [J]. Phys Rev X， 2011， 1（2）： 1?7.

[10] WANG W X， YANG R， LAI Y C， et al. Predicting catastrophes in nonlinear dynamical systems by compressive sensing [J]. Phys Rev Letters， 2011， 106（15）： 1?4.

[11] WANG W X， YANG R， LAI Y C， et al. Time?series based prediction of complex oscillator networks via compressive sensing [J]. EPL， 2011， 94（4）： 1?6.

[12] 邢池強，胡宇翔，蘭巨龍，等.可重構(gòu)安全承載網(wǎng)絡(luò)構(gòu)建與重構(gòu)算法研究[J].計算機應(yīng)用研究，2014，31（4）：1167?1171.

[13] 杜水明，張聰，王贊，等.一種基于VoIP的改進(jìn)WSOLA丟包隱藏算法[J].計算機應(yīng)用與軟件，2014，31（10）：266?268.

[14] 蔡霞，馬社祥，孟鑫.啟發(fā)式重構(gòu)算法在壓縮傳感中的應(yīng)用研究[J].計算機應(yīng)用研究，2012，29（11）：4232?4234.