基于聲譽的網絡成長模型

辛琦

福建江夏學院 經濟貿易學院,福建 福州 350108

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

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

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

1 網絡演化模型

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

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

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

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

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

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

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

2 仿真實驗及數據分析

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

2.1 網絡結構的特征分析

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

圖1 網絡的度分布(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 背叛誘惑和聲譽對網絡合作演化的影響分析

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

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

2.3 聲譽衰減系數和聲譽敏感度對網絡合作演化的影響分析

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

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

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

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

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

4 結論

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

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

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

[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]辛 琦,周 曉.基于動態收益矩陣的成長網絡合作演化仿真研究[J].系統仿真學報,2017(2):319-325