一種雪堆博弈網絡重構算法研究與仿真

摘 要： 針對演化博弈網絡拓撲難以事先確定的問題，提出一種基于壓縮感知理論的雪堆博弈復雜網絡重構算法。通過個體博弈時序信息將網絡重構問題轉化成壓縮感知理論可以處理的形式，同時運用雙曲正切函數和修正牛頓法對求解過程進行進一步優化，從而實現對網絡拓撲的有效重構，并通過Matlab 7.0作為實驗平臺對算法進行相應的驗證與仿真實驗，實驗結果表明，只需要較少量的時序信息就可以快速準確地完成重構工作。

關鍵詞： 雪堆博弈； 時間序列； 壓縮感知； 修正牛頓法； 復雜網絡

中圖分類號： TN926?34； TP18 文獻標識碼： 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 引 言

作為存在于自然界和人類社會中的普遍現象，個體的演化博弈行為獲得了生物學以及各種社會科學尤其是經濟學學者極大的研究興趣[1]，而針對博弈個體（節點）間存在的錯綜復雜的利益關系，使得復雜網絡理論成為研究相互競爭的自私個體間博弈演化的有力工具[2]。但是在實際網絡研究中，人們往往無法直接或事先獲知所有節點間的鏈接情況（如恐怖組織），即網絡拓撲是未知的，而相對更多的是只能獲得各個節點的相關時序信息。

如何基于個體行為及時序信息重構網絡拓撲已成為近年來復雜網絡研究的熱點問題[3?5]，并已取得了一定成果；如文獻[6?7]利用基因表達數據重構基因調控網絡；文獻[8]利用大腦活動數據提取腦功能網絡等。但是，當前的大部分研究方法或者需要一定的關于目標網絡動力學方程的先驗知識，或者要求節點的時序信息是長時并且連續的[9]。

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

本文以演化博弈中的經典模型——雪堆博弈為研究對象，基于個體在雪堆博弈過程中產生的時序信息，利用壓縮感知方法確定節點間的拓撲關系，并針對傳統壓縮感知算法的運算效率問題，采用修正牛頓法進行優化求解，從而構建出對應的雪堆博弈網絡拓撲。在后面的實驗中可以看到，只需要少量的時序信息，本文方法就可以快速準確地完成對網絡的構建工作。

1 相關背景

1.1 雪堆博弈模型

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

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

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

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

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

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

1.2 壓縮感知

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

式中，[a0]是向量a的L0范數。壓縮感知的優勢在于，當向量a稀疏并且D滿足約束條件時，M可以遠小于N，并且a中非零元素的個數也小于M。

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

2 雪堆博弈網絡重建算法

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

式（5）可以涵蓋節點i與網絡中所有節點（除節點i）進行博弈的所有可能情況。

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

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

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

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

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

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

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

此時經過正定性修正的牛頓方向d為：

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

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

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

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

（3） 當[r-r02]的值滿足要求時，減小σ的值，進入新的迭代，否則在當前σ值下繼續迭代，并使[r0=r]；

（4） 當σ值減小到目標值時，迭代結束。使用[Fσai]值最小所對應的ai作為最優解，并從中抽取出節點鏈接關系以構建網絡拓撲。

3 仿真實驗

實驗平臺為Matlab 7.0。測試的復雜網絡為足球聯盟網絡，網絡拓撲如圖1所示。該網絡是Newman 根據2000年美國秋季足球常規賽季的比賽情況構建的，共包含115個節點和616 條邊，節點代表球隊，邊代表兩個球隊間進行過比賽，節點平均度為10.7。

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

同時為了測試本文算法對博弈時序信息的實際需求量。基于初始時序數據，從中隨機抽取不同數量比例的時序信息分別進行網絡重構求解，每個數據量下都實驗5次并統計其平均準確率。

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

從這兩個圖中可以看到，算法只需要使用50%左右的時間序列數據量，就可以得出與圖1一致的網絡拓撲，即實現對圖1網絡的準確重構，這表明了壓縮感知算法在網絡重構應用上的有效性。

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

4 結 語

本文基于壓縮感知理論，嘗試利用少量時間序列信息實現對雪堆博弈復雜網絡的重構，并利用修正牛頓法對使用的壓縮感知算法進行了優化，以提高算法的求解性能。未來工作方向是對算法做進一步拓展，以期能對其他社會網絡進行有效重構。

參考文獻

[1] 榮智海，吳枝喜，王文旭.共演博弈下網絡合作動力學研究進展[J].電子科技大學學報，2013，42（1）：10?22.

[2] 楊涵新，汪秉宏.復雜網絡上的演化博弈研究[J].上海理工大學學報，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] 吳明輝，許愛強，周小程，等.基于時間序列分析的動調陀螺儀故障預測研究[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] 邢池強，胡宇翔，蘭巨龍，等.可重構安全承載網絡構建與重構算法研究[J].計算機應用研究，2014，31（4）：1167?1171.

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

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