基于分組選擇的可調(diào)聚類網(wǎng)絡(luò)中個體的合作行為研究

鄧云生，張紀會

(青島大學(xué) a.復(fù)雜性科學(xué)研究所;b.山東省工業(yè)控制技術(shù)重點實驗室，山東 青島 266071)

0 引言

自然界和人類社會中的合作現(xiàn)象隨處可見，然而其背后的形成原因卻一直是未解之謎[1]。各領(lǐng)域的學(xué)者從自身專業(yè)的角度對此提出了不同且深刻的見解。在眾多的研究中，值得一提的是Nowak和May[2]將復(fù)雜網(wǎng)絡(luò)模型和博弈論模型相結(jié)合，通過計算機仿真來研究合作問題的形成原因。在他們的研究中用方格網(wǎng)來代表合作個體之間的物理連接，用弱囚徒博弈模型來描述個體之間通過互動而獲得的收益狀況，大量仿真結(jié)果表明，個體傾向于聚集在一起形成合作簇來抵抗背叛策略的入侵。受他們研究的啟發(fā)，大量的研究工作使用這種跨學(xué)科相結(jié)合的方法，研究中使用的網(wǎng)絡(luò)模型也不局限于方格網(wǎng)，進而拓展到BA無標度網(wǎng)絡(luò)[3]、小世界網(wǎng)絡(luò)[4]、關(guān)聯(lián)網(wǎng)絡(luò)[5]，使用的博弈模型不僅有常見的囚徒博弈[6-8]，還包括雪堆博弈[9-11]、獵鹿博弈[12-13]、公共品博弈[14-16]等。

BA網(wǎng)絡(luò)一度被認為是對現(xiàn)實網(wǎng)絡(luò)的真實描述，但隨著研究的深入，卻發(fā)現(xiàn)BA模型雖然能夠描述現(xiàn)實網(wǎng)絡(luò)的“無標度”特性，但卻不能描述現(xiàn)實網(wǎng)絡(luò)的“聚類”特性。為此，Holme等人[17]修改了BA網(wǎng)絡(luò)的生成算法，最終生成同時具有“無標度”和“聚類可調(diào)”特性的網(wǎng)絡(luò)。在此網(wǎng)絡(luò)基礎(chǔ)上，一些對演化合作行為的研究得以展開[18-20]。Assenza等人[18]發(fā)現(xiàn)，改進后的網(wǎng)絡(luò)的高聚類特性有助于促進網(wǎng)絡(luò)中個體合作行為的涌現(xiàn)。Rong等人[19]研究了可調(diào)聚類網(wǎng)絡(luò)上的公共品博弈，發(fā)現(xiàn)網(wǎng)絡(luò)中存在的三角結(jié)構(gòu)反饋機制在促進合作中的關(guān)鍵作用。Wang等人[20]進一步改進了可調(diào)聚類網(wǎng)絡(luò)，修改后的網(wǎng)絡(luò)模型能夠更準確地反映現(xiàn)實社會中的合作關(guān)系。

在上述研究的基礎(chǔ)上，本文研究了可調(diào)聚類網(wǎng)絡(luò)中囚徒博弈困境下的合作問題。通過引入一個可調(diào)節(jié)參數(shù)對博弈個體的鄰居節(jié)點進行分組，并賦予博弈個體一定長度的記憶。個體通過對特定分組中的鄰居的學(xué)習(xí)，最終可以提高網(wǎng)絡(luò)的整體合作水平。

1 可調(diào)聚類網(wǎng)絡(luò)與博弈個體互動規(guī)則

1.1 可調(diào)聚類網(wǎng)絡(luò)

網(wǎng)絡(luò)的平均聚類系數(shù)反映了網(wǎng)絡(luò)中節(jié)點聚集的程度，其定義為

(1)

圖1 可調(diào)聚類網(wǎng)絡(luò)平均聚類系數(shù)變化Fig.1 Variation of average clustering coefficient of adjustable clustering networks

圖1所示的網(wǎng)絡(luò)初始時有2個相互連接的節(jié)點，網(wǎng)絡(luò)中每加入一個新節(jié)點都會在網(wǎng)絡(luò)中增加2個鏈接，直至達到網(wǎng)絡(luò)規(guī)模N=5 000為止。在概率Pt從0增加到1的過程中，網(wǎng)絡(luò)的度分布仍然服從冪律分布，但其平均聚類系數(shù)CC隨Pt的增大而增大，故可以直接使用Pt值來代表不同平均聚類水平的網(wǎng)絡(luò)。

1.2 個體互動規(guī)則

網(wǎng)絡(luò)中持有合作策略(Cooperation,C)的節(jié)點稱為合作者(cooperator)，持有背叛策略(Defection,D)的節(jié)點稱為背叛者(defector)。持有不同策略的節(jié)點互動時根據(jù)囚徒博弈(Prisoner′s Dilemma Game,PDG)所描述的收益矩陣獲得相應(yīng)的收益。本文使用文獻[2]所描述的弱囚徒博弈收益矩陣：

CD

(2)

當(dāng)兩個合作者互動時，每位合作者獲得收益R=1；兩個背叛者互動時，每位背叛者獲得收益P=0；當(dāng)合作者與背叛者互動時，合作者獲得收益S=0，背叛者獲得收益T=b；其中b>1。

在傳統(tǒng)的網(wǎng)絡(luò)節(jié)點博弈過程中，每一個節(jié)點在修改自己的策略之前，通常要選擇一個學(xué)習(xí)的目標，然后再通過一定的概率(例如費米函數(shù)、比例函數(shù)等)來判斷是否學(xué)習(xí)該目標的策略。節(jié)點通常采用隨機挑選的方式從自己的鄰居中選擇學(xué)習(xí)目標，這種方式雖然簡單，但卻忽略了個體在選擇過程中的主觀能動性?，F(xiàn)實中個體在挑選學(xué)習(xí)目標時往往帶有特定的指向，而非無目的地隨機挑選，被選中的學(xué)習(xí)目標往往具有能夠滿足挑選者需要的某種特質(zhì)?；谝陨嫌^察，提出一種分組選擇的方法進行學(xué)習(xí)目標的選擇。

假設(shè)網(wǎng)絡(luò)中每一個節(jié)點能夠記憶M輪博弈過程中所使用的策略和獲得的收益，則對于網(wǎng)絡(luò)中度值為k的節(jié)點x，在M輪博弈過程中每一份鏈接給節(jié)點x帶來的平均收益定義為

(3)

(4)

其中，κ=0.1代表系統(tǒng)的噪聲和不確定性。一旦i確定向節(jié)點j學(xué)習(xí)，節(jié)點i可直接模仿節(jié)點j在最近一輪博弈中所使用的策略[11-15]，或綜合考慮各種因素(例如：記憶、情緒、收益等等)做出策略選擇[7,21-22]。我們并不使用直接模仿的策略，而是綜合考慮節(jié)點j在過去M輪博弈中所使用的策略和收益而做出決策。節(jié)點i所采取的策略S定義為

(5)

2 仿真分析

2.1 預(yù)期最小收益對可調(diào)聚類網(wǎng)絡(luò)中合作行為的影響

所有仿真實驗中，網(wǎng)絡(luò)規(guī)模N=5 000，初始時刻合作策略與背叛策略以相同的數(shù)量隨機均勻分布在網(wǎng)絡(luò)中，即此時合作密度fc=0.5。每一次實驗都進行10 000步仿真，同時為了避免隨機性帶來的影響，仿真圖中所呈現(xiàn)的每一組數(shù)據(jù)都是50次獨立實驗后取平均值的結(jié)果。

首先考查用于分組的參數(shù)emp對可調(diào)聚類網(wǎng)絡(luò)中節(jié)點合作行為的影響，仿真結(jié)果如圖2所示。

圖2 emp對不同聚類水平網(wǎng)絡(luò)合作密度的影響Fig.2 The effect of emp on the cooperation densities of networks with different clustering levels

圖2所示實驗在M=7，b=1.1的4組不同聚類水平的網(wǎng)絡(luò)上進行，其中參數(shù)emp從0.3變化到1.2。由圖2可看出，不同聚類水平的網(wǎng)絡(luò)的合作密度fc隨著參數(shù)emp的增大呈現(xiàn)出相似的變化規(guī)律。以Pt=0.6為例，當(dāng)emp在區(qū)間[0.3,0.6]內(nèi)單調(diào)遞增時，fc隨之單調(diào)遞增，一旦emp值超過0.6，其對應(yīng)的fc急劇下降到低于初始合作值0.5的程度。隨著emp的繼續(xù)增大，fc的值有所上升，但仍然低于初始值0.5，最終當(dāng)emp≥1.1時，fc等于初始值0.5。究其原因，可以發(fā)現(xiàn)隨著emp的增加，高收益群組的范圍在不斷縮小，即|Ω|的值隨emp增加而減小，因為在囚徒博弈中相比于合作策略，背叛策略能帶來更大的收益(T>R)，當(dāng)emp低于0.6時挑選到因合作策略而得到高收益的節(jié)點的可能性較大，當(dāng)emp高于0.6時，高收益組中的節(jié)點很可能都是因背叛策略而獲得高收益，此時從中挑選學(xué)習(xí)目標并向其學(xué)習(xí)，往往學(xué)習(xí)的是背叛策略，從而導(dǎo)致整體合作率下降。隨著emp不斷增大，|Ω|不斷變小，直至emp≥1.1時，|Ω|=0，此時高收益組中沒有任何節(jié)點，因此，也不會有節(jié)點被選為學(xué)習(xí)目標，按照節(jié)點的互動規(guī)則，此時，網(wǎng)絡(luò)中的每一個節(jié)點保持初始策略不變，故整體的合作密度fc也維持在初始狀態(tài)0.5不發(fā)生變化。

當(dāng)emp處于促進合作行為的區(qū)間[0.3,0.6]內(nèi)時，不同聚類水平的網(wǎng)絡(luò)最終的合作者密度fc也是不相同的。在相同的emp下，聚類水平高(Pt值大)的網(wǎng)絡(luò)中的合作者密度要高于聚類水平低(Pt值小)的網(wǎng)絡(luò)中的合作者密度，充分體現(xiàn)了無標度網(wǎng)絡(luò)的高聚類特性對群體合作行為的促進作用。而在emp>0.6時，不同聚類水平的網(wǎng)絡(luò)其合作者密度都是大幅度下降的，而且此時在相同的emp下，不同網(wǎng)絡(luò)的合作密度在數(shù)值上非常接近并無明顯差異，這說明此時無標度網(wǎng)絡(luò)的高聚類特性并沒有發(fā)揮對合作行為的促進作用，這與以往研究的結(jié)論[18]是不同的。

2.2 個體記憶長度與聚類性對網(wǎng)絡(luò)中合作行為的影響

由個體的互動規(guī)則可知，參數(shù)emp和M共同對合作密度產(chǎn)生影響，接下來固定emp的值，考察另一個重要參數(shù)M對群體合作行為的影響。令emp=0.5，b=1.1，不同聚類水平網(wǎng)絡(luò)上的仿真結(jié)果如圖3所示。

圖3 記憶長度對不同聚類水平網(wǎng)絡(luò)合作密度的影響Fig.3 The effect of memory length on the cooperation densities of networks with different clustering levels

圖3中，emp=0.5處于促進合作行為的區(qū)間[0.3,0.6]，個體記憶長度M從2變化到20。在不同聚類水平的網(wǎng)絡(luò)中，合作密度隨著M增加呈現(xiàn)出相似的演化規(guī)律：從低到高然后再轉(zhuǎn)低，這也意味著個體的記憶長度的增加對合作行為的影響先是促進然后轉(zhuǎn)為抑制。這種先促進后抑制的演化規(guī)律說明，在給定的條件下，存在一個與M相關(guān)的點或區(qū)間，當(dāng)M在該點取值或該區(qū)間內(nèi)取值時，其所在網(wǎng)絡(luò)的合作密度將達到最大值。由圖3可以發(fā)現(xiàn)：當(dāng)Pt=0.2,0.4,0.6時，M=3可以使對應(yīng)的網(wǎng)絡(luò)合作密度達到最大值；而當(dāng)Pt=0.8,1.0時，M=4可以使對應(yīng)的網(wǎng)絡(luò)合作密度達到最大值。從圖3還可以發(fā)現(xiàn)：在不同聚類水平的網(wǎng)絡(luò)上，短期記憶(3≤M≤6)比長期記憶更有利于合作密度的提高。

此外，網(wǎng)絡(luò)的高聚類特性對合作行為的促進作用也可以從圖3中觀察到。對于相同的M，聚類水平高的網(wǎng)絡(luò)對應(yīng)的合作密度高于聚類水平低的網(wǎng)絡(luò)所對應(yīng)的合作密度，這是因為在高聚類的網(wǎng)絡(luò)中會存在一種具有極高連接度的節(jié)點(也稱為hub節(jié)點)，而這些hub節(jié)點會因為累積收益的計算方式而傾向于采用合作策略[18]。一旦這些hub節(jié)點成為合作者，因為與其連接的節(jié)點眾多，這些節(jié)點必然受到hub節(jié)點的影響而模仿其合作策略，最終會導(dǎo)致大量合作策略在網(wǎng)絡(luò)中傳播。圖4進一步展示了高聚類特性對hub節(jié)點策略行為的影響。

由圖4可以看出，不同聚類水平的網(wǎng)絡(luò)中，k值較小(k<18)的節(jié)點中合作者與背叛者并存，而k值較大(k>70)的hub節(jié)點中只有合作者的存在，進一步說明hub節(jié)點往往采用合作策略，成為合作者。在同一聚類水平的網(wǎng)絡(luò)中，這種“合作者高收益”的hub節(jié)點又會對周圍大量圍繞的相鄰節(jié)點產(chǎn)生一種榜樣示范效應(yīng)，促使其模仿hub節(jié)點的合作策略以爭取獲得高收益。這些hub節(jié)點的度值越大，影響到的相鄰節(jié)點也越多，其榜樣示范效應(yīng)也越強，一旦其相鄰節(jié)點轉(zhuǎn)變?yōu)楹献髡?，又能給與它相連的hub節(jié)點提供更多的收益。hub節(jié)點與其相鄰節(jié)點之間形成一種正向反饋的互動模式，所以，這些hub節(jié)點的收益整體呈現(xiàn)出一種隨連接度增大而增加的趨勢(見圖4b或4d)。

這種hub節(jié)點與網(wǎng)絡(luò)生成算法中的參數(shù)Pt有關(guān)，Pt值越大會導(dǎo)致其生成的網(wǎng)絡(luò)中高連接度的hub節(jié)點的度值越大，例如圖4b中，Pt=0.2時生成的網(wǎng)絡(luò)中最大度值的hub節(jié)點度為153，收益為131，而在圖4d中，Pt=0.7時生成的網(wǎng)絡(luò)中最大度值的hub節(jié)點度值為162，收益為139。此外，Pt值的大小也代表著網(wǎng)絡(luò)的聚類水平的高低。由上述分析可知，網(wǎng)絡(luò)的聚類性越高對合作行為的促進作用也越大。

圖4 連接度為k的節(jié)點數(shù)量及其收益Fig.4 The number of nodes with connection degree k and their payoffs

2.3 互動規(guī)則的應(yīng)用擴展

以上研究中，我們將個體互動規(guī)則應(yīng)用在聚類可調(diào)網(wǎng)絡(luò)中，探討了參數(shù)emp和M對高聚類網(wǎng)絡(luò)中合作行為的影響。本節(jié)，我們改變底層的網(wǎng)絡(luò)結(jié)構(gòu)，將個體的互動規(guī)則應(yīng)用在方格網(wǎng)和小世界網(wǎng)絡(luò)上，探討其合作行為演化過程，仿真結(jié)果如圖5所示。

圖5 emp對方格網(wǎng)和小世界網(wǎng)中合作行為的影響Fig.5 The impact of emp on cooperative behavior in Lattice and small-world networks

圖5a所示的仿真實驗是在規(guī)模為N=50×50的方格網(wǎng)上進行的，圖5b是在規(guī)模為N=2 500的小世界網(wǎng)絡(luò)[4]上進行的，小世界網(wǎng)絡(luò)中節(jié)點間的重連概率為0.01。個體互動過程中使用公式(2)所示的弱囚徒博弈，b=1.1，博弈個體的記憶長度M=10，每次實驗過程經(jīng)歷了10 000步仿真，每組數(shù)據(jù)是50次獨立實驗后取平均值的結(jié)果。為清晰展示合作率的演化過程，圖5中的橫坐標為對數(shù)坐標。

3 結(jié)論

論文研究了網(wǎng)絡(luò)的聚類性(Pt)、用于分組的最小期望收益值(emp)和博弈個體的記憶長度(M)三者對網(wǎng)絡(luò)合作行為的影響。研究發(fā)現(xiàn)，存在一個與emp相關(guān)的區(qū)間(例如，0.3≤emp≤0.5，見圖2)，在此區(qū)間內(nèi)emp與Pt具有促進合作策略傳播的作用。同時，較小的記憶長度M(例如，2≤M≤6，見圖3)有利于促進合作行為的形成。這些結(jié)果說明對于一個給定的聚類可調(diào)網(wǎng)絡(luò)，只需要指定emp與M的值，就可以使合作策略在網(wǎng)絡(luò)中傳播的效率達最大化，為我們促進網(wǎng)絡(luò)中合作行為的傳播提供了一種新方法。