网络演化博弈中的自组织临界性

曹亚娟，刘旭升，关剑月

(兰州大学物理科学与技术学院，兰州 730000)

网络演化博弈中的自组织临界性

曹亚娟，刘旭升，关剑月

(兰州大学物理科学与技术学院，兰州 730000)

结合雪堆博弈模型与扩展的Bak-Sneppen(BS)模型，研究一维规则环状网络上合作行为的涌现与个体间的动力学关联性。通过统计系统平均合作概率随时间的演化，发现当系统演化到稳态时群体具有较高的合作水平。此外，统计了个体策略突变行为的雪崩尺寸及适应度最低个体间的距离分布，发现这两种分布可近似为幂律分布。这表明系统自组织达到了一种临界状态，在临界状态个体策略在系统尺度上相互关联，因此与系统中高水平合作行为的涌现有着紧密的关系。

复杂网络; 雪堆博弈；自组织临界性；合作

0 引言

在达尔文时代之后很长一段时间里，大多生物学家认为生物演化是以一种非常光滑和连续的方式进行，并且这种渐进演化需要经过漫长的时间。然而在1972年，美国古生物学家Niles Eldredge和Stephen Jay Gould[1]在研究化石记录时发现生物演化并非这样。他们认为进化是跳跃与停滞相间的，而不是以匀速、平滑、渐变的方式进行。比如恐龙的灭绝，寒武纪大爆发等，但在这些爆发性事件之间经过了一系列小事件的频发。这表明相互作用的物种间的演化达到了一种自组织临界状态。自组织临界性(self-organizedcriticality，SOC)则是用来描述一个系统由远离平衡态自发趋于平衡态的性质，是认识自然界中无标度现象的一个重要理论框架。这一概念最早是由物理学家Per Bak,Chao Tang和Kurt Wiesenfeld[2]在1987年为解释原胞自动机模型上的一些行为而提出。他们通过沙堆模型形象展示了自组织临界态的形成及性质。向一沙堆上不断加入沙砾，随着沙堆斜率的增加整个系统将远离平衡态，当沙堆斜率趋于一个临界值时整个系统将会对极小的微扰产生敏感的反应。此时如果再向沙堆上加入一粒沙子，都可能会引起整个沙堆的崩塌。这就是所谓的“雪崩现象”。通过模拟计算发现当系统处于临界状态时，雪崩尺寸大小与雪崩发生频率呈幂律关系。一般当系统处于自组织临界状态时都可以寻找到空间或时间上的幂律分布。自组织临界性概念提出之后许多研究者都尝试将这一概念应用于研究各种各样具有复杂性出现的现象中，其范围涉及各个领域包括演化生物学、地质学、宇宙学、神经系统学和经济学等等[3-6]。

演化生物学中还有一个根本问题为合作的涌现和维持[7]。根据达尔文的自然选择学说个体都是自私的，在生存竞争中个体都将最大化自己收益。但是不管是在动物群落还是人类社会中我们发现合作行为都是普遍存在的。演化博弈理论[8]为研究这一问题提供了有力的理论框架。近年来，研究人员提出了多种促进合作行为的机制：亲缘选择[9]、直接互惠[10]、间接互惠[11-12]、网络互惠[13-16]、群选择[17-18]等。在每种机制下都有大量的研究给出了合作可以涌现的条件，而这些条件有时是很强的条件。比如在网络互惠中只有代价收益比大于个体平均度[19]时合作才能得以维持，但对于真实网络个体一般都具有较大的度。此外，还有研究者对博弈理论中的自组织临界性进行了深入的研究[20-22]，但是在这些研究中系统动力学导致的临界状态并没有与合作的涌现产生直接联系。

最近，Park和Jeong[23]通过博弈模型与自组织临界模型的结合，对上述演化理论中的两个问题进行了讨论。他们在一维环状网络上采用囚徒困境博弈模型，引入Bak-Sneppen(BS)竞争过程，研究了具有自组织临界性的合作涌现。那么，对于一维环状网络上的雪堆博弈，系统是否会达到自组织临界状态？系统的合作水平如何？基于此，我们引入扩展的BS竞争过程[24]，考察了一维环状网络上的雪堆博弈，发现系统经过长时演化后，BS过程会使系统达到自组织临界状态，从而使群体中合作水平显著提升。

1 方法

1.1 网络和博弈模型

在大小为N的具有周期性边界条件的一维规则环状网络上，令N个个体随机分布在网络的N个格点上。每个个体仅与左右两个相邻个体相互作用。个体之间的相互作用采用经典两策略对称博弈模型:雪堆博弈(SG)。雪堆博弈和囚徒困境博弈都是对不同社会困境的一种描述[25-26]。在博弈过程中每个个体可以采取两种策略：合作(C)或者背叛(D)。一般而言，个体的收益依赖于其采取的策略，可以使用矩阵进行描述：

每一个矩阵元素表示当个体使用左边(列)策略而对手使用上边(行)策略时的收益。在雪堆博弈中，收益参数需满足T>R>S>P，个体最好采取与对手相反的策略，即在雪堆博弈中其纳什均衡[27]为混合策略。本文收益参数分别为：R=1，P=1，0≤S≤1，1≤T≤2。

1.2 群体动力学

对于个体间的竞争过程，则引入推广后的Bak-Sneppen(BS)模型[24,28]。在具有周期性边界条件的晶格网络上，每个个体与其邻居进行相互作用，并根据上述收益矩阵获取收益。假设每个个体在繁殖成功前已经过足够多次的博弈，因此可以使用个体的平均收益表示个体的适应度。个体在博弈时所采取的策略为混合策略，即以概率Pc选择C策略，以概率1-Pc选择D策略。Pc=1和Pc=0分别表示纯合作策略C和纯背叛策略D。于是可以得到个体的平均收益为

fi=(1-S-T)PciK+dSPci+TK

(1)

在每一个时间步长内，适应度最低的个体将会死亡，其位置由一个新的个体取代。新个体的合作概率为一个从区间[0，1]内随机选取的数。考虑到一个物种的突变或灭绝可能会对其周围物种的适应度产生影响，比如生物链上相邻的两物种，当适应度最低的个体死亡时，其邻居位置上的个体也会以一定概率q死亡。如果邻居位置上个体发生死亡则其位置将以同样的方式被新的个体所占据。

在模拟过程中，令N个个体随机排列在一维规则环状网络的N个格点上:

1)初始时从均匀分布在[0，1]内的随机序列P(c)中随机获取N个随机数，作为每个个体的合作概率(混合策略)Pci(i=1,2,…,N)。然后个体与其2个邻居相互作用，获取收益期望值fi(i=1,2,…,N)。

2)在每个时间步内挑出系统中适应度最小的个体改变其策略，改变方法为随机从P(c)中挑出一个随机数赋予该个体。

3)该个体的2个邻居受中心个体的影响，影响强度用概率q描述。被影响到的个体以同样的规则改变其策略，即仍然从P(c)中挑出一个随机数赋予该个体。参数q将个体的自身适应度考虑到了相互作用中，q=0意味着个体间不进行相互作用，q=1则意味着个体间一定有相互作用即原始BS过程，而在区间(0，1)之间表明个体间存在着部分相互作用。

4)重复以上步骤，直到系统达到稳态为止。

2 结果与讨论

图1显示了一维规则环状网络上个体的合作概率与适应度随时间演化的快照特征。系统尺寸为N=64，收益参数分别为T=1.5，S=0.5，时间步长为初始的6 000步，个体间的作用强度q=1，即中心个体的适应度变化一定会对周围邻居产生影响。其中图1b为重新标度后的适应度，Fitness=fi/(R+S+T+P)∈[0,1]。从图中可以看出策略突变几乎只发生在个体适应度最低的位置及其邻居位置上。在图中适应度越低的个体越接近黑色，而其邻居位置上个体的合作概率也同样显示为黑色。这表明在雪堆博弈中当个体的邻居具有较低的合作概率Pc(倾向于背叛)时个体收益会达到最低。但是随着时间演化，发现适应度最低的个体其邻居会逐渐接近白色(倾向于合作)，系统的整体合作水平会得到提升。此外，图1中还表现出了群体适应度和策略演化的断续平衡[28]行为，为了进一步理解此现象，在后面将会讨论突变活动的雪崩动力学行为。

a中白色表示纯合作(1)，黑色表示纯背叛(0)；b中白色表示最高适应度(1)，黑色表示最低适应度(0)；参数N=64,T=1.5,S=0.5,q=1,时间步长为初始时6 000步。图1 系统中所有个体的状态随时间演化的空间构型Fig.1 Spatial pattern of mutation activity versus time for all agents in the system

为了更好地理解系统的动力学，在图3中统计了所有发生突变的个体的合作概率随时间的演化包括适应度最低的个体及其邻居个体，和它们的平均合作概率。将发生突变的个体的合作概率定义为:crep=(cmin+2cnei)/3。从图中可以看出初始时雪堆博弈中适应度最低的个体其邻居的合作概率也较低。对于雪堆博弈，当系统尺寸足够大时，总会存在一个个体m，其合作概率Pcm接近于0，而其邻居也都具有趋近于 0 的合作概率。极端情况就是一个个体与其邻居进行雪堆博弈时，自己与对手都选择背叛策略(D-D-D)。在这种情况下，中心个体将获取最低的收益。所以，在雪堆博弈下，初始时适应度最低的个体与其邻居都是具有较低合作概率的背叛者。随着时间的演化，这样的个体将从群体中消失。突变过程中将不断导致群体的平均合作概率〈c〉逐步上升。当群体平均合作概率提升之后，若一个新的具有随机合作概率的突变体其合作概率低于群体平均合作概率时，则下一时间步适应度最低个体极有可能就是该突变体的邻居，由此也将导致突变活动的雪崩效应。从图中可以看出当系统达到稳态以后，所有发生突变的个体其平均合作概率crep将收敛于稳定值0.5。由于群体的平均合作概率〈c〉的动力学取决于crep，在系统演化的初始阶段两者行为一致。但是当crep稳定时，群体的平均合作概率〈c〉仍然会持续增加，甚至超过了cmin，这是由于个体的突变活动出现了关联性，整个系统表现出了较高的合作水平。从上述说明可见自组织临界模型的动力学与系统中高水平的合作出现有着紧密的关系。另外，从图3中可以发现作用强度的大小并没有对群体平均合作概率的演化产生较大影响。

T=1.5，S=0.5，q=1 。图2 一维规则环状网络上不同系统尺寸下平均合作概率(〈c〉)的时间序列Fig.2 Time evolution of mean cooperation frequencyon a 1D line with different size N

N=128图3 系统平均合作概率〈c〉，适应度最低个体合作概率cmin，适应度最低个体邻居合作概率cnei，突变个体平均合作概率crep随时间的演化Fig.3 The cooperate probability of the whole system,individuals with the lowest fitness,neighbors of individuals with the lowest fitness,and mutated agents

当系统的合作水平达到稳定值时，我们统计了不同尺寸下的适应度分布d(f)(见图4)。随着系统尺寸增加适应度分布的峰值会降低并且分布相应变宽，群体的适应度都集中分布于一个很小的区间范围。在系统演化过程中群体动力学决定了系统中最小适应度随时间是不断增加的，最后趋于某个阈值fc。当群体的适应度小于最低临界值fc时适应度分布变为零。当系统达到稳态时所有个体的适应度将在临界值fc上，此时适应度最低的个体仍然会改变其策略，其适应度也随之产生变异。如果此时该个体的适应度低于临界值fc，则定义为变异活动雪崩的开始。直到群体的最低适应度再次大于临界值fc时表示此次雪崩终止。将在这次雪崩中发生的变异事件的总数定义为雪崩尺寸M。

在临界适应度fc下，根据上述雪崩的定义进一步研究了系统的雪崩尺寸分布。如图5所示在一维规则环状网络上，N=2 048、fc=3.9时的雪崩尺寸分布，通过拟合发现雪崩尺寸近似表现为幂律分布P(M)∝M-γ，标度指数γ=0.57±0.002。在稳态下我们同时测量了连续变异个体间的距离分布P(X)，其在双对数坐标下也近似表现为幂律分布P(X)∝X-γ，γ=2.73±0.02这表明系统自组织达到了临界状态。在临界状态下，BS机制建立的动力学关联性抑制了非合作策略在系统中的长时间存在，使得群体表现出了较高的合作水平。与一维环上的囚徒困境模型相比[23],雪崩尺寸及最小适应度个体间距离分布的标度指数是不相同的，这说明在这两种不同的博弈模型下由于BS过程的引入所表现出的临界行为不属于同一个普适类。

图4 不同系统尺寸下适应度的分布(q=1)Fig.4 The distribution of fitness for different population size

4 结论

在具有周期性边界条件的一维规则环状网络上，本文引入扩展的Bak-Sneppen(BS)过程描述个体间的竞争，研究了演化雪堆博弈中合作行为的涌现与自组织临界性。通过分析系统的动力学，统计了群体中适应度最低个体及其邻居的合作概率与系统平均合作概率随时间的演化，并分析了群体合作水平提升的原因。由于BS过程会使得演化过程中适应度最低的个体间产生动力学关联性，从而使群体的合作水平有较高的提升。在系统稳定后定义了系统中的雪崩尺寸，即适应度低于临界值后的连续变异事件总数。最后，统计了雪崩尺寸分布和连续变异间的距离分布，发现其具有近似的幂律行为，这表明系统自组织达到了一种临界状态。在临界状态时个体在系统尺度上相互关联，这与系统中高水平合作行为的涌现有着直接的关系。

a中fc=3.9,黑色直线是通过P(M)∝M-γ非线性拟合所得,γ=0.57±0.002；黑色直线是通过P(X)∝X-γ非线性拟合所得，γ=2.73±0.02。图5 一维规则环状网络上雪崩尺寸分布和最低适应度个体间距离分布Fig.5 Distribution of avalanche size and the distance between successive minimum fitness sites on a 1D lattice

[1]Gould S J,Eldredge N.Punctuated equilibria:the tempo and mode of evolution reconsidered [J].Paleobiology,1977,3:115-151.

[2]Bak P,Tang C,Wiesenfeld K.Self-organized criticality:an explanation of the 1/f noise [J].Phys Rev Lett,1987,59:381-384.

[3]Aschwanden M J.Self-Organized Criticality Systems [M].Berlin,Warsaw:Open Academic Press,2013:483.

[4]Wang S J,Hilgetag C,Zhou C S.Sustained activity in hierarchical modular neural networks:self-organized criticality and oscillations [J].Front Comput Neurosci,2011,5:30.

[5]Wang S J,Zhou C.Hierarchical modular structure enhances the robustness of self-organized criticality in neural networks[J].New Journal of Physics,2012,14(2):023005.

[6]Wang S J,Ouyang G,Guang J,et al.Stochastic oscillation in self-organized critical states of small systems:sensitive resting state in neural systems [J].Physical Review Letters,2016,116(1):018101.

[7]Ebel H,Bornholdt S.Coevolutionary games on networks [J].Physical Review E,2002,66(5):056118.

[8]Smith J M.Evolution and the Theory of Games [M].New York:Cambridge University Press,1982.

[9]Hamilton W D.The genetical evolution of social behaviour.II[J].Journal of Theoretical Biology,1964,7(1):17-52.

[10]Wedekind C,Milinski M.Cooperation through image scoring in humans [J].Science,2000,288(5467):850-852.

[11]Ohtsuki H,Iwasa Y.How should we define goodness?—reputation dynamics in indirect reciprocity[J].Journal of Theoretical Biology,2004,231(1):107-120.

[12]Brandt H,Sigmund K.The logic of reprobation:assessment and action rules for indirect reciprocation [J].Journal of Theoretical Biology,2004,231(4):475-486.

[13]Vukov J,Szabó G,Szolnoki A.Cooperation in the noisy case:Prisoner’s dilemma game on two types of regular random graphs[J].Physical Review E,2006,73(6):067103.

[14]Li P P,Ke J,Lin Z,et al.Cooperative behavior in evolutionary snowdrift games with the unconditional imitation rule on regular lattices[J].Physical Review E,2012,85(2):021111.

[15]Vukov J,Szabó G.Evolutionary prisoner’s dilemma game on hierarchical lattices[J].Physical Review E,2005,71(3):036133.

[16]Santos F C,Rodrigues J F,Pacheco J M.Graph topology plays a determinant role in the evolution of cooperation[J].Proceedings of the Royal Society of London B:Biological Sciences,2006,273(1582):51-55.

[17]Santos F C,Pacheco J M,Lenaerts T.Evolutionary dynamics of social dilemmas in structured heterogeneous populations[J].Proceedings of the National Academy of Sciences of the United States of America,2006,103(9):3490-3494.

[18]Santos F C,Pacheco J M.Scale-free networks provide a unifying framework for the emergence of cooperation[J].Physical Review Letters,2005,95(9):098104.

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

[20]Ebel H,Bornholdt S.Coevolutionary games on networks[J].Physical Review E,2002,66(5):056118.

[21] Lim Y F,Chen K,Jayaprakash C.Scale-invariant behavior in a spatial game of prisoners’ dilemma[J].Physical Review E,2002,65(2):026134.

[22] Killingback T,Doebeli M.Self-organized criticality in spatial evolutionary game theory[J].Journal of Theoretical Biology,1998,191(3):335-340.

[23]Park S,Jeong H C.Emergence of cooperation with self-organized criticality[J].Journal of the Korean Physical Society,2012,60(3):311-316.

[24] Li W,Luo Y,Wang Y F,et al.A mean-field Bak-Sneppen model with varying interaction strength[J].Chinese Science Bulletin,2011,56(34):3639-3642.

[25] Doebeli M,Hauert C.Models of cooperation based on the Prisoner′s Dilemma and the Snowdrift game[J].Ecology Letters,2005,8(7):748-766.

[26] Perc M,Wang Z.Heterogeneous aspirations promote cooperation in the prisoner's dilemma game[J].PLoS One,2010,5(12):e15117.

[27]Szabó G,Fath G.Evolutionary games on graphs[J].Physics Reports,2007,446(4):97-216.

[28]Bak P,Sneppen K.Punctuated equilibrium and criticality in a simple model of evolution[J].Physical Review Letters,1993,71(24):4083.

(责任编辑 耿金花)

Self-organized Criticality in Spatial Evolutionary Games

CAO Yajuan,LIU Xusheng,GUAN Jianyue

(School of Physical Science and Technology,Lanzhou University,Lanzhou 730000,China)

We study the emergence of cooperation with self-organized criticality on a one-dimensional lattice by connecting Snowdrift Game and Bak-Sneppen (BS) model.We first calculate the mean cooperation probability of the system by Monte-Carlo simulation and the results show that there is a high level cooperation in the steady state,which is possible because the BS mechanism builds dynamical correlation between the least fit sites.Besides,we also measure the distribution of avalanche size and the distance between successive minimum fitness sites,which are well fit by a power law approximately.The power law distribution we measured shows that the system has reached a critical state.In the critical state the agents are correlated at all scales which closely connected with the high level cooperation in the system.

complex networks; snowdrift game; self-organized criticality; cooperation

1672-3813(2017)01-0015-05；

10.13306/j.1672-3813.2017.01.003

2016-03-16；

2016-05-04

国家自然科学基金(11475074，11135001)；兰州大学中央高校基本科研业务费专项资金(lzujbky-2014-32)

曹亚娟(1991-)，女，宁夏固原人，硕士研究生，主要研究方向为网络演化博弈动力学。

关剑月(1981-)，女，河北邯郸人，博士，副教授，主要研究方向为网络演化博弈动力学。

N941.3

A