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

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

中圖分類號(hào)： TN926?34； TP18 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

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

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

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

本文以演化博弈中的經(jīng)典模型——雪堆博弈為研究對(duì)象，基于個(gè)體在雪堆博弈過(guò)程中產(chǎn)生的時(shí)序信息，利用壓縮感知方法確定節(jié)點(diǎn)間的拓?fù)潢P(guān)系，并針對(duì)傳統(tǒng)壓縮感知算法的運(yùn)算效率問(wèn)題，采用修正牛頓法進(jìn)行優(yōu)化求解，從而構(gòu)建出對(duì)應(yīng)的雪堆博弈網(wǎng)絡(luò)拓?fù)?。在后面的?shí)驗(yàn)中可以看到，只需要少量的時(shí)序信息，本文方法就可以快速準(zhǔn)確地完成對(duì)網(wǎng)絡(luò)的構(gòu)建工作。

1 相關(guān)背景

1.1 雪堆博弈模型

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

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

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

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

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

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

1.2 壓縮感知

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

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

[2] 楊涵新，汪秉宏.復(fù)雜網(wǎng)絡(luò)上的演化博弈研究[J].上海理工大學(xué)學(xué)報(bào)，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] 吳明輝，許愛(ài)強(qiáng)，周小程，等.基于時(shí)間序列分析的動(dòng)調(diào)陀螺儀故障預(yù)測(cè)研究[J].計(jì)算機(jī)測(cè)量與控制，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] 邢池強(qiáng)，胡宇翔，蘭巨龍，等.可重構(gòu)安全承載網(wǎng)絡(luò)構(gòu)建與重構(gòu)算法研究[J].計(jì)算機(jī)應(yīng)用研究，2014，31（4）：1167?1171.

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

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