空間網絡的標度性質對Naming Game演化行為的影響

莊　倩，沈哲思，何　琳，狄增如

(1. 南京農業大學信息科學技術學院，南京 210095； 2. 北京師范大學系統科學學院，北京 100875)

?

空間網絡的標度性質對Naming Game演化行為的影響

莊倩1，沈哲思2，何琳1，狄增如2

(1. 南京農業大學信息科學技術學院，南京 210095； 2. 北京師范大學系統科學學院，北京 100875)

鑒于社會網絡結構對于信息傳播、共識形成等社會行為的重要影響，在有限能量約束條件下，通過添加距離服從冪律分布的長程連邊，構造出具有標度性質的空間網絡。在此空間網絡上，討論了引入無意收聽機制的Naming Game 模型的演化行為。研究發現，存在一個最優的冪指數，使得該空間網絡上的Naming Game 模型收斂時間最短,當能量約束足夠大時，這一最優冪指數趨于1.5附近。本研究說明，社會關系網絡中的空間性質對于社會集體認同的形成有很大的影響。

空間網絡；標度性質；Naming Game；收斂

0　引言

近年來，關于語言的形成與演化已成為人們感興趣的焦點問題[1]，它關心語言如何產生、以及作為人類交流工具的語言符號如何在個體之間傳播擴散并得到認同等[2-3]。20世紀末，Steels提出了一個簡單的語言動力學模型——Naming Game模型，用來解釋存在交互關系的個體之間如何通過多次互動最終形成集體認同[4]。隨著信息網絡技術的發展，Naming Game模型有著越來越廣泛的應用領域。特別是隨著Web 2.0等社會服務網絡技術的發展，Delicious、Flickr和CiteUlike等社會標簽系統也逐漸發展起來，用戶可以通過分享、點贊、評論以及標注等交互行為逐漸對書簽、圖片、電影等信息資源形成統一的標簽共識。因此，社會標簽系統的演化過程可以用Naming Game 這樣的動力學模型來研究和刻畫，而對Naming Game模型的進一步研究則有助于推動社會標簽系統的發展。由此看來，無論在理論上還是實際應用上，Naming Game 的研究都很有意義。因此，近二十年來Naming Game模型備受關注，涌現出了大量的研究，尤其是關于在一個群體中語言或約定是如何隨著時間的發展而產生和演化的[2-3,5]。已有研究發現，對于Naming Game模型，在沒有任何中介協調的情況下，通過個體間局部的成對交互就能使系統達到全局收斂[6-7]。

2005年，Baronchelli等人在原始Naming Game模型的基礎上提出了簡化模型，這個簡化的模型突破了系統規模的限制，從最初的十個擴展到上千個，他們分析了交互成功率隨時間的變化模式，并揭示了系統的收斂時間、系統達到最大詞匯量的時間以及系統的最大詞匯量與參與者的數量存在的冪律關系[8]，更加突出了時間和詞匯量等個體交互和共識形成的關鍵因素。Baronchelli等人的工作是基于在完全圖上進行交互的假設，但近年來隨著復雜網絡研究的發展[9-10]，人們開始了從復雜網絡的角度研究Naming Game 模型，分析網絡的拓撲性質對系統演化的影響[11-15]。研究表明，基于規則網絡的Naming Game中，詞匯量相對較小，而收斂時間相對較長[16]；網絡的小世界特性則使得Naming Game模型的收斂速度比在規則網絡上更快，而在異質網絡上，由于度不同的點在演化中所起的作用不同，導致了局部較早達到一致狀態，然后由積累了大量詞匯的高度節點將詞匯傳播出去，最終導致系統的全局收斂[17]。除了個體之間交互作用的網絡結構方面的研究外，一些人類社會的典型特征也被引入Naming Game模型中，例如有限的記憶[18]、聲譽效應[19]、無意間的收聽[20]等。

由于結構對系統功能起決定性作用，隨著空間網絡的發展涌現出一批探討空間網絡結構對系統動力學的影響的研究。Yang等[33]在引入了總能量約束的空間網絡上研究了網絡的導航問題，探討了冪指數對網絡平均最短路徑的影響。Li等[34]在Kleinberg 導航模型中添加了總能量的限制，研究發現導航模型在有限能量約束下的最優導航冪指數為網絡維數加一，黎勇等[26]從理論上證明了當網絡規模足夠大且總能量相對較小時，二維有限能量約束下的最優導航冪指數為 3。除了空間網絡上的導航性，學者們也對空間網絡上的Ising模型、隨機游走、同步能力等動力學過程進行了研究[35]，給出了Ising模型相變的臨界溫度與網絡的空間維度和長程連邊的關系[36-38]，隨機游走覆蓋范圍與游走時間的標度關系[39-40]，以及空間網絡和小世界特性對網絡同步能力的影響[41-42]。同時，也有相關學者研究探討了社會網絡的空間性質對社會行為如疾病傳播等的影響[43]。

本文以有限能量約束下的空間網絡模型為基礎，討論引入空間地理位置因素后的網絡上的Naming Game模型，特別關注空間標度性質對模型收斂行為的影響。此外，現有的社交網絡不單單是兩兩交互，而是多人的交互，例如，微信的朋友圈、微博、QQ空間等，一個用戶發出的信息，其所有的好友都可以分享?；诖耍覀兛疾斓氖且霟o意間的收聽機制的Naming Game模型。所謂無意間的收聽機制，即發話者發出的信息，其所有的鄰居都作為接聽者可以接收到這個信息。引入這樣的機制后的Naming Game模型更容易達到全局收斂[21]。通過對空間網絡上這個改進的Naming Game模型的研究，發現存在一個最優的冪指數γ使得該Naming Game模型的收斂時間最短。此外，當能量約束足夠大時，使Naming Game 模型收斂最快的最優冪指數γ將趨于1.5附近。同時，我們也研究了系統中最大的不同詞匯量和最大總詞匯量，與總能量約束和冪指數γ之間的關系，研究發現，給定總能量約束的情況下，存在一個使得系統中最大總詞匯量最大的最優γ值。并且，隨著總能量的增加，這個最優γ值逐漸趨于2附近。

1　模型

1.1建立二維能量約束下的空間網絡

1)N個點被排列在一個周期邊界的二維網格上，每個節點與其最近的4個鄰居建立短程連接；

3) 隨機選擇一個節點i，然后在與節點i的距離為r的所有節點中隨機選擇一個節點j，若節點i和節點j之間沒有連接，則在這兩個節點之間建立一條長程連邊，考慮到能量消耗正比于節點間的距離，假設該長程連邊使總能量消耗；

4) 重復步驟2)和3)，直到總能量耗盡。

圖1給出了二維有限能量約束下的空間網絡的示意圖。從構建網絡的方式可以看出，空間網絡模型中包括兩個參數：γ和c。其中參數γ(距離分布的冪指數)能夠對空間網絡的結構和功能產生決定性的影響。當γ→∞時，距離最短的邊出現的概率將趨近于1，而長距離的連邊將缺失，在這種情況下，空間網絡便與規則網絡類似；當γ→0時，不同距離的邊出現的概率相等，任意兩點之間的連接概率相等，在這種情況下，空間網絡便成為一個NW小世界網絡[44]。

1.2引入無意收聽機制的Naming game模型

在引入無意收聽機制的Naming game模型中，上述空間網絡中的N=n×n個節點對應著N個智能體，他們可以和任意一個鄰居進行交互。這N個智能體對同一個目標制定一個特定的名字，最終形成的“目標-名字”匹配必須得到所有個體的共同認可。每個智能體擁有一個存儲庫，在這個存儲庫里，存放著一批不限制優先級的名字。在初始時刻，所有智能體的存儲庫都是空白的。系統的演化規則即智能體間的交互規則為：

1) 在每個時間步，隨機選擇一個個體i作為發話者，他所有的鄰居作為接聽者，發話者i從當前的存儲庫里隨機選擇一個名字，如果此時存儲庫為空，則創造一個新的名字，并將這個名字傳遞給接聽者。

2) 如果接聽者j的存儲庫里有發話者i傳遞過來的這個名字，那么交互成功，接下來交互雙方將各自存儲庫里的其他名字刪除，僅保留剛剛選擇的這個名字，只要發話者i的接聽者中至少有一個個體與其交互成功，發話者i就將存儲庫里的其他名字刪除，保留交互成功的這個名字。

3) 如果接聽者j的存儲庫里沒有發話者i傳遞過來的這個名字，那么交互失敗，接聽者將接收到的名字加入自己的存儲庫。

圖2給出了交互過程失敗和成功的例子，在圖中，選擇圖1中的節點i作為發話者，他的所有鄰居作為接聽者，發話者選擇的名字用下劃線標示。圖2a表示失敗的交互，當發話者選擇B并將其傳遞給所有接聽者時，所有接聽者的存儲庫中沒有相應的B，因此交互失敗，同時接聽者將B增加進自己新的存儲庫；圖2b表示成功的交互，當發話者選擇C并將其傳遞給接聽者時，接聽者2的存儲庫擁有相應的C，因此交互成功，發話者和接聽者2將自己的存儲庫中非C的其他字母清空，除接聽者2之外的其他的接聽者交互失敗，將C加進自己的存儲庫中。

2　模擬結果

在這個Naming Game模型中，系統經過一段時間的演化可以達到所有個體共同認可一個名字即達成共識的穩態。無論對于智能體還是人類來說，在合作和交流中快速達成共識很重要。所以，定義達到穩態的時間為收斂時間tc，它是對系統收斂效率的測量。首先，在規模為100×100的二維網格上構造空間網絡。這樣的空間網絡具有如下特征：在能量約束常數c不變的情況下，隨著冪指數γ增加，長程連邊的長度越長，出現的概率越小，由于存在總能量約束，因此長程連邊的數量將會增加；在冪指數γ不變的情況下，能量約束常數c增加，會使得網絡中的連邊數量增加。

2.1網絡結構對收斂時間的影響

通過模擬分析，首先探討了長程連邊的數量和長度如何影響系統的收斂時間tc。圖3給出了規模為100×100的網絡上，在取不同的能量約束常數c的情況下，收斂時間tc與冪指數γ之間的關系。從圖中很明顯地看出，收斂時間tc不是冪指數γ的單調函數。在每個能量約束常數c下，都能找到一個使收斂時間達到最優的γ值γopt。并且隨著能量的增加，γopt逐步接近于1.5，冪指數1.5對應的空間網絡具有最大的輸運能力[33]，這樣的網絡結構有利于信息的傳播，增加了收斂速度。這部分結果說明網絡結構對于最優結果的形成是有很大影響的。此外，從圖3中還可以看出，總能量越大，系統的收斂時間越短。這也說明長程連邊的數量越多越有利于全局收斂。

2.2網絡結構對不同詞匯量的影響

2.3網絡結構對總詞匯量的影響

3　結論與展望

本文首先建立了二維有限能量約束下的空間網絡，并在此二維空間網絡上討論了一個引入無意收聽機制的Naming Game模型，在此基礎上，細致研究了空間網絡的標度性質對模型演化行為的影響。我們發現存在一個距離分布的最優冪指數γ，使得該空間網絡上的Naming Game 模型收斂時間最短。進一步，我們從總能量約束的角度討論了空間網絡結構對該最優冪指數γ的影響。研究結果表明，當能量約束足夠大時，使得Naming Game 模型收斂最快的最優冪指數γ最終將穩定在1.5附近，對應的空間網絡具有最大的輸運能力。這個結果說明，適當遠距離的交流能夠促進集體認同的快速形成。局部近距離的交流或者是全局的交流都不利于甚至是阻礙集體認同的形成。同時，我們還研究了總能量約束和冪指數γ對系統中最大的不同詞匯量和最大詞匯量的影響。結果發現，隨著總能量的增加，最大詞匯量的峰值對應的γ值在不斷減小，說明遠距離的交流需要更大的存儲空間，即更高的記憶能力。但當能量約束足夠大時，對應最大詞匯量峰值的γ值穩定在2左右，此時空間網絡具有最小的平均最短路徑。

綜上所述，空間結構性質是社會關系網絡普遍存在的性質，而它所展現出來的標度性質對許多社會行為有重要影響。本文的工作一方面豐富了網絡上Naming Game模型的研究；更重要的是從更符合現實的角度對Naming Game模型進行了研究和改進，并特別關注了社會網絡空間結構性質對模型收斂行為和最終穩態的影響。當然，在這一研究領域可待研究的問題還有很多，例如，結合社會標簽系統的演化規律改進Naming Game模型，使其能夠更好地模擬現實，從而進一步揭示人類集體認同的形成。這樣的研究不但對于研究語言形成問題，而且對于研究社會慣例、文化的產生和演化、及其與空間地域性質之間的相關關系也有很大的理論意義和實際價值。

[1]潘向東,楊建梅.Naming Game模型的研究進展及應用[J].復雜系統與復雜性科學, 2009, 6(2): 87-92.

Pan Xiangdong, Yang Jianmei. A survey of the development and application of Naming Game model [J]. Complex Systems and Complexity Science, 2009, 6(2): 87-92.

[2]Steels L.The synthetic modeling of language origins[J].Evolution of Communication, 1997, 1(1): 1-34.

[3]Kirby S. Natural language from artificial life [J]. Artificial Life, 2002, 8(2): 185-215．

[4]Steels L. A self-organizing spatial vocabulary[J]. Artificial Life, 1995, 2(3): 319-332．

[5]Lu Q, Korniss G, Szymanski B K. Naming games in two-dimensional and small-world-connected random geometric networks[J]. Phys Rev E, 2008, 77: 016111.

[6]Briscoe T. Linguistic Evolution Through Language Acquisition: Formal and Computational Models[M]. Cambridge: Cambridge University Press,2002.

[7]Hurford J, Knight C, Studdert-Kennedy M. Approach to the Evolution of Human Language[M]. Cambridge: Cambridge University Press,1999.

[8]Baronchelli A, Felici M, Caglioti E, et al. Sharp transition towards shared vocabularies in multi-agent systems[J]. Stat Mech, 2005, 6014: 0509075.

[9]Dorogovtsev N, Mendes J F F. Evolution of Networks: from Biological Nets to the Internet and WWW[M]. Oxford: Oxford University Press, 2003.

[10] Pastor-Satorras R, Vespignani A. Evolution and Structure of the Internet: a Statistical Physics Approach[M]. Cambridge: Cambridge University Press, 2004.

[11] Gao Y, Chen G R, Chan R H M. Naming game on networks: let everyone be both speaker and hearer [J]. Scientific Reports, 2014, 6:149.

[12] Dall’Asta L, Baronchelli A, Barrat A, et a1．Agreement dynamics on small-world networks [J]. Europhys Lett, 2006, 73: 969.

[13] Barrat A, Baronchelli A, Dall’Asta L, et al. Agreement dynamics on interaction networks with diverse topologies [J]. Chaos, 2007, 17: 026111.

[14] Baronchelli A, Dall’Asta L, Barrat A, et al. The role of topology on the dynamics of the Naming Game [J].EurPhys J Special Topics, 2007, 143: 233-235.

[15] Liu R R, Wang W X, Lai Y C, et al. Optimal convergence in naming game with geography-basednegotiation on small-world networks [J]. Phys Lett, 2011, 375: 363-367.

[16] Baronchelli A, Dall’Asta L, Barrat A, Loreto V. Topology-induced coarsening in language games[J]. Phys Rev E, 2006, 73: 015102(R).

[17] Dall’Asta L, Baronchelli A, Barrat A, et al. Nonequilibrium dynamics of language games on complex networks [J]. Phys Rev E, 2006, 74: 036105.

[18] 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-536.

[19] Brigatti E. Consequence of reputation in an open-ended naming game[J]. Phys Rev E, 2008, 78: 046108.

[20] Maity S K, Mukherjee A, Tria F, et al. Emergence of fast agreement in an overhearing population: the case of the naming game [J]. Euro Phys Lett, 2013, 101(6): 68004.

[21]Liben-Nowell D, Novak J, Kumar R, et al. Geographic routing in social networks [J]. Proc Natl Acad Sci USA, 2005, 102(33): 11623-11628.

[22] Adamic L, Adar E．How to Search a Social Network [J]. Social Networks, 2005, 27(3): 187-203.

[23]Lambiotte R, Blondel V D, De Kerchove C, et al, Geographical dispersal of mobile communication networks [J]. Physica A, 2008, 387: 5317-5325.

[24] Yook S H, Jeong H, Barabási A L. Modeling the Internet's large-scale topology [J]. Proc Natl Acad Sci USA, 2002, 99: 13382-13386.

[25]黎勇,胡延慶,張晶,等. 空間網絡綜述[J].復雜系統與復雜性科學, 2010, 7(2/3): 145-163.

Li Yong, Hu Yanqing, Zhang Jing, et al.Review on spatial networks[J]. Complex Systems and Complexity Science, 2010, 7(2/3): 145-163.

[26] 鈄斐玲,胡延慶,黎勇,等.空間網絡上的隨機游走[J].物理學報, 2012, 61(17): 571-577.

Dou Feiling, Hu Yanqing,Li Yong, et al. Random walks on spatial networks [J]. Acta Physica Sinica, 2012, 61(17): 571-577.

[27] 黎勇,鈄斐玲,樊瑛,等.二維有限能量約束下最優導航問題的理論分析[J].物理學報, 2012, 61(22): 546-551.

Li Yong,Dou Feiling, Fan Ying, et al.Theoretical analysis on optimal navigation with totalenergy restriction in a two-dimensional lattice [J]. ActaPhysicaSinica,2012, 61(22): 546-551.

[28] Viswanathan G M, Buldyrev S V, Havlin S, et al. Optimizing the success of random searches [J]. Nature, 1999, 401: 911-914.

[29] Viswanathan G M,AfanasyevV, Buldyrev S V, et al. Levy fights in random searches [J]. Physica A, 2000, 282: 1-12.

[30] Brockmann D, Hufnagel L, Geisel T. The scaling laws of human travel [J]. Nature, 2006, 439: 462-465.

[31] Shlesinger M F. The structure of suspended graphene sheets [J]. Nature, 2006, 2: 60-63.

[32] Gonzalez M C, Hidalgo C A, Barabási A L. Understanding individual human mobility patterns [J]. Nature, 2008, 453: 779-782.

[33] Yang H, Nie Y C, Zeng A, et al. Scaling properties in spatial networks and their effects on topology and traffic dynamics [J]. Euro Phys Lett, 2010, 89: 58002.

[34] Li G, Reis S D S, Moreira A A, et al． Towards design principles for optimal transport networks [J]. Phys Rev E, 2010, 104: 018701.

[35] Barthélemy M. Spatial networks [J]. Physics Reports, 2011, 499: 1-101.

[36] Barrat A, Weigt M. On the properties of small-world network models [J]. Euro Phys J B, 2000, 13: 547.

[37] Barthélemy M, Flammini A. Optimal traffic networks [J]. J Stat Mech, 2006, L07002.

[38] Bradde S, Caccioli F, Dall’asta L, et al. Critical fluctuations in spatial complex networks [J]. Phys Rev Lett, 2010, 104: 218701.

[39] Jespersen S, Sokolov I M, Blumen A. Relaxation properties of small-world networks [J]. Phys Rev E, 2000, 62: 4405-4408.

[40] Monasson R. Diffusion, localization and dispersion relations on small-world lattices [J]. Euro Phys B, 1999, 12: 555-567.

[41] Chowdhury D, Cross M C. Synchronization of oscillators with long range power law interactions [J]. Phys Rev E, 2010, 82:016205．

[42] Zeng A, Zhou D, Hu Y Q, et al. Dynamics on spatial networks and the effect of distance coarse graining [J]. Physica A, 2011, 390(2122): 3962-3969.

[43] Murray J D. Mathematical Biology[M]. New York: Springer， 1993： 315-379.

[44]Newman M E J, Watts D J. Renormalization group analysis of the small-world network model [J]. Phys Lett A, 1999, 263: 341-346.

[45] 汪小帆, 李翔, 陳關榮. 網絡科學導論[M].北京: 高等教育出版社, 2012.

(責任編輯李進)

Effects of Geographic Scaling Property on the Evolution of Naming Game

ZHUANG Qian1, SHEN Zhesi2, HE Lin1, DI Zengru2

(1.College of Information Science and Technology, Nanjing Agricultural University, Nanjing 210095, China;2. School of Systems Science, Beijing Normal University, Beijing 100875, China)

The structure of social networks is of paramount importance in collective behaviors，e.g. information propagation, consensus and formation of social norms. In this paper, a special network is constructed by adding remote links among nodes over lattice graphs with total energy constraints.A power law distribution is used to model the relation between the link probability and the distance.We study the effect of geographic scaling property on the dynamics of Naming Game with a group interaction rule. We find that there exists an optimal parameter value which minimizes the time to converge to global consensus. When the total energy constraint is large enough the optimal parameter value is approximately 1.5. Numerical simulations indicate that the geographic scaling property in social network plays an important role in the emergence of social collective behavior and rules.

spatial networks； scaling property； Naming Game； convergence

1672-3813(2016)03-0019-07；DOI:10.13306/j.1672-3813.2016.03.003

2015-03-03；

2015-05-21

國家社會科學基金(14CTQ044)；國家自然科學基金(70974084, 61174150)；北京市優秀博士學位論文指導教師科技項目(20121002704)

莊倩(1984-)，女，黑龍江肇東人，博士，講師，主要研究方向為復雜系統的演化機理。

N94

A