基于声誉的网络成长模型

辛琦

福建江夏学院 经济贸易学院,福建 福州 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