囚徒困境博弈策略在社團(tuán)網(wǎng)絡(luò)中的演化

陳雅姍，郭文忠

(1．福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建福州 350116;2．福州大學(xué)至誠(chéng)學(xué)院，福建福州 350002)

0 引言

無論是自然界還是人類社會(huì)，合作現(xiàn)象都是普遍存在的［1］．但是根據(jù)自然選擇的適者生存進(jìn)化原理，生物個(gè)體是自私自利、追求利益最大化的，這將導(dǎo)致個(gè)體之間相互背叛，那么自然界中的合作現(xiàn)象是如何存在的?科學(xué)家們將進(jìn)化博弈論與復(fù)雜網(wǎng)絡(luò)相結(jié)合，深入探究合作行為的產(chǎn)生機(jī)理及演化情況．復(fù)雜網(wǎng)絡(luò)是近年來興起的一門交叉學(xué)科，可以準(zhǔn)確描述許多自然界和社會(huì)中的系統(tǒng)，并已引起國(guó)內(nèi)外專家學(xué)者們的研究興趣，取得一定的研究成果［2－4］．但其平均路徑卻比較長(zhǎng);小世界網(wǎng)絡(luò)雖然兼具小的平均路徑和高聚類特性，但其度分布卻不服從冪律分布．1999年Barabási和Albert在總結(jié)這些網(wǎng)絡(luò)模型缺陷的基礎(chǔ)上，構(gòu)建了度分布服從冪律分布的無標(biāo)度網(wǎng)絡(luò)模型［5］(BA模型)，此模型能更好地刻畫實(shí)際網(wǎng)絡(luò)，因此在之后的復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域里，無標(biāo)度網(wǎng)絡(luò)占據(jù)了主導(dǎo)地位．

近年來大量的研究表明許多真實(shí)網(wǎng)絡(luò)都有一個(gè)相同的特征——社團(tuán)結(jié)構(gòu)，而BA模型無此特性．社團(tuán)結(jié)構(gòu)就是一個(gè)大網(wǎng)絡(luò)由多個(gè)小的“群”或者“社團(tuán)”所組成，同一個(gè)“群”內(nèi)的節(jié)點(diǎn)連接緊密，不同“群”之間的節(jié)點(diǎn)連接稀少［6］．社團(tuán)結(jié)構(gòu)在真實(shí)系統(tǒng)中代表著不同的含義:在社交網(wǎng)中，不同“群”代表著不同的領(lǐng)域、職業(yè)、年紀(jì)等［7］;在引文網(wǎng)中，不同“群”體現(xiàn)了不同的研究領(lǐng)域［8］．基于此，有專家提出了兼具無標(biāo)度和社團(tuán)結(jié)構(gòu)特性的社團(tuán)網(wǎng)絡(luò)［9－10］．

目前關(guān)于社團(tuán)網(wǎng)絡(luò)的研究工作還比較少，本文基于社團(tuán)網(wǎng)絡(luò)，采用“囚徒困境”模型來模擬個(gè)體之間的合作演化情況，重點(diǎn)在于討論社團(tuán)網(wǎng)絡(luò)中，具有什么特點(diǎn)的網(wǎng)絡(luò)拓?fù)湫再|(zhì)能更好地促進(jìn)合作的涌現(xiàn)和維持，并深入探討這些網(wǎng)絡(luò)拓?fù)洵h(huán)境促進(jìn)合作產(chǎn)生的內(nèi)在機(jī)制．

1 模擬方法

1．1 網(wǎng)絡(luò)模型

首先生成一個(gè)網(wǎng)絡(luò)規(guī)模為N且具有社團(tuán)結(jié)構(gòu)的無標(biāo)度網(wǎng)絡(luò)［10］:先形成G(G≥2)個(gè)社團(tuán)，每一個(gè)社團(tuán)都包含m0(m0＞1)個(gè)節(jié)點(diǎn)．讓初始的m0×G個(gè)節(jié)點(diǎn)彼此相互連接，在之后的每一時(shí)間步長(zhǎng)里，每個(gè)社團(tuán)都添加一個(gè)新節(jié)點(diǎn)和m條邊(m＜m0，且網(wǎng)絡(luò)平均度=2m)．先指定其中的n條邊連接到同一個(gè)社團(tuán)里(0≤n≤m)，剩下的m－n條邊連接到隨機(jī)選取的其它社團(tuán)中．所有邊的連接都按照BA無標(biāo)度網(wǎng)絡(luò)的度優(yōu)先連接原則．定義了社團(tuán)強(qiáng)度Q，它體現(xiàn)同一社團(tuán)內(nèi)部節(jié)點(diǎn)相互之間連接的緊密程度．其中Q與m和n具有簡(jiǎn)潔的關(guān)系形式:

1．2 “囚徒困境”模型

囚徒困境是博弈論中的經(jīng)典模型．在該模型中，兩個(gè)個(gè)體同時(shí)決定背叛或者合作，如果甲選擇背叛而乙選擇合作，那么甲得到的收益為T，而乙將獲得收益為S;反之亦然，如果雙方都合作獲得R收益，都背叛獲得P收益．該模型中T＞R＞S＞P，2R＞S+T［4］．顯而易見，無論乙采用何種策略，甲認(rèn)為采用背叛總是對(duì)本身最有利，相同的邏輯對(duì)對(duì)方同樣適用．根據(jù)適者生存進(jìn)化原理，這將導(dǎo)致個(gè)體之間相互背叛，但是在自然界合作現(xiàn)象仍普遍存在，生物個(gè)體似乎可以克服自身的私利，采取有利于所有個(gè)體的策略．

1．3 演化規(guī)則及參數(shù)設(shè)置

參考傳統(tǒng)演化過程模擬的參數(shù)設(shè)置，具體參數(shù)取值為:R=1，T=b=1～2，P=S=0，N=10000，G=10，m=4，0≤n≤m，m0=5．網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)代表參與博弈的每個(gè)個(gè)體，個(gè)體間如果發(fā)生交互關(guān)系就連接該兩節(jié)點(diǎn)．初始化網(wǎng)絡(luò)時(shí)，各節(jié)點(diǎn)合作和背叛策略的分布概率相同．為降低漲落引起的誤差，每次的模擬都是先演化30 000代，再對(duì)之后的2 000代取平均，并模擬50次，最后對(duì)所得的50次結(jié)果進(jìn)行平均處理．模擬過程進(jìn)行的是同步演化規(guī)則，每一代的演化都包括如下兩過程:

1)個(gè)體都與自身的所有鄰居產(chǎn)生博弈，并獲得收益值．令si代表個(gè)體i所選擇的策略，其取值為:

和所有鄰居產(chǎn)生博弈時(shí)，個(gè)體i都選擇同一種策略，可得到經(jīng)過每一代博弈后個(gè)體i的總收益值為:

其中:fi表示在博弈時(shí)個(gè)體i的鄰居中采取合作策略的個(gè)體數(shù)目;ki表示個(gè)體i的度，即個(gè)體i有ki個(gè)鄰居．

2)當(dāng)個(gè)體i要更新策略時(shí)，從ki個(gè)鄰居中隨機(jī)選取鄰居j，當(dāng)Ei＜Ej時(shí)，在下一代個(gè)體i將以概率

采取鄰居j的策略．其中k＞取ki和kj的較大者［11］．

為了定量分析合作行為的變化趨勢(shì)，引入群體合作頻率ρc，其定義為在進(jìn)化博弈進(jìn)入穩(wěn)定狀態(tài)后，合作個(gè)體占總?cè)后w數(shù)目的比例．

2 模擬結(jié)果及討論

2．1 社團(tuán)強(qiáng)度對(duì)合作演化的影響

不同社團(tuán)強(qiáng)度對(duì)合作演化情況的影響如圖1所示．由圖1(a)可見，與BA無標(biāo)度網(wǎng)絡(luò)相比，具有社團(tuán)結(jié)構(gòu)的無標(biāo)度網(wǎng)絡(luò)更能促進(jìn)合作行為的產(chǎn)生．同時(shí)，社團(tuán)強(qiáng)度Q值的大小明顯影響了群體的合作情況．當(dāng)Q為0．9時(shí)，一直都保持著較高的合作率，而當(dāng)Q為0．3時(shí)的合作情況卻不如Q為0．1時(shí)的情況，因此本文固定了背叛誘惑b值的大小，考察群體合作頻率隨Q的變化關(guān)系．圖1(b)是網(wǎng)絡(luò)平均度=8，背叛誘惑b=1．8時(shí)，群體合作率隨Q的變化曲線．圖示表明，合作率并不隨Q的改變成線性關(guān)系，而是當(dāng)Q較小或較大時(shí)，有利于合作的產(chǎn)生，當(dāng)Q在0．5左右時(shí)，大大降低了系統(tǒng)的合作率．為了更詳盡地探究不同社團(tuán)強(qiáng)度的網(wǎng)絡(luò)拓?fù)洵h(huán)境如何影響系統(tǒng)合作的演化，本文考量了網(wǎng)絡(luò)的另一個(gè)重要指標(biāo):聚類系數(shù)C．

圖1 社團(tuán)強(qiáng)度對(duì)合作演化的影響Fig．1 Community strength influences the evolution of cooperation

2．2 網(wǎng)絡(luò)聚類系數(shù)對(duì)合作演化的影響

網(wǎng)絡(luò)聚類系數(shù)隨社團(tuán)強(qiáng)度的變化情況如圖2(a)所示，曲線趨勢(shì)與圖1(b)相似，即Q較大或較小時(shí)，網(wǎng)絡(luò)具有較大聚類系數(shù)，當(dāng)Q為0．5左右時(shí)，聚類系數(shù)較小．聚類系數(shù)的其中一種定義為:C=(3×三角形數(shù)目)角形數(shù)目 (5)其中:角形是一個(gè)節(jié)點(diǎn)與另外兩個(gè)節(jié)點(diǎn)相連形成的夾角形狀．當(dāng)Q在0．5左右時(shí)，表示剛產(chǎn)生的新節(jié)點(diǎn)所引入的m條邊中，有一半是與節(jié)點(diǎn)所在的社團(tuán)成員連接，另一半則與其他社團(tuán)的成員連接，如此引進(jìn)的m條邊很難為網(wǎng)絡(luò)增加新的三角形;而當(dāng)引進(jìn)的m條邊都與節(jié)點(diǎn)所在的社團(tuán)成員連接，或者只與其他社團(tuán)成員連接時(shí)，將有利于新三角形的形成，也將提高網(wǎng)絡(luò)的聚類系數(shù)．三角形是最穩(wěn)定的幾何結(jié)構(gòu)單元，從公式(3)可知，當(dāng)構(gòu)成三角形的三個(gè)節(jié)點(diǎn)都是合作者時(shí)，它們彼此的收益達(dá)到最大，處于相對(duì)穩(wěn)定狀態(tài)，并將慢慢形成一棵越來越大越緊密的穩(wěn)定合作樹，共同抵制背叛者入侵;而當(dāng)三個(gè)節(jié)點(diǎn)都是背叛者時(shí)，它們自身的收益降到最低，此時(shí)背叛者難以生存，很快又采取合作策略．無標(biāo)度網(wǎng)絡(luò)雖然具有度冪律分布的特點(diǎn)，但其網(wǎng)絡(luò)聚類系數(shù)卻接近于零，事實(shí)上，大量現(xiàn)實(shí)網(wǎng)絡(luò)(如社會(huì)關(guān)系網(wǎng)絡(luò))都有較高的聚類系數(shù)．此屬性較易理解，比如，一個(gè)成員的朋友關(guān)系網(wǎng)絡(luò)中，他的朋友彼此之間也比較容易認(rèn)識(shí)而成為朋友．

圖2 網(wǎng)絡(luò)聚類系數(shù)對(duì)合作演化的影響Fig．2 Clustering coefficient influences the evolution of cooperation．

為了更接近真實(shí)網(wǎng)絡(luò)，本文按照文獻(xiàn)［12］構(gòu)建網(wǎng)絡(luò)的方法，生成了能調(diào)節(jié)聚類系數(shù)的社團(tuán)網(wǎng)絡(luò)．具體的網(wǎng)絡(luò)生長(zhǎng)過程如下:引入一個(gè)新節(jié)點(diǎn)i，在完成一次優(yōu)先連接后以幾率POT(probability of triangle formation)組成一個(gè)三角連接，再以幾率1－POT完成優(yōu)先連接，直到連完m條邊，繼續(xù)重復(fù)此過程引入另一新節(jié)點(diǎn)，直到生成一個(gè)節(jié)點(diǎn)數(shù)目為N的網(wǎng)絡(luò)．可見，能夠通過調(diào)節(jié)POT概率來改變網(wǎng)絡(luò)聚類系數(shù)．圖2(b)是三種不同C的社團(tuán)網(wǎng)絡(luò)中，群體合作率ρc與背叛誘惑b值的關(guān)系圖，網(wǎng)絡(luò)的社團(tuán)強(qiáng)度固定為0．9．由圖可見:具有較大聚類系數(shù)C的網(wǎng)絡(luò)，更能促進(jìn)群體合作行為的涌現(xiàn)．

2．3 網(wǎng)絡(luò)平均度對(duì)合作演化的影響

度是復(fù)雜網(wǎng)絡(luò)研究當(dāng)中的一個(gè)重要指標(biāo)，網(wǎng)絡(luò)中一般用ki表示節(jié)點(diǎn)i的度，即節(jié)點(diǎn)i與ki個(gè)鄰居節(jié)點(diǎn)有直接的連線，網(wǎng)絡(luò)平均度即為每一個(gè)節(jié)點(diǎn)度的平均值，一般用表示．圖3是具有相同社團(tuán)強(qiáng)度，卻有不同平均度的社團(tuán)網(wǎng)絡(luò)中系統(tǒng)合作率ρc與背叛誘惑b值的關(guān)系圖．由圖3可見，在社團(tuán)網(wǎng)絡(luò)中，平均度越大，反而阻礙了群體合作行為的出現(xiàn)．主要是因?yàn)榫W(wǎng)絡(luò)中的“中樞節(jié)點(diǎn)”(“中樞節(jié)點(diǎn)”指網(wǎng)絡(luò)中度比較大的節(jié)點(diǎn))之間的直接連線能提高系統(tǒng)合作率［13］．當(dāng)網(wǎng)絡(luò)平均度較小時(shí)，“中樞節(jié)點(diǎn)”的地位相對(duì)穩(wěn)固，“中樞節(jié)點(diǎn)”之間的連線比例較高．隨著平均度增加，將有更多的“老節(jié)點(diǎn)”(“老節(jié)點(diǎn)”指生成網(wǎng)絡(luò)時(shí)較先引入的節(jié)點(diǎn))開始加入“中樞節(jié)點(diǎn)”行列，并且在網(wǎng)絡(luò)生成過程中，這些“老節(jié)點(diǎn)”之間沒有連線，之后的演化中也無法再相互連線，必將降低“中樞節(jié)點(diǎn)”之間直接連線的比例，因此導(dǎo)致了網(wǎng)絡(luò)平均度越大反而降低了群體合作率．

圖3 不同平均度下ρc隨b的變化Fig．3 ρc vsbon different values of k

3 結(jié)論

將囚徒困境博弈策略與社團(tuán)網(wǎng)絡(luò)相結(jié)合，探討社團(tuán)網(wǎng)絡(luò)的拓?fù)洵h(huán)境怎樣影響群體合作行為的演化．計(jì)算機(jī)模擬結(jié)果顯示，社團(tuán)強(qiáng)度Q明顯影響了群體的合作情況，Q較小或較大時(shí)都能激勵(lì)合作行為的涌現(xiàn)，維護(hù)合作現(xiàn)象的持續(xù)，當(dāng)Q為0．5左右時(shí)，系統(tǒng)合作率明顯降低;系統(tǒng)合作行為在不同聚類系數(shù)的社團(tuán)網(wǎng)絡(luò)中演化情況不同，有明顯聚類效應(yīng)的網(wǎng)絡(luò)更有利于合作行為的演化;當(dāng)網(wǎng)絡(luò)平均度增大時(shí)，反而阻礙了合作行為的出現(xiàn)．

［1］Gintis H．Game theory evolving［M］．Princeton:Princeton University，2000．

［2］Hu Cheng，Yu Juan，Jiang Haijun，et al．Synchronization of complex community networks with nonidentical nodes and adaptive coupling strength［J］．Physics Letters A，2011，375(5):873 －879．

［3］榮智海，吳枝喜，王文旭．共演博弈下網(wǎng)絡(luò)合作動(dòng)力學(xué)研究進(jìn)展［J］．電子科技大學(xué)學(xué)報(bào)，2013，42(1):10－19．

［4］陳雅姍．影響力異質(zhì)性影響群體合作的演化［J］．福州大學(xué)學(xué)報(bào):自然科學(xué)版，2010，38(5):653－656．

［5］Barabási A L，Albert R．Emergence of scaling in random networks［J］．Science，1999，286(5 439):509 －512．

［6］Kim Y，Son SW，Jeong H．Link rank:finding communities in directed networks［J］．Physical Review E，2010，81(1):95－102．

［7］李曉佳，張鵬，狄增如，等．復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)［J］．復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2008，5(3):20－40．

［8］張聰，沈惠璋．網(wǎng)絡(luò)自然密度社團(tuán)結(jié)構(gòu)模塊度函數(shù)［J］．電子科技大學(xué)學(xué)報(bào)，2012，41(2):185－191．

［9］Kashtan N，Alon U．Spontaneous evolution of modularity and network motif［J］．Proceedings of the National Academy of Sciences of the United States of America，2005，102(39):13 773－13 778．

［10］鄧智龍，淦文燕．復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)方法［J］．計(jì)算機(jī)科學(xué):2012，39(6A):103－108．

［11］Santos F C，Pacheco J M．Scale－free networks provide a unifying framework for the emergence of cooperation［J］．Physical Review Letters，2005，95(9):98－104．

［12］Holme P，Kim B J．Growing scale－free networks with tunable clustering［J］．Physical Review E，2002，65(2):1 －4．

［13］Chen Yashan，Lin Hai，Wu Chenxu．Evolution of prisoner＇s dilemma strategies on scale － free networks［J］．Physica A －Statistical Mechanics and its Applications，2007，385:379－384．