基于多層復雜網(wǎng)絡與共演化策略的合作演化的研究

卿倫科

（杭州電子科技大學計算機學院，杭州310018）

0 引言

從圖論發(fā)展而來的復雜網(wǎng)絡科學，一直都被各科學學科作為理論范本，用于建立貼近現(xiàn)實現(xiàn)象的模型。復雜網(wǎng)絡的研究工作主要分為兩類，一類是對網(wǎng)絡上主體之間交互的動力學研究，另一類是對網(wǎng)絡自身拓撲結構的動力學研究。長期以來，演化博弈論用于研究網(wǎng)絡上主體之間交互的動力學，根據(jù)網(wǎng)絡的結構和博弈規(guī)則以及一些改進的策略來研究主體策略的演化過程。現(xiàn)實網(wǎng)絡的結構不斷發(fā)生變化，網(wǎng)絡結構的變化與個體在網(wǎng)絡中演化過程存在著不可忽視的必然聯(lián)系。網(wǎng)絡的共演化策略，結合了網(wǎng)絡的兩種動力學研究工作，用于動態(tài)網(wǎng)絡中合作演化的研究。然而，現(xiàn)有的工作大多針對某一特定的網(wǎng)絡進行單層網(wǎng)絡建模，如在社交網(wǎng)站上分析輿論導向或人物關系，在物理交通網(wǎng)上分析流量和交通部署方案，等等。從經濟、文化到政治，各種相互關聯(lián)的網(wǎng)絡交織在我們每時每刻的生活之中。這些網(wǎng)絡之間看似沒有直接的交互連接，但網(wǎng)絡間的相互影響是潛移默化甚至難以被明顯察覺的。一些非常有價值的研究表明，我們生活在一個充分連接的世界，一些看起來毫不起眼的變化，可能在另一個領域或網(wǎng)絡中引起巨大的變故甚至災難，或者說是出乎人意料的結局。近幾年，國際上提出了“多層復雜網(wǎng)絡”以及“網(wǎng)絡中的網(wǎng)絡”等新興概念模型，成為了復雜網(wǎng)絡領域最前沿的研究方向之一。

針對當前研究的建模過于簡化的問題，本文提出了一種基于多層網(wǎng)絡的網(wǎng)絡共演化策略。由于個體同時身處多個網(wǎng)絡之中，在個體掌握有限的資源（如時間、精力、財富等）的前提下，完全理性個體通常需要對資源進行有效地部署來實現(xiàn)利益最大化。因此該策略使得個體自適應斷邊，回收資源后，在其他某層中隨機連邊，重新部署資源。通過本策略的C++仿真實驗，證明了該策略能有效促進合作的演化。

1 模型

本節(jié)中的多層網(wǎng)絡是由m層相互依賴的單層復雜網(wǎng)絡（ER隨機網(wǎng)絡或BA無標度網(wǎng)絡）排列組合，每層網(wǎng)絡的規(guī)模大小N相同，網(wǎng)絡拓撲結構不同。個體在各層網(wǎng)絡中同時進行同步囚徒困境博弈。每個節(jié)點為一個博弈對象，節(jié)點在各層網(wǎng)絡中與其當層網(wǎng)絡中的鄰居節(jié)點進行博弈。對于一個個體i，用Gk ij=1表示在第k層網(wǎng)絡中交互個體i和交互個體j相連（互為鄰居），反之則值為0。用Sk i(t)=1表示隨時間演化的第t輪中個體i在第k層采取合作策略，值為0則是采取背叛策略，網(wǎng)絡的初始化時，主體有50%的幾率為合作者。與合作者的博弈時，合作者的收益為R=1，背叛者的收益為T=bT=1.5；與背叛者的博弈中，合作者的收益為S=-1，背叛者的收益為P=0，這一博弈矩陣是嚴格的囚徒困境博弈，滿足 T＞R＞P＞S 且 2R＞T+S。根據(jù)此規(guī)則個體i在某一層中與其所有鄰居博弈后得到一個收益值pk i(t)，表示在第t代中個體i在第k層博弈后的收益，個體i在第k輪網(wǎng)絡博弈后得到的總收益定義為：

在多層網(wǎng)絡中，合作者比例cˉ的計算方法為：

每一輪的囚徒困境博弈結束后，對每個個體進行同步的策略更新，和單層網(wǎng)絡中的更新步驟不同的是，對于進行策略更新的主體i，隨機選取其所在的一層網(wǎng)絡l，隨機選取該網(wǎng)絡中的一位鄰居j，主體i在本層中學習其鄰居j的概率用比例學習方程進行計算：

2 共演化規(guī)則

在個體掌握有限的資源（如時間、精力、財富等）的前提下，完全理性個體可通過對資源進行有效部署來實現(xiàn)利益最大化。在種群初始化時，個體在網(wǎng)絡中的度的總和被視為其可支配的資源。每個網(wǎng)絡中的度的大小kl視為其分配在該網(wǎng)絡上的資源的量。設主體的分離系數(shù)為T∈(0 ,1]，值越大表示個體越難以容忍投資收益比較低的網(wǎng)絡，其更傾向于回收在網(wǎng)絡中的資源。通常地，假設復雜網(wǎng)絡中的主體能夠獲取鄰居當前的收益以及其周圍的環(huán)境（即鄰居的鄰居）。在進行一輪的PDG后，主體會根據(jù)自己的收益和投入的資源，找到投資收益比V最小的層，若該值小于的分離系數(shù)，則準備回收一個單元的資源，即斷開一條連接。此時主體會首先遍歷其所有鄰居找到友好度F最低的個體，兩個值的計算方法如下：

約束條件（6）表示客體的博弈環(huán)境很不友好，正在吞噬自己的利益并令人難以忍受；約束條件（7）是防止出現(xiàn)孤立節(jié)點，保證圖的連通性。若資源回收成功，即成功斷開連接，則將回收的資源重新分配給其他層，即建立新連接。個體找到投資收益比最高的層，如果找到了多層，就在這之間隨機選取一層，然后在該層中隨機選取節(jié)點，若選中的節(jié)點是已有連接的鄰居節(jié)點則重新選擇節(jié)點建立連接。

3 實驗結果分析

本策略在多層網(wǎng)絡中的合作演化過程如圖1所示，縱坐標為種群合作者個體比例，橫坐標為演化代數(shù)，紅、藍曲線分別為四層ER、BA網(wǎng)絡中的演化過程。為了驗證策略的有效性，還進行了一組標準對照仿真實驗，讓初始種群在無網(wǎng)絡共演化的靜態(tài)的多層網(wǎng)絡下進行合作演化，如綠色實線所示。較為明顯地，在無策略的多層網(wǎng)絡下，種群的合作個體在前10代迅速從50%下降到20%，進而在一百代左右時，合作者被背叛者全部侵略，主導整個種群。相反地，在采取本節(jié)策略的ER多層網(wǎng)絡（紅色實線）和BA多層網(wǎng)絡（藍色實線）中合作個體比例在前60代左右有持續(xù)下降至40%，但隨著個體的自適應調整，個體將更多的邊分配到收益較好的網(wǎng)絡之中，在任一網(wǎng)絡中，通過自適應調整，合作者抱團，進而逐漸主導種群，大約在200代時合作者比例收斂與65%上下。合作行為不僅得到了保護，還有積極演化趨勢直至最后收斂。我們也同樣驗證了BA網(wǎng)絡-無策略的演化過程，其演化過程與綠線呈相同趨勢，且擬合度較高。由于我們只是為了體現(xiàn)該策略的有效性，為去除重要參數(shù)分離系數(shù)的影響，我們將分離系數(shù)設置為1，即種群中的主體希望自己的每一次投資都得到正收益，保證局部最優(yōu)解。為了進一步理解這一現(xiàn)象，以及兩種不同的網(wǎng)絡拓撲結構對合作產生的影響，我們需要深入分析各參數(shù)與演化過程的關系。

圖1 共演化策略對合作演化的影響

在保證參數(shù)和隨機種子相同的情況下，進行圖1的重復試驗，觀察網(wǎng)絡的不同時期的拓撲結構的動力變化，如圖2所示。由于該實驗在200代時已經趨于收斂狀態(tài)，我們取了1、50、200這三個時間節(jié)點進行描繪。紅色、藍色柱狀圖分別為ER網(wǎng)絡、BA網(wǎng)絡中的度分布圖，由于背叛者侵蝕合作者的利益，其友好值F較低，易被斷邊，而合作者之間相對更易抱團，最后形成“背叛者孤島”。因此，隨著時間推移，即使隨機網(wǎng)絡在初始時，平均度為4×4，服從泊松分布，涌現(xiàn)出大節(jié)點，和無標度特性，其度分布會向著冪律分布的結構演化，逐漸呈現(xiàn)出“長尾狀”。在接近收斂時，兩個網(wǎng)絡的度分布也十分相似。這與大多數(shù)的現(xiàn)實網(wǎng)絡最終趨于冪律分布這一現(xiàn)實規(guī)律相符。

在驗證了本節(jié)策略有利合作演化后，接下來我們研究了實驗的重要參數(shù)——分離系數(shù)T對合作演化的影響，分離系數(shù)T越大意味著主體對投資回報的期待更高，所以更難容忍被低回報投資，在低回報的網(wǎng)絡中更傾向于回收資源。為了排除網(wǎng)絡結構的隨機性影響數(shù)據(jù)樣本，本實驗控制程序的隨機種子保證了網(wǎng)絡的初始狀態(tài)以及主體的初始狀態(tài)都是一樣的。對于網(wǎng)絡結構更復雜的BA網(wǎng)絡而言（如圖3a），不同T的演化趨勢卻較為相似，這意味著網(wǎng)絡的結構演化過程相近。而對于網(wǎng)絡結構相對簡單的ER網(wǎng)絡而言，其在不同T的影響下，演化趨勢擬合度更低，意味著在沒有超大節(jié)點的去中心化的環(huán)境中結構演化過程更加隨機。

總體地，從兩圖的演化規(guī)律來看，隨著T的減小，種群的演化需要更多時間才能收斂。另外，T取最大值時，收斂后合作者比例卻不是最大的，也就是說，在可行的范圍內，對低回報網(wǎng)絡的適當容忍或觀望反而可以促進種群的合作，使得主體得到更多的利益。值得注意的是，BA網(wǎng)絡當T降至0.3時合作演化失敗，而在ER網(wǎng)絡中這一標準是0.2。關系復雜的網(wǎng)絡合作演化的門檻更高，各主體需要有較強的投資回報期待才能抵消部分hub節(jié)點的消極影響。在隨機網(wǎng)絡中，各主體的資源初始時相對均勻，因此促使合作演化的門檻較低。

為了進一步驗證共演化策略的有效性，本文對不同種群大小的多層網(wǎng)絡進行了對照研究。如圖4所示，描繪了基于該策略下不同種群大小的兩種多層上的合作演化圖。其中每個網(wǎng)絡的層數(shù)為m=4，平均度d=4，分離系數(shù)T=0.6。經過試驗分析，總體來看，種群的大小不影響合作的大致演化趨勢。然而，基于BA無標度網(wǎng)絡的多層網(wǎng)絡中，其結構更為復雜，存在少量對網(wǎng)絡影響大的節(jié)點，隨著種群規(guī)模的變大，由于長尾效應，將有更多的度較小的個體加入到網(wǎng)絡中，這些個體手容易受大節(jié)點影響，因此收斂時的回歸值會有輕微的上升；而基于ER隨機網(wǎng)絡的多層網(wǎng)絡中，網(wǎng)絡的結構均勻并附有隨機性，其演化收斂時的結果更多取決于網(wǎng)絡生成時的初始態(tài)及主體的動力過程，因此不受制于種群大小的變化。

圖2 P（D）-Generation度分布隨時間的演化

圖3 分離系數(shù)對合作演化的影響。N=400，d=4，m=4

最后本文研究了多層結構的層變量對演化過程的影響，如圖5所示。實驗結果表明在兩層網(wǎng)絡結構中，層間相互約束的作用相對其他多層網(wǎng)絡較少，沒有明顯優(yōu)于單層網(wǎng)絡。隨著網(wǎng)絡層數(shù)的增加，網(wǎng)絡結構變得更為復雜，合作者抱團難度也隨之增加，收斂的時間成本增加，在二十層時，合作者難以快速抱團，最終合作行為消失。在這之間的范圍內，層數(shù)的變化亦不影響合作演化的最終的收斂結果。

4 結語

本文提出了基于多層網(wǎng)絡的網(wǎng)絡共演化策略，用相互依賴的多層復雜網(wǎng)絡模擬真實環(huán)境中的由多層網(wǎng)絡同步進行演化，相互影響的特征；用自適應斷邊隨機連邊的多層網(wǎng)絡共演化方法模擬真實網(wǎng)絡中，網(wǎng)絡結構不斷發(fā)生變化的特點。通過仿真實驗驗證了該策略的有效性，有助于更深刻地理解合作的涌現(xiàn)。

圖4 種群大小N對合作演化的影響。m=4，d=4，T=0.6

圖5 網(wǎng)絡層數(shù)對合作演化的影響。N=200，d=4，T=0.6