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

卿倫科

（杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院，杭州310018）

0 引言

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

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

1 模型

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

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

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

2 共演化規(guī)則

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

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

3 實(shí)驗(yàn)結(jié)果分析

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

圖1 共演化策略對(duì)合作演化的影響

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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

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