基于聲譽的網(wǎng)絡成長模型

辛琦

福建江夏學院 經(jīng)濟貿(mào)易學院,福建 福州 350108

合作在自然和人類系統(tǒng)中極為重要，它是每一個新的群體組織出現(xiàn)的必要先決條件。演化博弈理論[1]為研究合作提供了有力的框架。研究表明親緣選擇、直接互惠、間接互惠、群體選擇和空間互惠是促進合作的五種主要演化機制[2]。其中，間接互惠意味著“助人者，人助之”，人們總是希望與樂于助人者（合作者）交往，而遠離自私者（背叛者）。因此，該機制能很好地解釋為什么人類社會中無血緣、無種群關系的個體之間會產(chǎn)生合作。

網(wǎng)絡是描述群體組織及其內(nèi)部關聯(lián)性的有力工具。近年來，關于合作行為與網(wǎng)絡結構的協(xié)同演化問題受到廣泛關注[3-6,8-10]。本文將側重于研究間接互惠機制下的網(wǎng)絡協(xié)同演化問題。間接互惠機制中，聲譽是個體合作行為的累積，對促進合作具有重要作用[7]。文獻[8]首次在網(wǎng)絡動態(tài)演化博弈中引入“聲譽”機制，個體根據(jù)聲譽更換鄰居，斷開與低聲譽鄰居的連接，并以一定的概率與高聲譽個體建立連接，在此基礎上研究網(wǎng)絡的合作演化。文獻[9]考慮了方格網(wǎng)絡中，個體可因不滿所處的聲譽環(huán)境而產(chǎn)生遷移，進而研究遷移行為對合作演化的影響。文獻[10]改進了聲譽計算方法，并利用公共物品博弈模型研究考慮成本的伙伴更新行為對網(wǎng)絡合作演化的影響。上述文獻都是在網(wǎng)絡節(jié)點及連邊數(shù)量均不變的情況下，網(wǎng)絡拓撲結構由于個體或者連邊在聲譽影響下產(chǎn)生移動而改變，進而研究網(wǎng)絡的合作演化問題。

在實際的社會網(wǎng)絡中，組織因發(fā)展需要會不斷完善結構形態(tài)，調(diào)整網(wǎng)絡規(guī)模，吸收新的個體，淘汰劣質(zhì)個體，而個體也會根據(jù)自己的需求進入或者離開某個群體或組織。因此，網(wǎng)絡結構的改變不僅僅是個體之間關聯(lián)的變化，還應涉及網(wǎng)絡規(guī)模的變化。尤其，處于成長過程中的網(wǎng)絡，網(wǎng)絡規(guī)模持續(xù)擴大，隨著網(wǎng)絡結構的不斷演變，其復雜性[11,12]特征日益凸顯。本文考慮網(wǎng)絡隨著新個體的進入及其連邊的增加而不斷成長，研究在聲譽機制作用下，個體博弈策略改變和個體連接選擇雙動力下的網(wǎng)絡共演化問題。

1 網(wǎng)絡演化模型

描述社會困境的囚徒困境博弈（Prisoner’s Dilemma Game，PDG）是研究在自私個體構成的群體中合作是如何產(chǎn)生的典型模型。該模型中，兩位博弈者同時進行決策，選擇合作或者背叛策略，由此獲取收益。博弈雙方因相互合作得到報酬R和相互背叛受到懲罰P，當背叛者與合作者相遇時，前者能獲得最高收益T（即背叛誘惑），而后者只有最低收益S。因此，這4個收益參數(shù)滿足不等式T＞R＞P＞S，并且 2R＞T+S。不失一般性，本文以弱囚徒困境[13]（即T=b，R=1，P=S=0，且 1≤b≤2）模型為基礎進行基于聲譽的網(wǎng)絡共演化問題的研究。

成長網(wǎng)絡的初始結構是一個由m0個節(jié)點（個體）構成的全連通網(wǎng)絡，其中，每個個體的初始狀態(tài)是聲譽為1的合作者?？紤]網(wǎng)絡博弈和網(wǎng)絡成長兩個時間尺度，分別用τD和τT表示，在每一輪時間尺度τD內(nèi)，所有個體根據(jù)弱囚徒困境模型與周圍鄰居進行博弈而獲得相應收益，該收益決定了是否需要改變策略，并基于該輪博弈所采取的策略更新個體聲譽值；對于每一輪時間尺度τT，網(wǎng)絡會有一個新個體加入，該個體根據(jù)聲譽情況與m個原有個體建立連接。以下是對個體策略演化、聲譽更新以及新加入個體的連接選擇方法的具體介紹。

個體策略演化時，個體與所有鄰居一一博弈，依據(jù)弱囚徒困境模型的收益矩陣得出每一博弈結果的收益值，與所有鄰居博弈后的收益之和即為個體在該輪博弈中獲得的總收益，然后根據(jù)復制動力學（Replicator Dynamics）演化規(guī)則來調(diào)整自己的策略，即，對于個體i隨機選擇的鄰居j，當j的收益fj(t)大于i的收益fj(t)時，i便以一定的概率向j進行策略學習，并且該概率與兩者的收益差成正比，計算公式如下。

式中，ki(t)，kj(t)分別表示時間步t時個體i和j的度（即，鄰居的數(shù)量）。個體策略調(diào)整之后，更新其聲譽值，聲譽的計算方法如公式(2)所示[8]。

式中，Ri(t)表示時間步t時個體i的累積聲譽值；Si(t)表示時間步t時個體i的單次聲譽值，如果個體i采取合作策略，則Si(t)=1，否則Si(t)=0；α(α∈[0,1])表示歷史聲譽的衰減系數(shù)，當α→0時，歷史聲譽不起作用，當α→1時，歷史聲譽不會衰減，個體聲譽值為歷次時間步所得聲譽值的累加。

網(wǎng)絡結構演化時，網(wǎng)絡中新加入一個個體，其初始狀態(tài)是隨機生成的，即，個體有50%的概率成為一個合作者，相應的初始聲譽值為1；否則該個體就是一個背叛者，初始聲譽值為0。新個體在選擇網(wǎng)絡中已有個體進行連接時，聲譽越高者獲得連接的概率越大，連接概率的計算如公式(3)所示。

式中，L(t)表示時間步t時網(wǎng)絡中所有個體的集合；γ(γ∈[0,∞])表示新加入個體在選擇原有個體建立連接時對聲譽的敏感度，當γ→0時，新增個體與網(wǎng)絡中所有個體建立連接的概率相等，個體的聲譽不起作用；當γ→∞時，新增個體與網(wǎng)絡中聲譽最高的個體以100%概率建立連接。

2 仿真實驗及數(shù)據(jù)分析

成長網(wǎng)絡的初始結構是一個全聯(lián)通網(wǎng)絡，只包含m0=3個個體，每個個體的初始狀態(tài)均為聲譽值為1的合作者。每個新增個體加入網(wǎng)絡時，與m=2個原有個體建立連接。個體策略演化和網(wǎng)絡結構演化的時間尺度滿足關系τD=10τT[15]。以下分別從網(wǎng)絡的度分布，聲譽對合作演化的影響，背叛誘惑、聲譽衰減系數(shù)、聲譽敏感度對合作演化的影響等方面對網(wǎng)絡的演化特征進行仿真分析。仿真數(shù)據(jù)是通過對網(wǎng)絡規(guī)模成長至個體數(shù)量N=5000的50次獨立實驗結果取平均得到。

2.1 網(wǎng)絡結構的特征分析

由圖1可見，當網(wǎng)絡成長為有5000個個體時，網(wǎng)絡結構呈現(xiàn)出冪律分布特征，大多數(shù)個體的度較小，即只有較少的連邊，但存在少數(shù)具有較大度的個體，它們是網(wǎng)絡中其他個體爭相與之建立連接的對象。與初始的同質(zhì)的全連通的網(wǎng)絡結構相比，經(jīng)過不斷演化，網(wǎng)絡結構的異質(zhì)性和復雜性凸顯。圖2表明個體的度與聲譽值之間是正相關關系。對應圖1和圖2可以看出，雖然度大的個體的數(shù)量很少，但是他們具有較高的聲譽值，其原因在于，由于引入了聲譽機制，新增個體傾向于與高聲譽者建立連接，高聲譽者往往都是合作者，由于多數(shù)個體愿意或者已經(jīng)與其相連而成為它的鄰居，使其在博弈收益總量上遠遠高于其他個體，因此能夠保持合作策略不變，聲譽值不斷上升，進而吸引更多的個體與之相連，如此循環(huán)，形成圖1和圖2所呈現(xiàn)的“富者恒富”之特征。

圖1 網(wǎng)絡的度分布(b=1.5,α=1,γ=1)Fig.1 Distribution of network’s degrees(b=1.5,α=1,γ=1)

圖2 度與聲譽之間的關系(b=1.5,α=1,γ=1)Fig.2 Relationship between degree and reputation(b=1.5,α=1,γ=1)

2.2 背叛誘惑和聲譽對網(wǎng)絡合作演化的影響分析

圖3 所示為兩種成長機制下背叛誘惑對網(wǎng)絡合作率的影響。兩種成長機制中，一種是基于聲譽的網(wǎng)絡成長機制，新增個體的連接是根據(jù)聲譽（公式(3)）而建立的；另一種是基于收益的網(wǎng)絡成長機制，新增個體的連接是根據(jù)收益而建立的[15]。曲線R和F分別反映了這兩種成長機制下網(wǎng)絡合作率Cρ與背叛誘惑b的關系，為網(wǎng)絡中合作者的數(shù)量，N=5000為網(wǎng)絡中所有個體的數(shù)量）。由圖3可見，隨著b不斷增大，兩種機制下網(wǎng)絡的合作率均呈現(xiàn)下降趨勢。這理所當然是因為當背叛誘惑越大，人們越會為了獲取更高的利益而不惜背叛自己的伙伴，從而導致ρC不斷下降。同時，基于聲譽成長的網(wǎng)絡合作率總是高于基于收益成長的網(wǎng)絡合作率，當背叛誘惑較小時，兩種網(wǎng)絡的合作率差別并不大，但是，b越大，這種差別越明顯。其原因在于，如果新增個體的連接是注重聲譽而非收益，則在一定程度上可以避免與背叛者連接而遭受損失的風險，當背叛誘惑越大，所規(guī)避的風險損失也就越大。聲譽機制使得高聲譽者獲得更多的連接，又由于個體的收益是其與所有鄰居分別博弈后的所有收益之和，因此鄰居數(shù)量越多，個體獲得高收益的可能性越大，而高聲譽者的高收益則會導致其眾多的鄰居向其學習，采取合作策略，從而不斷促進整個網(wǎng)絡的合作演化。

圖3 背叛誘惑和聲譽機制對網(wǎng)絡合作率的影響(α=1,γ=1)Fig.3 Influence of defection temptation and reputation mechanism on network cooperation rate(α=1,γ=1)

2.3 聲譽衰減系數(shù)和聲譽敏感度對網(wǎng)絡合作演化的影響分析

圖4 對比了聲譽衰減系數(shù)α不同取值時ρC的變化曲線，圖5是聲譽敏感度γ不同取值時ρC的變化曲線。由兩組曲線圖可見，無論α、γ取值如何，ρC總是隨著b值的增大而減少。但是，α和γ的不同取值，決定了ρC下降的速度和幅度。

公式(2)體現(xiàn)了歷史聲譽會隨著時間的流逝而不斷衰減，衰減程度由參數(shù)控制。由圖4可知，本例中，當時，ρC曲線基本一致，這是因為當α較小時，網(wǎng)絡經(jīng)過若干時間步的成長，個體的歷史聲譽以較大的幅度產(chǎn)生衰減，其作用幾乎為0；只有當α足夠大時，歷史聲譽的作用才得以體現(xiàn)。如圖4所示，歷史聲譽作用越大（α越大），越能有效地減少因背叛產(chǎn)生的高收益對個體的誘惑，越有利于促進網(wǎng)絡的合作演化。

公式(3)中的聲譽敏感度γ體現(xiàn)了聲譽在新增個體選擇原有個體建立連接時所發(fā)揮作用的大小。由圖5可見，當γ較大時，網(wǎng)絡合作率較大，也較為穩(wěn)定，幾乎不受背叛誘惑b的影響；當γ較小時，網(wǎng)絡合作率會隨著背叛誘惑的增大而下降。根據(jù)公式(3)，當γ越大，聲譽值越高的個體會以越高的概率獲得新增個體的連接，當γ大到一定程度時，新增個體會確定與網(wǎng)絡中聲譽值最高和次高的兩個個體建立連接。正如上文所分析，高聲譽者獲取高收益，影響大量其他個體向他們學習，成為合作者，將網(wǎng)絡的合作率穩(wěn)定在比較高的水平。而當γ較小時，聲譽值所發(fā)揮的作用并不充分，聲譽較低的個體會以一定的概率得到新增個體的連接，并在較大的背叛誘惑收益下影響與其相連的所有鄰居，從而降低整個網(wǎng)絡的合作率。

圖4 衰減系數(shù)對網(wǎng)絡合作率的影響(γ=1)Fig.4 Influence of attenuation coefficient on network cooperation rate(γ=1)

圖5 聲譽敏感度對網(wǎng)絡合作率的影響(α=1)Fig.5 Influence of reputation sensitivity on network cooperation rate(α=1)

4 結論

合作對人類社會的發(fā)展具有重要意義。間接互惠是一種促進合作演化的重要機制，聲譽作為衡量反復博弈時個體策略特征的指標，對間接互惠機制下的網(wǎng)絡合作演化具有重要影響。本文構建了一個基于聲譽的網(wǎng)絡成長模型。該模型提供了雙動力學的網(wǎng)絡共演化機制，即基于收益的個體策略演化和基于聲譽的網(wǎng)絡結構演化。

通過數(shù)值仿真分析網(wǎng)絡度分布的特點、聲譽機制的引入和背叛誘惑對網(wǎng)絡合作率的影響、聲譽衰減系數(shù)和聲譽敏感度對網(wǎng)絡合作率的影響，并得出如下結論：（1）網(wǎng)絡的節(jié)點度分布具有冪律分布特點，并且，聲譽越高者，度越大。這與現(xiàn)實的人類社會網(wǎng)絡特征相符，一個人如果越是利他者，則越能吸引其他人與之交往，進而更有機會獲得更多人的幫助而從中獲利；（2）與注重收益而產(chǎn)生個體之間的連接相比，基于聲譽的連接選擇能更好地促進網(wǎng)絡的合作演化，并且，后者比前者具有更強的抗拒背叛誘惑的能力；（3）聲譽衰減系數(shù)α控制著歷史聲譽對當下聲譽累積值的貢獻程度，進而影響整個網(wǎng)絡的合作演化結果。α越大，越有利于網(wǎng)絡合作率的提高，但是，該特點只有在α足夠大時才表現(xiàn)得比較明顯，否則，歷史聲譽會因若干時間步的不斷重復衰減而幾乎為0，無法發(fā)揮作用；（4）聲譽敏感度γ控制著個體獲得連接的概率，進而影響整個網(wǎng)絡的合作演化結果。γ越大，網(wǎng)絡合作率越高，抵抗背叛誘惑的能力越強，并且當γ足夠大時，背叛誘惑幾乎無法發(fā)揮作用。

本文所提出的網(wǎng)絡結構的演化側重于探討隨著個體數(shù)量的不斷增加，網(wǎng)絡規(guī)模的不斷擴大，網(wǎng)絡結構是如何演化的；并且，網(wǎng)絡的成長不是依賴于節(jié)點度[14]或者收益[15,16]，而是將聲譽機制引入了網(wǎng)絡成長模型?，F(xiàn)實社會中，各種網(wǎng)絡的規(guī)模并非固定不變，并且聲譽往往是個體選擇交往對象的決定性因素，因此，本文的研究結果將有助于人們更好地理解現(xiàn)實社會網(wǎng)絡在發(fā)展成長過程中，聲譽機制是如何發(fā)揮作用，并促進網(wǎng)絡的合作演化。

[1]Smith MJ.Evolution and the Theory of Games[M].Cambridge,UK:Cambridge University Press,1982

[2]Nowak MA.Five rules for the evolution of cooperation[J].Science,2006,314(5805):1560-1563

[3]Szolnoki A,Szabó G.Cooperation enhanced by inhomogeneous activity of teaching for evolutionary Prisoner's Dilemma games[J].Europhysics Letters,2007,77(3):30004

[4]Fu F,Liu LH,Wang L.Evolutionary prisoner's dilemma on heterogeneous Newman-Watts small-world network[J].The European Physical Journal B,2007,56(4):367–372

[5]Santos FC,Pacheco JM,Lenaerts T.Evolutionary dynamics of social dilemmas in structured heterogeneous populations[J].Proc Natl Acad Sci USA,2006,103(9):3490-3494

[6]Hauert C,Doebeli M.Spatial structure often inhibits the evolution of cooperation in the snowdrift game[J].Nature,2004,428(6983):643-646

[7]Nowak MA,Sigmund K.Evolution of indirect reciprocity by image scoring[J].Nature,1998,393(6685):573-577

[8]Fu F,Hauert C,Nowak MA,et al.Reputation-based partner choice promotes cooperation in social networks[J].Physical Review E,2008,78(2):026117

[9]CongR,WuB,QiuY,etal.EvolutionofCooperationDrivenbyReputation-BasedMigration[J].PLoSOne,2012,7(5):e35776

[10]Li Y.The evolution of reputation-based partner-swithching behaviors with a cost[J].Scientific Reports,2014(4):5957

[11]Newman MEJ.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256

[12]BoccalettiS,LatoraV,MorenoY,etal.Complexnetworks:structureanddynamics[J].PhysicsReports,2006,424(1):175-308

[13]Nowak MA,May R.Evolutionary games and spatial chaos[J].Nature,1992,359(6398):826-829

[14]Albert R,Barabasi AL.Statistical mechanics of complex networks[J].Reviews of Modern Physics,2002,74(1):47-98

[15]Poncela J,Gómez-Garde?es J,Floría LM,et al.Complex cooperative networks from evolutionary preferential attachment[J].PLoS One,2008,3(6):e2449

[16]辛 琦,周 曉.基于動態(tài)收益矩陣的成長網(wǎng)絡合作演化仿真研究[J].系統(tǒng)仿真學報,2017(2):319-325