小世界網絡中隨機游走談判者之間的命名演化博弈

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

關鍵詞： 小世界網絡； 動態網絡； 命名博弈； 移動談判者

中圖分類號： TN711?34 文獻標識碼： A 文章編號： 1004?373X（2015）07?0150?03

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，]每個節點隨機選擇[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。本小世界網絡平均度=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，平均度=4）。

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

圖3 平均不同詞匯數[NdN]隨時間的演化關系

2.3 總詞匯數[Nw]與參數D的關系

總詞匯數[Nw]與參數D的關系如圖4所示。固定談判者個數N=1 000，調整不同的運動參數所有數據點是通過對10個不同小世界網絡，每個網絡取100次平均后再平均而得，小世界網絡節點數N=1 000，平均度=4。

圖4 平均詞匯數[NwN]隨時間的演化關系

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

2.4 談判成功率S（t）與移動參數D之間的關系

圖5為固定位置網絡數和談判者數N=1 000，對不同運動參數D，命名博弈成功率S（t）隨時間的演化關系（所有數據點是通過對10個不同小世界網絡，每個網絡取100次平均后再平均而得。小世界網絡節點數N=1 000，平均度=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 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] 周濤， 汪秉宏， 韓筱璞， 等.社會網絡分析及其在輿情和疫情防控中的應用[J].系統工程學報 ，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.