小世界網(wǎng)絡(luò)中隨機(jī)游走談判者之間的命名演化博弈

陳光平，張志遠(yuǎn)，郝加波，陳小波

（四川文理學(xué)院物理與機(jī)電工程學(xué)院，四川達(dá)州635000）

小世界網(wǎng)絡(luò)中隨機(jī)游走談判者之間的命名演化博弈

陳光平，張志遠(yuǎn)，郝加波，陳小波

（四川文理學(xué)院物理與機(jī)電工程學(xué)院，四川達(dá)州635000）

提出一個在小世界網(wǎng)絡(luò)中，移動談判者之間命名博弈（Naming Game）模型，研究談判者在進(jìn)行命名博弈的同時進(jìn)行隨機(jī)游走，發(fā)現(xiàn)移動快慢對收斂的時間有重要的影響；還研究了不同詞匯數(shù)、總詞匯數(shù)和談判成功率與談判者運動的關(guān)系。這些研究有助于更好理解移動參與者的群體行為特征，也有助于理解參與者的合作演化行為的產(chǎn)生和維持。

小世界網(wǎng)絡(luò)；動態(tài)網(wǎng)絡(luò)；命名博弈；移動談判者

0 引言

最近幾年，隨著復(fù)雜網(wǎng)絡(luò)科學(xué)的迅猛發(fā)展，復(fù)雜網(wǎng)絡(luò)和社會動力學(xué)行為相結(jié)合的研究越來越受到廣泛關(guān)注[1?4]。人們通?？梢詫⑸鐣妥匀幌到y(tǒng)描述為個體作節(jié)點、個體之間關(guān)系作邊的復(fù)雜網(wǎng)絡(luò)。已有研究表明真實的社會系統(tǒng)和自然系統(tǒng)既不是規(guī)則的也不是完全隨機(jī)的網(wǎng)絡(luò)，而是具有小世界（Small?World）或無標(biāo)度（Scale?Free）特性的網(wǎng)絡(luò)。因此，有必要將社會動力系統(tǒng)抽象為小世界網(wǎng)絡(luò)或者無標(biāo)度網(wǎng)絡(luò)而代替完全規(guī)則或者完全隨機(jī)網(wǎng)絡(luò)。

作為社會動力學(xué)研究領(lǐng)域中一個重要研究方面——命名博弈，最近被研究者進(jìn)行了廣泛研究，主要集中于語言進(jìn)化[5?8]、詞匯競爭[9?14]、談判者信譽(yù)效應(yīng)[15]、談判者有限記憶[16]、網(wǎng)絡(luò)結(jié)構(gòu)對命名博弈達(dá)成一致收斂的影響等[17?18]。

以上研究，均設(shè)想談判者處于靜止不移動狀態(tài)，即談判者之間的關(guān)系是不隨時間變化的靜態(tài)網(wǎng)絡(luò)。而真實世界中，談判者往往處于不停移動的狀態(tài)。他們實際組成了一個動態(tài)復(fù)雜網(wǎng)絡(luò)，最近一些研究者開始探尋這樣一些動態(tài)網(wǎng)絡(luò)的動力學(xué)行為，如移動節(jié)點的交通動力學(xué)[19]、路由策略[20]，也有研究者研究移動交談?wù)咧g達(dá)成收斂一致[21]。

受此啟發(fā)，提出談判者在一個小世界位置網(wǎng)絡(luò)中進(jìn)行命名博弈的同時，處于隨機(jī)移動的模型，即位置是一個固定網(wǎng)絡(luò)，而談判者之間的關(guān)系卻是一個動態(tài)網(wǎng)絡(luò)；通過仿真實驗詳細(xì)研究該模型的動力學(xué)行為：收斂時間與移動速度的關(guān)系，不同詞匯數(shù)、總詞匯數(shù)和談判成功率隨時間的合作演化過程等。通過本文研究，將更加深刻理解移動個體對命名博弈的影響，也為大家正確理解生活中千變?nèi)f化的群體移動和大數(shù)據(jù)個體遷徙對于合作演化所起的作用。

1 模型

在此采用D.Watts和S.Strogatz給出的模型構(gòu)造一個小世界網(wǎng)絡(luò)（Small?World Networks）作為位置網(wǎng)絡(luò)，即每一個節(jié)點代表一個位置，網(wǎng)絡(luò)節(jié)點數(shù)為N，每個節(jié)點隨機(jī)選擇＜k＞/2個節(jié)點作為位置鄰居，并用邊相連，這個位置網(wǎng)絡(luò)是一個靜態(tài)網(wǎng)絡(luò)。假設(shè)初始時每一個位置上有一個談判者，共N個談判者，談判者與談判者的初始鄰居關(guān)系由位置網(wǎng)絡(luò)決定，若他們之間只有一個地理位置的邊相連，則稱為鄰居。在命名博弈進(jìn)行時，命名者不停在位置網(wǎng)絡(luò)上移動（從一個位置移動到鄰居位置上），因此，談判者之間的鄰居關(guān)系隨著時間在變化，即談判者之間的關(guān)系網(wǎng)絡(luò)是一個動態(tài)網(wǎng)絡(luò)。只要兩個位置節(jié)點之間有邊連接，談判者就可以在這些位置之間移動。如果兩個談判者所處位置之間有一個邊相連或者兩個談判者占據(jù)同一個位置，均稱他們互為鄰居關(guān)系；再假設(shè)每個位置節(jié)點可以容納談判者的個數(shù)為無限。命名博弈演化過程如圖1所示。

圖1 命名博弈演化圖

開始時，所有參與者的存儲庫都是空白，在接下來的每一個時間步（t=1，2，…），一對相鄰的參與者被隨機(jī)選擇進(jìn)行交互，其中一個作為發(fā)話者（speaker），另外一個作為接聽者（hearer），交互過程遵循如下規(guī)則：

（1）在每一個時間步，隨機(jī)選擇一個談判者作為說話者（Speaker），在他的鄰居中隨機(jī)選擇一個作為聽話者（Hearer）。假如說話者記憶庫為空，他將發(fā)明一個詞語，將它存儲于自己的記憶庫，并將此詞告訴聽話者；如果聽話者的記憶庫中有這個詞，則他們命名博弈成功，雙方都保留這個詞語，而將其他詞語從記憶庫中刪出；如果聽話者的記憶庫中沒有這個詞語，則他們之間的命名博弈不成功，聽話者只需要把這個詞放入自己的記憶庫，不做其他詞的刪除；假如說話者的記憶庫不為空，他將從記憶庫中隨機(jī)選擇一個詞，然后將此詞告訴聽話者，聽話者查看自己詞庫是否有該詞，如果有，則談判成功，雙方都只保留這個詞而刪除其他所有詞語，談判成功；如果沒有，則只需將此詞加入它的記憶庫即可。

（2）每經(jīng)D個時間步（D定義為衡量運動快慢的參數(shù)，稱為參數(shù)D），隨機(jī)選擇一個談判者，讓他隨機(jī)向其位置鄰居移動一步到下一個位置，移動完成后，重新建立談判者之間的鄰居關(guān)系，例如有的談判者之間走得更近（原來所處位置間沒有邊連接而后來有邊連接）而成為鄰居關(guān)系，而有的談判者之間距離疏遠(yuǎn)（原來所處位置間有邊連接而后來沒有邊連接）而不再是鄰居.重新建立談判者之間的鄰居關(guān)系后，再進(jìn)行一次命名博弈；如果兩個談判者之間有一個位置邊連接或占據(jù)同一個位置，則稱他們互為鄰居。參數(shù)D是我們研究的一個重要物理量，D越大表明移動越慢，D越小表示整體移動越快。

（3）重復(fù)以上兩個步驟，直至達(dá)到所有談判者記憶庫有且只有同一個詞語，則命名博弈結(jié)束。

2 數(shù)值模擬與結(jié)果分析

2.1 收斂時間Tc與參數(shù)D的關(guān)系

采用蒙特卡洛方法（Monte Carlo Method）對該模型進(jìn)行數(shù)值仿真。

圖2所示為該模型的收斂時間隨參數(shù)D的變化。分別取小世界位置網(wǎng)絡(luò)節(jié)點數(shù)和談判者個數(shù)為N= 1 000，2 000，3 000。本小世界網(wǎng)絡(luò)平均度＜k＞=4，所有數(shù)據(jù)點是通過對10個不同小世界網(wǎng)絡(luò)，每個網(wǎng)絡(luò)取100次平均后再平均而得。

圖2 收斂時間Tc與參數(shù)D的函數(shù)關(guān)系

從圖2可以看到D比較小（D=1）時，談判者移動比較快，N=1 000，2 000，3 000的收斂時間都很短，且談判者總數(shù)對收斂時間影響不大；當(dāng)D增加時，談判者移動減慢，收斂時間均在增加，且增長速率隨移動的減慢而放緩，最后幾乎不增長；談判者個數(shù)越多，收斂時間增長率越大，當(dāng)D=400時，N分別為1 000，2 000，3 000時的收斂時間之間的差值較大，而D=1時，N分別為1 000，2 000，3 000時，收斂時間之間的差值非常??；由此可見，加快談判者的移動速度（D減?。梢源蟠罂s短收斂時間，減小談判者總數(shù)對收斂時間的影響。對于這一現(xiàn)象，我們的理解是：當(dāng)參與談判者總數(shù)固定時，運動越快（D越?。?，信息交流越多，談判者之間越容易達(dá)成一致，所以收斂時間越短；如果讓談判者都快速移動起來，盡管談判者總數(shù)增加會使收斂時間增加，但是，快速移動的談判者接觸到不同談判者的機(jī)會增多，在一定程度上可以提高信息交換的效率，所以與移動較慢（D較大）情況相比，會大大減小談判者總數(shù)對收斂時間的影響，于是出現(xiàn)不同談判者總數(shù)的收斂時間之間的差值減小。

2.2 不同詞匯數(shù)Nd與參數(shù)D的關(guān)系

在命名博弈中，不同詞匯數(shù)是指所有談判者中，不同詞匯數(shù)出現(xiàn)的個數(shù)。研究它有利于在人工智能中預(yù)先合理分配每個節(jié)點存儲容量空間，進(jìn)而合理利用資源。圖3是談判者數(shù)和位置網(wǎng)絡(luò)節(jié)點數(shù)N=1 000時，取不同運動參數(shù)D=1，10，100時，平均不同詞匯數(shù)與時間的演化關(guān)系（所有數(shù)據(jù)點是通過對10個不同小世界網(wǎng)絡(luò)，每個網(wǎng)絡(luò)取100次平均后再平均而得。小世界網(wǎng)絡(luò)節(jié)點數(shù)N=1 000，平均度＜k＞=4）。

從圖3可以看出，參數(shù)D越小，運動越快，平均不同詞匯數(shù)隨時間衰減得越快，表明運動參數(shù)D對不同詞匯數(shù)有重要的影響，因此加快談判者移動速度，可大大縮短收斂時間。

圖3 平均不同詞匯數(shù)Nd/N隨時間的演化關(guān)系

2.3 總詞匯數(shù)Nw與參數(shù)D的關(guān)系

總詞匯數(shù)Nw與參數(shù)D的關(guān)系如圖4所示。固定談判者個數(shù)N=1 000，調(diào)整不同的運動參數(shù)所有數(shù)據(jù)點是通過對10個不同小世界網(wǎng)絡(luò)，每個網(wǎng)絡(luò)取100次平均后再平均而得，小世界網(wǎng)絡(luò)節(jié)點數(shù)N=1 000，平均度＜k＞=4。

圖4 平均詞匯數(shù)Nw/N隨時間的演化關(guān)系

由圖4可知，D=1運動較快時，記憶庫存儲的平均詞匯數(shù)（總詞匯數(shù)除以談判者人數(shù)）先增加后迅速減少，加快收斂速度，降低了收斂時間，但是最大平均詞匯數(shù)卻增加。這意味著運動談判者的快速移動，談判者之間交流機(jī)會增大，不僅加快意見達(dá)成一致的收斂，而且過程中信息量（詞匯數(shù)）也得到一定的加大。

2.4 談判成功率S（t）與移動參數(shù)D之間的關(guān)系

圖5為固定位置網(wǎng)絡(luò)數(shù)和談判者數(shù)N=1 000，對不同運動參數(shù)D，命名博弈成功率S（t）隨時間的演化關(guān)系（所有數(shù)據(jù)點是通過對10個不同小世界網(wǎng)絡(luò)，每個網(wǎng)絡(luò)取100次平均后再平均而得。小世界網(wǎng)絡(luò)節(jié)點數(shù)N= 1 000，平均度＜k＞=4）。當(dāng)D=1運動較快時，談判成功率迅速增加到1?？焖俚囊苿雍芸斓玫捷^高的成功率，較高的成功率使得一個詞語很快成為談判者群體中最流行的詞，也可使得系統(tǒng)迅速達(dá)到一致收斂。

圖5 命名博弈成功率S(t)隨時間的演化關(guān)系

3 結(jié)論

本文研究了小世界位置網(wǎng)絡(luò)中，移動談判者之間的命名演化博弈。通過數(shù)值仿真研究，發(fā)現(xiàn)談判者的快速移動既可以加快系統(tǒng)收斂、減少收斂時間，又可以減小談判者參與人數(shù)對收斂時間的影響，還可以增加信息量平均詞匯數(shù)。這些研究結(jié)果與真實生活中的交流系統(tǒng)非常相似，即談判者移動越快，交流機(jī)會越多達(dá)成一致收斂越快，交互信息量越多。這些研究結(jié)果對理解實際社會交互網(wǎng)絡(luò)具有重要的指導(dǎo)意義。

[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(xiàn)á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]周濤，汪秉宏，韓筱璞，等.社會網(wǎng)絡(luò)分析及其在輿情和疫情防控中的應(yīng)用[J].系統(tǒng)工程學(xué)報，2010（25）：742?754.

[12]ZHOU T，F(xiàn)U Z Q，WANG B H.Epidemic dynamics on com?plex networks[J].Prog Natl Sci，2006，16：452?457.

[13]CASTELLANO C，F(xiàn)ORTUNATO 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—），男，四川遂寧人，碩士。主要研究方向為復(fù)雜網(wǎng)絡(luò)、冷原子。

2014?10?20