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

關(guān)鍵詞： 小世界網(wǎng)絡(luò)； 動態(tài)網(wǎng)絡(luò)； 命名博弈； 移動談判者

中圖分類號： TN711?34 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2015）07?0150?03

0 引 言

最近幾年，隨著復(fù)雜網(wǎng)絡(luò)科學(xué)的迅猛發(fā)展，復(fù)雜網(wǎng)絡(luò)和社會動力學(xué)行為相結(jié)合的研究越來越受到廣泛關(guān)注[1?4]。人們通常可以將社會和自然系統(tǒng)描述為個體作節(jié)點(diǎn)、個體之間關(guān)系作邊的復(fù)雜網(wǎng)絡(luò)。已有研究表明真實(shí)的社會系統(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)系是不隨時(shí)間變化的靜態(tài)網(wǎng)絡(luò)。而真實(shí)世界中，談判者往往處于不停移動的狀態(tài)。他們實(shí)際組成了一個動態(tài)復(fù)雜網(wǎng)絡(luò)，最近一些研究者開始探尋這樣一些動態(tài)網(wǎng)絡(luò)的動力學(xué)行為，如移動節(jié)點(diǎn)的交通動力學(xué)[19]、路由策略[20]，也有研究者研究移動交談?wù)咧g達(dá)成收斂一致[21]。

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

1 模 型

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

圖1 命名博弈演化圖

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

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

（2） 每經(jīng)D個時(shí)間步（D定義為衡量運(yùn)動快慢的參數(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 收斂時(shí)間[Tc]與參數(shù)[D]的關(guān)系

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

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

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

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

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

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

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

圖3 平均不同詞匯數(shù)[NdN]隨時(shí)間的演化關(guān)系

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

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

圖4 平均詞匯數(shù)[NwN]隨時(shí)間的演化關(guān)系

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

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

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

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

3 結(jié) 論

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

參考文獻(xiàn)

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

[12] ZHOU T， FU Z Q， WANG B H. Epidemic dynamics on complex 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 friendship 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. Asymmetric 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. Transportation 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.