小世界网络中随机游走谈判者之间的命名演化博弈

陈光平，张志远，郝加波，陈小波

（四川文理学院物理与机电工程学院，四川达州635000）

小世界网络中随机游走谈判者之间的命名演化博弈

陈光平，张志远，郝加波，陈小波

（四川文理学院物理与机电工程学院，四川达州635000）

提出一个在小世界网络中，移动谈判者之间命名博弈（Naming Game）模型，研究谈判者在进行命名博弈的同时进行随机游走，发现移动快慢对收敛的时间有重要的影响；还研究了不同词汇数、总词汇数和谈判成功率与谈判者运动的关系。这些研究有助于更好理解移动参与者的群体行为特征，也有助于理解参与者的合作演化行为的产生和维持。

小世界网络；动态网络；命名博弈；移动谈判者

0 引言

最近几年，随着复杂网络科学的迅猛发展，复杂网络和社会动力学行为相结合的研究越来越受到广泛关注[1⁃4]。人们通常可以将社会和自然系统描述为个体作节点、个体之间关系作边的复杂网络。已有研究表明真实的社会系统和自然系统既不是规则的也不是完全随机的网络，而是具有小世界（Small⁃World）或无标度（Scale⁃Free）特性的网络。因此，有必要将社会动力系统抽象为小世界网络或者无标度网络而代替完全规则或者完全随机网络。

作为社会动力学研究领域中一个重要研究方面——命名博弈，最近被研究者进行了广泛研究，主要集中于语言进化[5⁃8]、词汇竞争[9⁃14]、谈判者信誉效应[15]、谈判者有限记忆[16]、网络结构对命名博弈达成一致收敛的影响等[17⁃18]。

以上研究，均设想谈判者处于静止不移动状态，即谈判者之间的关系是不随时间变化的静态网络。而真实世界中，谈判者往往处于不停移动的状态。他们实际组成了一个动态复杂网络，最近一些研究者开始探寻这样一些动态网络的动力学行为，如移动节点的交通动力学[19]、路由策略[20]，也有研究者研究移动交谈者之间达成收敛一致[21]。

受此启发，提出谈判者在一个小世界位置网络中进行命名博弈的同时，处于随机移动的模型，即位置是一个固定网络，而谈判者之间的关系却是一个动态网络；通过仿真实验详细研究该模型的动力学行为：收敛时间与移动速度的关系，不同词汇数、总词汇数和谈判成功率随时间的合作演化过程等。通过本文研究，将更加深刻理解移动个体对命名博弈的影响，也为大家正确理解生活中千变万化的群体移动和大数据个体迁徙对于合作演化所起的作用。

1 模型

在此采用D.Watts和S.Strogatz给出的模型构造一个小世界网络（Small⁃World Networks）作为位置网络，即每一个节点代表一个位置，网络节点数为N，每个节点随机选择＜k＞/2个节点作为位置邻居，并用边相连，这个位置网络是一个静态网络。假设初始时每一个位置上有一个谈判者，共N个谈判者，谈判者与谈判者的初始邻居关系由位置网络决定，若他们之间只有一个地理位置的边相连，则称为邻居。在命名博弈进行时，命名者不停在位置网络上移动（从一个位置移动到邻居位置上），因此，谈判者之间的邻居关系随着时间在变化，即谈判者之间的关系网络是一个动态网络。只要两个位置节点之间有边连接，谈判者就可以在这些位置之间移动。如果两个谈判者所处位置之间有一个边相连或者两个谈判者占据同一个位置，均称他们互为邻居关系；再假设每个位置节点可以容纳谈判者的个数为无限。命名博弈演化过程如图1所示。

图1 命名博弈演化图

开始时，所有参与者的存储库都是空白，在接下来的每一个时间步（t=1，2，…），一对相邻的参与者被随机选择进行交互，其中一个作为发话者（speaker），另外一个作为接听者（hearer），交互过程遵循如下规则：

（1）在每一个时间步，随机选择一个谈判者作为说话者（Speaker），在他的邻居中随机选择一个作为听话者（Hearer）。假如说话者记忆库为空，他将发明一个词语，将它存储于自己的记忆库，并将此词告诉听话者；如果听话者的记忆库中有这个词，则他们命名博弈成功，双方都保留这个词语，而将其他词语从记忆库中删出；如果听话者的记忆库中没有这个词语，则他们之间的命名博弈不成功，听话者只需要把这个词放入自己的记忆库，不做其他词的删除；假如说话者的记忆库不为空，他将从记忆库中随机选择一个词，然后将此词告诉听话者，听话者查看自己词库是否有该词，如果有，则谈判成功，双方都只保留这个词而删除其他所有词语，谈判成功；如果没有，则只需将此词加入它的记忆库即可。

（2）每经D个时间步（D定义为衡量运动快慢的参数，称为参数D），随机选择一个谈判者，让他随机向其位置邻居移动一步到下一个位置，移动完成后，重新建立谈判者之间的邻居关系，例如有的谈判者之间走得更近（原来所处位置间没有边连接而后来有边连接）而成为邻居关系，而有的谈判者之间距离疏远（原来所处位置间有边连接而后来没有边连接）而不再是邻居.重新建立谈判者之间的邻居关系后，再进行一次命名博弈；如果两个谈判者之间有一个位置边连接或占据同一个位置，则称他们互为邻居。参数D是我们研究的一个重要物理量，D越大表明移动越慢，D越小表示整体移动越快。

（3）重复以上两个步骤，直至达到所有谈判者记忆库有且只有同一个词语，则命名博弈结束。

2 数值模拟与结果分析

2.1 收敛时间Tc与参数D的关系

采用蒙特卡洛方法（Monte Carlo Method）对该模型进行数值仿真。

图2所示为该模型的收敛时间随参数D的变化。分别取小世界位置网络节点数和谈判者个数为N= 1 000，2 000，3 000。本小世界网络平均度＜k＞=4，所有数据点是通过对10个不同小世界网络，每个网络取100次平均后再平均而得。

图2 收敛时间Tc与参数D的函数关系

从图2可以看到D比较小（D=1）时，谈判者移动比较快，N=1 000，2 000，3 000的收敛时间都很短，且谈判者总数对收敛时间影响不大；当D增加时，谈判者移动减慢，收敛时间均在增加，且增长速率随移动的减慢而放缓，最后几乎不增长；谈判者个数越多，收敛时间增长率越大，当D=400时，N分别为1 000，2 000，3 000时的收敛时间之间的差值较大，而D=1时，N分别为1 000，2 000，3 000时，收敛时间之间的差值非常小；由此可见，加快谈判者的移动速度（D减小），可以大大缩短收敛时间，减小谈判者总数对收敛时间的影响。对于这一现象，我们的理解是：当参与谈判者总数固定时，运动越快（D越小），信息交流越多，谈判者之间越容易达成一致，所以收敛时间越短；如果让谈判者都快速移动起来，尽管谈判者总数增加会使收敛时间增加，但是，快速移动的谈判者接触到不同谈判者的机会增多，在一定程度上可以提高信息交换的效率，所以与移动较慢（D较大）情况相比，会大大减小谈判者总数对收敛时间的影响，于是出现不同谈判者总数的收敛时间之间的差值减小。

2.2 不同词汇数Nd与参数D的关系

在命名博弈中，不同词汇数是指所有谈判者中，不同词汇数出现的个数。研究它有利于在人工智能中预先合理分配每个节点存储容量空间，进而合理利用资源。图3是谈判者数和位置网络节点数N=1 000时，取不同运动参数D=1，10，100时，平均不同词汇数与时间的演化关系（所有数据点是通过对10个不同小世界网络，每个网络取100次平均后再平均而得。小世界网络节点数N=1 000，平均度＜k＞=4）。

从图3可以看出，参数D越小，运动越快，平均不同词汇数随时间衰减得越快，表明运动参数D对不同词汇数有重要的影响，因此加快谈判者移动速度，可大大缩短收敛时间。

图3 平均不同词汇数Nd/N随时间的演化关系

2.3 总词汇数Nw与参数D的关系

总词汇数Nw与参数D的关系如图4所示。固定谈判者个数N=1 000，调整不同的运动参数所有数据点是通过对10个不同小世界网络，每个网络取100次平均后再平均而得，小世界网络节点数N=1 000，平均度＜k＞=4。

图4 平均词汇数Nw/N随时间的演化关系

由图4可知，D=1运动较快时，记忆库存储的平均词汇数（总词汇数除以谈判者人数）先增加后迅速减少，加快收敛速度，降低了收敛时间，但是最大平均词汇数却增加。这意味着运动谈判者的快速移动，谈判者之间交流机会增大，不仅加快意见达成一致的收敛，而且过程中信息量（词汇数）也得到一定的加大。

2.4 谈判成功率S（t）与移动参数D之间的关系

图5为固定位置网络数和谈判者数N=1 000，对不同运动参数D，命名博弈成功率S（t）随时间的演化关系（所有数据点是通过对10个不同小世界网络，每个网络取100次平均后再平均而得。小世界网络节点数N= 1 000，平均度＜k＞=4）。当D=1运动较快时，谈判成功率迅速增加到1。快速的移动很快得到较高的成功率，较高的成功率使得一个词语很快成为谈判者群体中最流行的词，也可使得系统迅速达到一致收敛。

图5 命名博弈成功率S(t)随时间的演化关系

3 结论

本文研究了小世界位置网络中，移动谈判者之间的命名演化博弈。通过数值仿真研究，发现谈判者的快速移动既可以加快系统收敛、减少收敛时间，又可以减小谈判者参与人数对收敛时间的影响，还可以增加信息量平均词汇数。这些研究结果与真实生活中的交流系统非常相似，即谈判者移动越快，交流机会越多达成一致收敛越快，交互信息量越多。这些研究结果对理解实际社会交互网络具有重要的指导意义。

[1]ALBERT R，BARABASI A L.Statistical mechanics of complex networks[J].Rev Mod Phys，2002，74（47）：48⁃83.

[2]DOROGOVTSEV S N，MENDES J F F.Evolution of networks [J].Adv Phys，2002，51：1079⁃1187.

[3]Newman M E J.The structure and function of complex net⁃works[J].SIAM Rev，2003，45：167⁃256.

[4]BOCCALETTI S.Complex networks：Structure and dynamics [J].Phys Rep，2006，434：175⁃308.

[5]NOWAK M A.Five rules for the evolution of cooperation[J]. Science，2006，314：1560⁃1563.

[6]DE OLIVEIRA V M，GOMES M A F，TSANG I R.Theoreti⁃cal model for the evolution of the linguistic diversity[J].Physi⁃ca A，2006，361：361⁃370.

[7]ZHANG P P，CHEN K，HE Y，et al.Model and empirical study on some collaboration networks[J].Physica A，2006，360：599⁃616.

[8]FUNK S，SALATHÉM，JANSEN V A A.Modelling the influ⁃ence of human behavior on the spread of infectious diseases：a review[J].Journal of R Soc Interface，2010，7：1247⁃1256.

[9]SZABÓ G，FÁTH G.Evolutionary games on graphs[J].Phys Rep，2007，446：97⁃216.

[10]NEWMAN M E J.Communities，modules and large⁃scale structure in networks[J].Nature Physics 2011，8：25⁃31.

[11]周涛，汪秉宏，韩筱璞，等.社会网络分析及其在舆情和疫情防控中的应用[J].系统工程学报，2010（25）：742⁃754.

[12]ZHOU T，FU Z Q，WANG B H.Epidemic dynamics on com⁃plex networks[J].Prog Natl Sci，2006，16：452⁃457.

[13]CASTELLANO C，FORTUNATO S，LORETO V.Statistical physics of social dynamics[J].Rev Mod Phys，2009，81：591⁃646.

[14]GONZÁLEZ M C，HERRMANN H J，KERTÉSZ J，et al. Community structure and ethnic preferences in school friend⁃ship networks[J].Physica A，2007，379：307⁃316.

[15]BRIGATTI Edgardo.Consequence of reputation in an open⁃ended naming game[J].Phys Review E，2008，78：046108.

[16]WANG W X，LIN B Y，TANG C L，et al.Agreement dynamics of finite⁃memory language games on networks[J].Eur Phys J B，2007，60：529⁃533.

[17]YANG Han⁃xin，WANG Wen⁃xu，WANG Bing⁃hong.Asym⁃metric negotiation in structured language games[J].Phys Rev E，2008，77：027103.

[18]HAO Jia⁃bo，YANG Han⁃xin，LIU Run⁃ran，et al.Effect of geometric distance on agreement dynamics of naming game [J].Chin Phys Letters，2010，27：090202.

[19]YANG Han⁃xin，WANG Wen⁃xu，XIE Yan⁃bo，et a1.Trans⁃portation dynamics on networks of mobile agents[J].Phys Rev E，2011，83：016102.）

[20]YANG Han⁃xin，WANG Wen⁃xu，LAI Ying⁃cheng，et al. Greedy routing on networks of mobile agents[J/OL].[2013⁃12⁃25].http：//www.researchgate.net.

[21]BARONCHELLI Andrea，DIAZ⁃GUILERA Albert.Consensus in networks of mobile communicating agents[J/OL].[2014⁃08⁃13].http：//www.works.bepress.com.

Naming game between mobile agents randomly walking in small⁃world networks

CHEN Guang⁃ping，ZHANG Zhi⁃yuan，HAO Jia⁃bo，CHEN Xiao⁃bo
（School of Physics and Mechanical&Electronic Engineering，Sichuan University of Art and Sciences，Dazhou 635000，China）

A model of naming game between mobile agents in small⁃world networks is proposed.It is found that the mobile velocity play an important role in the convergence time by investigating the phenomenon that the agents make random walk while they are playing naming⁃game.The relations of different names，total names and success rate with mobile velocity are investigated in detail.All of these results may be contributed to understanding the collective behavior of mobile agents，and the emergence and maintain of cooperative game as well.

small⁃world network；dynamic network；naming game；mobile agent

TN711⁃34

A

1004⁃373X（2015）07⁃0150⁃03

陈光平（1981—），男，四川遂宁人，硕士。主要研究方向为复杂网络、冷原子。

2014⁃10⁃20