苗 萍，楊洪勇

(魯東大學信息與電氣工程學院，山東 煙臺 264025)

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

苗 萍，楊洪勇

(魯東大學信息與電氣工程學院，山東 煙臺 264025)

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

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

0 引言

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

1 網(wǎng)絡模型的構建

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

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

(1)

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

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

3) 終止條件: 網(wǎng)絡的規(guī)模N達到預先設定的值。

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

(2)

(3)

解微分方程(3)得：

(4)

則

(5)

因此：

(6)

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

(7)

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

1.3 仿真分析

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

(8)

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

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

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

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

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

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

(9)

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

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

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

(10)

則i點所參與的由自己和ki個鄰居組成的ki+1次公共物品博弈獲得的總收益的表達式為

(11)

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

(12)

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

2.3 仿真分析

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

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

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

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

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

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

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

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

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

圖4 博弈結果結果比較Fig.4 Comparison of game results

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

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

圖5 空間斑圖Fig.5 Space pattern

3 結論

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

(責任編輯 李進)

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

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

苗萍(1990-)，女，山東泰安人，碩士研究生，主要研究方向為復雜網(wǎng)絡、博弈論。

楊洪勇(1967-)，男，山東德州人，博士，教授，主要研究方向為復雜網(wǎng)絡、多智能體編隊控制等。

N94; F224

A