一種高聚類冪律可調(diào)網(wǎng)絡(luò)異質(zhì)配置模式下的公共品博弈研究

苗 萍，楊洪勇

(魯東大學(xué)信息與電氣工程學(xué)院，山東 煙臺(tái) 264025)

一種高聚類冪律可調(diào)網(wǎng)絡(luò)異質(zhì)配置模式下的公共品博弈研究

苗 萍，楊洪勇

(魯東大學(xué)信息與電氣工程學(xué)院，山東 煙臺(tái) 264025)

為了研究網(wǎng)絡(luò)結(jié)構(gòu)與演化博弈之間的關(guān)系，提出了一種基于網(wǎng)絡(luò)內(nèi)部“三角結(jié)構(gòu)”與“內(nèi)部演化”演化機(jī)制的高聚類冪律可調(diào)的網(wǎng)絡(luò)模型。該網(wǎng)絡(luò)模型具有無(wú)標(biāo)度網(wǎng)絡(luò)冪律分布的特性，且具有更高的聚類系數(shù)。在該網(wǎng)絡(luò)模型的基礎(chǔ)上，研究了異質(zhì)配置模式的公共品博弈，即根據(jù)網(wǎng)絡(luò)中的節(jié)點(diǎn)與其一層鄰居和二層鄰居中合作者數(shù)目的多少來(lái)決定公共品博弈中合作者的投入差異，并通過(guò)一個(gè)調(diào)節(jié)因子來(lái)調(diào)節(jié)投入差異的異質(zhì)性程度。最后仿真證明，該異質(zhì)配置模式演化博弈模型在高聚類冪律可調(diào)網(wǎng)絡(luò)模型上可以快速達(dá)到納什均衡，且存在一個(gè)調(diào)節(jié)因子的最佳范圍能夠促進(jìn)合作的涌現(xiàn)。

高聚類系數(shù)；冪律可調(diào)；異質(zhì)配置；演化博弈

0 引言

理解網(wǎng)絡(luò)結(jié)構(gòu)和動(dòng)態(tài)演化特性之間的關(guān)系是復(fù)雜網(wǎng)絡(luò)的研究方向之一?！癢S小世界網(wǎng)絡(luò)”具有較高的聚類系數(shù)[1]，“BA無(wú)標(biāo)度網(wǎng)絡(luò)”節(jié)點(diǎn)的度服從冪律分布的特性[2]，現(xiàn)在許多文獻(xiàn)對(duì)這兩個(gè)經(jīng)典網(wǎng)絡(luò)模型進(jìn)行了深入的研究。但是現(xiàn)實(shí)世界中的網(wǎng)絡(luò)一般同時(shí)具備高聚類無(wú)標(biāo)度的特性，因此Holme與Kim提出了同時(shí)具備高聚類和無(wú)標(biāo)度特性的HK網(wǎng)絡(luò)模型[3]。然而在HK網(wǎng)絡(luò)模型的構(gòu)造過(guò)程中，網(wǎng)絡(luò)中新加入的節(jié)點(diǎn)只與網(wǎng)絡(luò)中已存在節(jié)點(diǎn)之間建立連接。本文從實(shí)際出發(fā)聯(lián)合考慮到網(wǎng)絡(luò)的“內(nèi)部演化”與“三角結(jié)構(gòu)”，提出了一種冪律可調(diào)的網(wǎng)絡(luò)模型，該網(wǎng)絡(luò)模型在服從冪律分布且冪律可調(diào)的情況下，相對(duì)于HK網(wǎng)絡(luò)具有更高的聚類系數(shù)。

1 網(wǎng)絡(luò)模型的構(gòu)建

1.1 網(wǎng)絡(luò)模型內(nèi)部演化機(jī)制

假設(shè)在已知網(wǎng)絡(luò)中加入一個(gè)新節(jié)點(diǎn)，網(wǎng)絡(luò)中已經(jīng)存在的節(jié)點(diǎn)i被選中連接的概率服從：

(1)

其中,ki為i節(jié)點(diǎn)的度，∑kj為網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度之和，本文所提出的高聚類冪律可調(diào)網(wǎng)絡(luò)內(nèi)部演化模型構(gòu)建過(guò)程如下：

1) 初始狀態(tài): 初始網(wǎng)絡(luò)中含有m0個(gè)完全相連接的節(jié)點(diǎn)。

3) 終止條件: 網(wǎng)絡(luò)的規(guī)模N達(dá)到預(yù)先設(shè)定的值。

1.2 演化網(wǎng)絡(luò)度分布分析

(2)

(3)

解微分方程(3)得：

(4)

則

(5)

因此：

(6)

則該網(wǎng)絡(luò)模型的冪律指數(shù)γ為

(7)

由于概率p∈[0,1]，通過(guò)式(7)可得當(dāng)p=0時(shí)，該網(wǎng)絡(luò)模型的冪律指數(shù)γ=3則網(wǎng)絡(luò)回歸到BA無(wú)標(biāo)度網(wǎng)絡(luò)。當(dāng)p=1時(shí)γ=5-4/(m+1)因此該網(wǎng)絡(luò)為冪律指數(shù)大小介于γ=3和γ=5-4/(m+1)之間的冪律可調(diào)網(wǎng)絡(luò)模型。且p是新加入的節(jié)點(diǎn)的邊選中以式(1)連接的某點(diǎn)的鄰居的概率，p的值影響了網(wǎng)絡(luò)中形成三角結(jié)構(gòu)的數(shù)量即該網(wǎng)絡(luò)中三角回路的數(shù)量。由于內(nèi)部演化機(jī)制的存在，使得網(wǎng)絡(luò)中的三角回路的數(shù)量呈倍數(shù)增長(zhǎng)，這種網(wǎng)絡(luò)結(jié)構(gòu)對(duì)論文后半部分研究的異質(zhì)配置模式公共品演化博弈有重要影響。

1.3 仿真分析

復(fù)雜網(wǎng)絡(luò)中某點(diǎn)i的聚類系數(shù)可表示為

(8)

其中,n為節(jié)點(diǎn)i的所有相鄰節(jié)點(diǎn)之間相互連接的邊的個(gè)數(shù)，k為節(jié)點(diǎn)i的所有相鄰的節(jié)點(diǎn)的個(gè)數(shù)，即節(jié)點(diǎn)i的鄰居。本文提出的高聚類冪律可調(diào)網(wǎng)絡(luò)模型，由于內(nèi)部演化機(jī)制的存在，網(wǎng)絡(luò)新邊的產(chǎn)生不只存在于新舊節(jié)點(diǎn)之間，也存在于被當(dāng)作某中心節(jié)點(diǎn)的鄰居而選中的舊節(jié)點(diǎn)與該中心節(jié)點(diǎn)的其他鄰居之間，根據(jù)式(8)可知，該網(wǎng)絡(luò)模型的聚類系數(shù)將大大提升。

圖1的實(shí)驗(yàn)結(jié)果顯示了本文提出的高聚類冪律可調(diào)網(wǎng)絡(luò)模型的聚類系數(shù)與HK網(wǎng)絡(luò)模型聚類系數(shù)的比較，初始條件中網(wǎng)絡(luò)中原有節(jié)點(diǎn)數(shù)m0為8, 每次引入新節(jié)點(diǎn)時(shí)與新節(jié)點(diǎn)連接的邊數(shù)m為6，最終生成網(wǎng)絡(luò)的規(guī)模N=1 000，由仿真結(jié)果可以看出，隨著調(diào)節(jié)概率p的增加，網(wǎng)絡(luò)的聚類系數(shù)單調(diào)地增加，在相同的調(diào)節(jié)概率下，由于舊節(jié)點(diǎn)之間同時(shí)產(chǎn)生新邊的內(nèi)部演化機(jī)理，高聚類冪律可調(diào)網(wǎng)絡(luò)的聚類系數(shù)遠(yuǎn)遠(yuǎn)高于HK網(wǎng)絡(luò)的聚類系數(shù)。

圖1 聚類系數(shù)比較Fig.1 Comparison of clustering coefficients

2 異質(zhì)配置模式公共品博弈

2.1 復(fù)雜網(wǎng)絡(luò)上的公共品博弈

假設(shè)在一個(gè)公共品博弈中，參與者總數(shù)為N,每個(gè)參與者獨(dú)立地決定是否以代價(jià)c在公共品博弈中進(jìn)行投資，且總體回報(bào)能夠增值r(r>1)倍，博弈完成之后的總體回報(bào)會(huì)全部平均分給所有參與者[9]。則合作者的收益PC與背叛者的收益PD可表示為：

(9)

從整體來(lái)看，由于背叛者的收益總是高于合作者的收益，如果博弈持續(xù)下去，所有的參與者將都不會(huì)進(jìn)行投資，因而所有參與者將都不會(huì)有收益，從而導(dǎo)致公共悲劇。但如果所有的參與者都進(jìn)行投資那么所有的參與者都能獲得最高報(bào)酬。為了防止這種公共悲劇的發(fā)生，更好地促進(jìn)每個(gè)參與者參與合作，達(dá)到納什均衡時(shí)參與者都有較大的收益，本文提出了以下異質(zhì)配置模式的公共品博弈模型。

2.2 異質(zhì)配置模式公共品博弈模型

假設(shè)公共品博弈中每個(gè)個(gè)體i參與由自己和ki個(gè)鄰居組成的ki+1次公共物品博弈，并以資金量Q進(jìn)行投資。則i從鄰居j中獲得的收益可表示為

(10)

則i點(diǎn)所參與的由自己和ki個(gè)鄰居組成的ki+1次公共物品博弈獲得的總收益的表達(dá)式為

(11)

當(dāng)β=0時(shí)，合作者的投入量不受調(diào)節(jié)因子的影響均為C，該演化博弈模型為投入均質(zhì)模型。當(dāng)β≠0時(shí)合作者依靠調(diào)節(jié)因子β來(lái)調(diào)節(jié)投入異質(zhì)性的強(qiáng)弱。得到收益和之后，所有個(gè)體隨機(jī)選取一個(gè)鄰居按照Fimi演化規(guī)則決定是否采取該鄰居的策略[10]。如每輪博弈完成之后，總收益為Pi的i個(gè)體是否采取隨機(jī)選取的總收益為Pj的i點(diǎn)的鄰居j的策略的概率服從：

(12)

其中,k刻畫了參與者的非理性程度，當(dāng)k→0時(shí)表示參與者為完全理性，該參與者只會(huì)學(xué)習(xí)自身的博弈策略。本論文中的所有仿真程序k的值均為0.1，初始時(shí)，背叛者與合作者的比例均占50%。

2.3 仿真分析

圖2 合作概率的變化Fig.2 Change of cooperation probability

2.3.1高聚類冪律可調(diào)網(wǎng)上均質(zhì)公共品博弈

由式(10)可得當(dāng)調(diào)節(jié)因子β=0時(shí)，個(gè)體的投入資金量為固定值C，即可得到投入均質(zhì)模型，在該高聚類冪律可調(diào)網(wǎng)絡(luò)上通過(guò)改變網(wǎng)絡(luò)構(gòu)造過(guò)程中的可調(diào)概率p，觀察網(wǎng)絡(luò)結(jié)構(gòu)的變化對(duì)投入均質(zhì)模型的影響，其仿真結(jié)果如圖2所示。

仿真實(shí)驗(yàn)是在N=1 000的網(wǎng)絡(luò)上博弈200次取最后50次平均得到的，仿真結(jié)果顯示在增益因子r比較小的情況下，演化博弈的合作概率pc結(jié)果為0，隨著增益因子的增加，合作比率呈線性增長(zhǎng)最后趨于穩(wěn)定。由于在該網(wǎng)絡(luò)構(gòu)造過(guò)程中，當(dāng)概率p=0時(shí)，網(wǎng)絡(luò)回歸到BA網(wǎng)絡(luò)，由仿真結(jié)果看出博弈達(dá)到穩(wěn)定后合作概率較低，且達(dá)到穩(wěn)定狀態(tài)需要較大的r值。隨著p的逐漸增加，網(wǎng)絡(luò)的聚類系數(shù)隨之增大，且網(wǎng)路中三角形回路的數(shù)量不斷增加，從而形成結(jié)構(gòu)上的反饋機(jī)制。文獻(xiàn)[11]證明HK網(wǎng)絡(luò)中的三角形回路能夠促進(jìn)網(wǎng)絡(luò)演化博弈個(gè)體的合作。所以在增益因子r相同的情況下，p越大對(duì)應(yīng)的合作概率就越高。

2.3.2高聚類冪律可調(diào)網(wǎng)絡(luò)上異質(zhì)公共品博弈

當(dāng)式(10)中調(diào)節(jié)因子β≠0時(shí)，每個(gè)合作者投入資金量C受調(diào)節(jié)因子β的影響不再是固定值，而是根據(jù)某節(jié)點(diǎn)與鄰居節(jié)點(diǎn)，鄰居節(jié)點(diǎn)與二層鄰居節(jié)點(diǎn)中合作者占參與者的比重來(lái)決定。因?yàn)橘Y金配置過(guò)于異質(zhì)或者過(guò)于均勻都會(huì)抑制合作，為了保證參與者在這種外在強(qiáng)制調(diào)節(jié)的干預(yù)下，資源配置在量上對(duì)每輪公共品博弈的收益達(dá)到最優(yōu)，經(jīng)過(guò)反復(fù)試驗(yàn)發(fā)現(xiàn)，調(diào)節(jié)因子β應(yīng)合理地限制在(0,1]中。

圖3表示調(diào)節(jié)因子與合作概率的關(guān)系，當(dāng)β控制在(0,1]時(shí)，隨著r的增長(zhǎng)，pc與r之間呈現(xiàn)出一種平緩的正相關(guān)關(guān)系，r值越大越能夠維持合作者的生存，合作概率不斷提高，且能快速達(dá)到穩(wěn)定狀態(tài)。當(dāng)β超出(0,1]的范圍時(shí)，r的差異對(duì)該演化博弈的影響逐漸變小，隨著β的不斷增加，最終不同的r值具有相似的合作水平。

由圖4的結(jié)果可以看到，在網(wǎng)絡(luò)狀況相同情況下，隨著增益因子的增加，異質(zhì)配置模式公共品博弈可以較同質(zhì)配置模式公共品博弈更快速到達(dá)納什均衡穩(wěn)定狀態(tài)，且出現(xiàn)合作涌現(xiàn)?；谝陨辖Y(jié)果分析，當(dāng)β≠0時(shí)，若要增加收益，網(wǎng)絡(luò)中個(gè)體基于目前一層鄰居與二層鄰居中合作者數(shù)目的比例來(lái)進(jìn)行投資。由于β控制在(0,1]之內(nèi)，若合作者與參與者之比≥0.5說(shuō)明社團(tuán)中有較多的合作者，β取(0,1]，這種強(qiáng)制干預(yù)調(diào)節(jié)使得合作者占參與者的比重在原始基礎(chǔ)上增加，從而參與者的每輪博弈獲得比不加強(qiáng)制調(diào)節(jié)之前更高的收益，網(wǎng)絡(luò)中的個(gè)體更趨向于選擇合作，進(jìn)而提高了合作概率。若合作者與參與者之比<0.5說(shuō)明相應(yīng)節(jié)點(diǎn)范圍內(nèi)有較少的合作者，β取其相反數(shù)，同樣通過(guò)這種強(qiáng)制調(diào)節(jié)，使得合作者占參與者的比重>1，參與者的每輪博弈同樣獲得比不加強(qiáng)制調(diào)節(jié)之前更高的收益，進(jìn)而這種調(diào)節(jié)作用使得合作者投資量不斷增加，其鄰居獲得的收益量隨之增加。由于個(gè)體收

圖3 合作概率的變化Fig.3 Development of cooperation probability

圖4 博弈結(jié)果結(jié)果比較Fig.4 Comparison of game results

益同時(shí)受一層鄰居和二層鄰居的影響，該高聚類冪律可調(diào)網(wǎng)絡(luò)中存在大量三角形回路，如果三角形兩個(gè)頂點(diǎn)上的參與者均為合作者那么他們可以通過(guò)另一個(gè)頂點(diǎn)作為共同的鄰居具有式(11)的收益關(guān)系，從而獲得額外的收益，因此該網(wǎng)絡(luò)的高聚類特性使得中心節(jié)點(diǎn)與一層鄰居和二層鄰居之間產(chǎn)生結(jié)構(gòu)上的正反饋互惠機(jī)制，降低了合作策略擴(kuò)散的閾值，使得演化博弈繼續(xù)進(jìn)行的過(guò)程中有更多的個(gè)體趨向于合作。

圖5顯示了該演化博弈策略的空間動(dòng)態(tài)斑圖，其中淺色代表合作個(gè)體，深色代表背叛個(gè)體。從圖中可以看出，隨著演化博弈的進(jìn)行，合作者的合作簇不斷擴(kuò)散，背叛者的簇逐漸消減，直至合作者幾乎占據(jù)整個(gè)博弈空間(見(jiàn)圖5d)。由于度較大的的節(jié)點(diǎn)每輪博弈后的累計(jì)收益一般會(huì)比小度節(jié)點(diǎn)高，所以如果中心節(jié)點(diǎn)采用合作策略，又由于資金投入調(diào)節(jié)機(jī)制的存在，其收益會(huì)隨著鄰居中的合作者數(shù)目增加而提高，從而促使更多鄰居采用中心節(jié)點(diǎn)的策略而轉(zhuǎn)變?yōu)楹献髡?，同時(shí)鄰居中合作者數(shù)目的提高又會(huì)使得中心節(jié)點(diǎn)的收益提高，進(jìn)而形成了采用合作策略的中心節(jié)點(diǎn)的收益與其鄰居策略選擇間的正反饋機(jī)制。

圖5 空間斑圖Fig.5 Space pattern

3 結(jié)論

本文基于“三角結(jié)構(gòu)”與“內(nèi)部演化”機(jī)制，提出了一種高聚類冪律可調(diào)的網(wǎng)絡(luò)結(jié)構(gòu)模型，該模型的高聚類特性會(huì)使得中心節(jié)點(diǎn)與鄰居節(jié)點(diǎn)之間產(chǎn)生結(jié)構(gòu)上的正反饋互惠，降低了合作策略擴(kuò)散的閾值；并在此基礎(chǔ)上提出了一種通過(guò)調(diào)節(jié)因子來(lái)調(diào)節(jié)公共品博弈中合作者比例來(lái)控制投入差異的異質(zhì)配置模式公共品博弈，實(shí)驗(yàn)證明在該高聚類冪律可調(diào)網(wǎng)絡(luò)上進(jìn)行異質(zhì)配置模式公共品博弈，存在調(diào)節(jié)因子∈[0,1)使得博弈快速達(dá)到納什均衡，促進(jìn)合作的涌現(xiàn)。

[1] Watts D J,Strogatz S H. Collective dynamics of small-world networks[J]. Nature, 1998, 393(3): 440-442.

[2]Barabási A L, Albert R,Jeong H. Mean-field theory for scale-free random networks[J]. Physica A Statistical Mechanics & Its Applications, 1999, 272(1/2): 173-187.

[3]Holme P, Kim B J. Growing scale-free networks with tunable clustering[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2001, 65(2): 95-129.

[4]Huang Z G,Wu Z X,Wu A C,et al. Role of collective influence in promoting cooperation[J]. Europhysics Letters, 2008, 84(5): 786-798.

[5]Yang H X,Wu Z X,Du W B. Evolutionary games on scale-free networks with tunable degree distribution[J]. Europhysics Letters, 2012, 99(99): 288-290.

[6]Yang H X,Wang W X,Wu Z X, et al. Diversity-optimized cooperation on complex networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2009, 79(2): 711-715.

[7]Li Z,Deng C,Suh I H. Network topology control strategy based on spatial evolutionary public goods game[J]. Physica A Statistical Mechanics & Its Applications, 2015, 432: 16-23.

[8]Chen M H,Wang L,Sun S W,et al. Evolution of cooperation in the spatial public goods game with adaptive reputation assortment[J]. Physics Letters A, 2015, 380(1): 40-47.

[9]Colman A M. Game theory and its applications in the social and biological sciences[J]. Journal of Behavioral Decision Making, 1998, 11(3): 228-229.

[10] Gy?, Szabó R, Toke A C. Evolutionary prisoner's dilemma game on a square lattice[J]. Physical Review E, 1998, 58(1): 69-73.

[11] Rong Z,Yang H X,Wang W X. Feedback reciprocity mechanism promotes the cooperation of highly clustered scale-free networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2010, 82(2): 1922-1928.

(責(zé)任編輯 李進(jìn))

Donation-Diversity Public Goods Game on High Clustering Coefficient and Adjustable Power-Law Networks

MIAO Ping, YANG Hongyong

(School of Information and Electrical Engineering, Ludong University, Yantai 264025, China)

In order to study the relationship between network structure and evolutionary game,a high clustering coefficient and adjustable power-law network model is put forward on the basis of the “triangular structure” and “internal evolution” evolution mechanism in the network. This model possesses the same characteristics as the standard scale-free networks such as the power-law degree distribution, but with the high clustering at the same time. And on the basis of the network model, according to the numbers of cooperators that is in a node with it’s immediate neighbors and neighbors’ neighbors to determine the difference of cooperators’ inputs in public goods game, in the same time use a regulatory factor to adjust the degree of heterogeneity. The simulation proves that the heterogeneous configuration model can quickly reach the Nash equilibrium, and the adjustment factors exist an optimal range can promote the boom of cooperation on the new network model.

high clustering coefficient; adjustable power-law; heterogeneous configuration; evolutionary game

1672-3813(2017)02-0052-07；

10.13306/j.1672-3813.2017.02.008

2016-07-09；

2016-12-02

國(guó)家自然科學(xué)基金(61273152,61673200)；山東省科技發(fā)展計(jì)劃(2012YD03110)

苗萍(1990-)，女，山東泰安人，碩士研究生，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)、博弈論。

楊洪勇(1967-)，男，山東德州人，博士，教授，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)、多智能體編隊(duì)控制等。

N94; F224

A