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

(1. 南京農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，南京 210095； 2. 北京師范大學(xué)系統(tǒng)科學(xué)學(xué)院，北京 100875)

?

空間網(wǎng)絡(luò)的標(biāo)度性質(zhì)對(duì)Naming Game演化行為的影響

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

(1. 南京農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，南京 210095； 2. 北京師范大學(xué)系統(tǒng)科學(xué)學(xué)院，北京 100875)

鑒于社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)對(duì)于信息傳播、共識(shí)形成等社會(huì)行為的重要影響，在有限能量約束條件下，通過(guò)添加距離服從冪律分布的長(zhǎng)程連邊，構(gòu)造出具有標(biāo)度性質(zhì)的空間網(wǎng)絡(luò)。在此空間網(wǎng)絡(luò)上，討論了引入無(wú)意收聽(tīng)機(jī)制的Naming Game 模型的演化行為。研究發(fā)現(xiàn)，存在一個(gè)最優(yōu)的冪指數(shù)，使得該空間網(wǎng)絡(luò)上的Naming Game 模型收斂時(shí)間最短,當(dāng)能量約束足夠大時(shí)，這一最優(yōu)冪指數(shù)趨于1.5附近。本研究說(shuō)明，社會(huì)關(guān)系網(wǎng)絡(luò)中的空間性質(zhì)對(duì)于社會(huì)集體認(rèn)同的形成有很大的影響。

空間網(wǎng)絡(luò)；標(biāo)度性質(zhì)；Naming Game；收斂

0　引言

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

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

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

本文以有限能量約束下的空間網(wǎng)絡(luò)模型為基礎(chǔ)，討論引入空間地理位置因素后的網(wǎng)絡(luò)上的Naming Game模型，特別關(guān)注空間標(biāo)度性質(zhì)對(duì)模型收斂行為的影響。此外，現(xiàn)有的社交網(wǎng)絡(luò)不單單是兩兩交互，而是多人的交互，例如，微信的朋友圈、微博、QQ空間等，一個(gè)用戶發(fā)出的信息，其所有的好友都可以分享。基于此，我們考察的是引入無(wú)意間的收聽(tīng)機(jī)制的Naming Game模型。所謂無(wú)意間的收聽(tīng)機(jī)制，即發(fā)話者發(fā)出的信息，其所有的鄰居都作為接聽(tīng)者可以接收到這個(gè)信息。引入這樣的機(jī)制后的Naming Game模型更容易達(dá)到全局收斂[21]。通過(guò)對(duì)空間網(wǎng)絡(luò)上這個(gè)改進(jìn)的Naming Game模型的研究，發(fā)現(xiàn)存在一個(gè)最優(yōu)的冪指數(shù)γ使得該Naming Game模型的收斂時(shí)間最短。此外，當(dāng)能量約束足夠大時(shí)，使Naming Game 模型收斂最快的最優(yōu)冪指數(shù)γ將趨于1.5附近。同時(shí)，我們也研究了系統(tǒng)中最大的不同詞匯量和最大總詞匯量，與總能量約束和冪指數(shù)γ之間的關(guān)系，研究發(fā)現(xiàn)，給定總能量約束的情況下，存在一個(gè)使得系統(tǒng)中最大總詞匯量最大的最優(yōu)γ值。并且，隨著總能量的增加，這個(gè)最優(yōu)γ值逐漸趨于2附近。

1　模型

1.1建立二維能量約束下的空間網(wǎng)絡(luò)

1)N個(gè)點(diǎn)被排列在一個(gè)周期邊界的二維網(wǎng)格上，每個(gè)節(jié)點(diǎn)與其最近的4個(gè)鄰居建立短程連接；

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

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

圖1給出了二維有限能量約束下的空間網(wǎng)絡(luò)的示意圖。從構(gòu)建網(wǎng)絡(luò)的方式可以看出，空間網(wǎng)絡(luò)模型中包括兩個(gè)參數(shù)：γ和c。其中參數(shù)γ(距離分布的冪指數(shù))能夠?qū)臻g網(wǎng)絡(luò)的結(jié)構(gòu)和功能產(chǎn)生決定性的影響。當(dāng)γ→∞時(shí)，距離最短的邊出現(xiàn)的概率將趨近于1，而長(zhǎng)距離的連邊將缺失，在這種情況下，空間網(wǎng)絡(luò)便與規(guī)則網(wǎng)絡(luò)類似；當(dāng)γ→0時(shí)，不同距離的邊出現(xiàn)的概率相等，任意兩點(diǎn)之間的連接概率相等，在這種情況下，空間網(wǎng)絡(luò)便成為一個(gè)NW小世界網(wǎng)絡(luò)[44]。

1.2引入無(wú)意收聽(tīng)機(jī)制的Naming game模型

在引入無(wú)意收聽(tīng)機(jī)制的Naming game模型中，上述空間網(wǎng)絡(luò)中的N=n×n個(gè)節(jié)點(diǎn)對(duì)應(yīng)著N個(gè)智能體，他們可以和任意一個(gè)鄰居進(jìn)行交互。這N個(gè)智能體對(duì)同一個(gè)目標(biāo)制定一個(gè)特定的名字，最終形成的“目標(biāo)-名字”匹配必須得到所有個(gè)體的共同認(rèn)可。每個(gè)智能體擁有一個(gè)存儲(chǔ)庫(kù)，在這個(gè)存儲(chǔ)庫(kù)里，存放著一批不限制優(yōu)先級(jí)的名字。在初始時(shí)刻，所有智能體的存儲(chǔ)庫(kù)都是空白的。系統(tǒng)的演化規(guī)則即智能體間的交互規(guī)則為：

1) 在每個(gè)時(shí)間步，隨機(jī)選擇一個(gè)個(gè)體i作為發(fā)話者，他所有的鄰居作為接聽(tīng)者，發(fā)話者i從當(dāng)前的存儲(chǔ)庫(kù)里隨機(jī)選擇一個(gè)名字，如果此時(shí)存儲(chǔ)庫(kù)為空，則創(chuàng)造一個(gè)新的名字，并將這個(gè)名字傳遞給接聽(tīng)者。

2) 如果接聽(tīng)者j的存儲(chǔ)庫(kù)里有發(fā)話者i傳遞過(guò)來(lái)的這個(gè)名字，那么交互成功，接下來(lái)交互雙方將各自存儲(chǔ)庫(kù)里的其他名字刪除，僅保留剛剛選擇的這個(gè)名字，只要發(fā)話者i的接聽(tīng)者中至少有一個(gè)個(gè)體與其交互成功，發(fā)話者i就將存儲(chǔ)庫(kù)里的其他名字刪除，保留交互成功的這個(gè)名字。

3) 如果接聽(tīng)者j的存儲(chǔ)庫(kù)里沒(méi)有發(fā)話者i傳遞過(guò)來(lái)的這個(gè)名字，那么交互失敗，接聽(tīng)者將接收到的名字加入自己的存儲(chǔ)庫(kù)。

圖2給出了交互過(guò)程失敗和成功的例子，在圖中，選擇圖1中的節(jié)點(diǎn)i作為發(fā)話者，他的所有鄰居作為接聽(tīng)者，發(fā)話者選擇的名字用下劃線標(biāo)示。圖2a表示失敗的交互，當(dāng)發(fā)話者選擇B并將其傳遞給所有接聽(tīng)者時(shí)，所有接聽(tīng)者的存儲(chǔ)庫(kù)中沒(méi)有相應(yīng)的B，因此交互失敗，同時(shí)接聽(tīng)者將B增加進(jìn)自己新的存儲(chǔ)庫(kù)；圖2b表示成功的交互，當(dāng)發(fā)話者選擇C并將其傳遞給接聽(tīng)者時(shí)，接聽(tīng)者2的存儲(chǔ)庫(kù)擁有相應(yīng)的C，因此交互成功，發(fā)話者和接聽(tīng)者2將自己的存儲(chǔ)庫(kù)中非C的其他字母清空，除接聽(tīng)者2之外的其他的接聽(tīng)者交互失敗，將C加進(jìn)自己的存儲(chǔ)庫(kù)中。

2　模擬結(jié)果

在這個(gè)Naming Game模型中，系統(tǒng)經(jīng)過(guò)一段時(shí)間的演化可以達(dá)到所有個(gè)體共同認(rèn)可一個(gè)名字即達(dá)成共識(shí)的穩(wěn)態(tài)。無(wú)論對(duì)于智能體還是人類來(lái)說(shuō)，在合作和交流中快速達(dá)成共識(shí)很重要。所以，定義達(dá)到穩(wěn)態(tài)的時(shí)間為收斂時(shí)間tc，它是對(duì)系統(tǒng)收斂效率的測(cè)量。首先，在規(guī)模為100×100的二維網(wǎng)格上構(gòu)造空間網(wǎng)絡(luò)。這樣的空間網(wǎng)絡(luò)具有如下特征：在能量約束常數(shù)c不變的情況下，隨著冪指數(shù)γ增加，長(zhǎng)程連邊的長(zhǎng)度越長(zhǎng)，出現(xiàn)的概率越小，由于存在總能量約束，因此長(zhǎng)程連邊的數(shù)量將會(huì)增加；在冪指數(shù)γ不變的情況下，能量約束常數(shù)c增加，會(huì)使得網(wǎng)絡(luò)中的連邊數(shù)量增加。

2.1網(wǎng)絡(luò)結(jié)構(gòu)對(duì)收斂時(shí)間的影響

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

2.2網(wǎng)絡(luò)結(jié)構(gòu)對(duì)不同詞匯量的影響

2.3網(wǎng)絡(luò)結(jié)構(gòu)對(duì)總詞匯量的影響

3　結(jié)論與展望

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

綜上所述，空間結(jié)構(gòu)性質(zhì)是社會(huì)關(guān)系網(wǎng)絡(luò)普遍存在的性質(zhì)，而它所展現(xiàn)出來(lái)的標(biāo)度性質(zhì)對(duì)許多社會(huì)行為有重要影響。本文的工作一方面豐富了網(wǎng)絡(luò)上Naming Game模型的研究；更重要的是從更符合現(xiàn)實(shí)的角度對(duì)Naming Game模型進(jìn)行了研究和改進(jìn)，并特別關(guān)注了社會(huì)網(wǎng)絡(luò)空間結(jié)構(gòu)性質(zhì)對(duì)模型收斂行為和最終穩(wěn)態(tài)的影響。當(dāng)然，在這一研究領(lǐng)域可待研究的問(wèn)題還有很多，例如，結(jié)合社會(huì)標(biāo)簽系統(tǒng)的演化規(guī)律改進(jìn)Naming Game模型，使其能夠更好地模擬現(xiàn)實(shí)，從而進(jìn)一步揭示人類集體認(rèn)同的形成。這樣的研究不但對(duì)于研究語(yǔ)言形成問(wèn)題，而且對(duì)于研究社會(huì)慣例、文化的產(chǎn)生和演化、及其與空間地域性質(zhì)之間的相關(guān)關(guān)系也有很大的理論意義和實(shí)際價(jià)值。

[1]潘向東,楊建梅.Naming Game模型的研究進(jìn)展及應(yīng)用[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 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]黎勇,胡延慶,張晶,等. 空間網(wǎng)絡(luò)綜述[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 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] 鈄斐玲,胡延慶,黎勇,等.空間網(wǎng)絡(luò)上的隨機(jī)游走[J].物理學(xué)報(bào), 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] 黎勇,鈄斐玲,樊瑛,等.二維有限能量約束下最優(yōu)導(dǎo)航問(wèn)題的理論分析[J].物理學(xué)報(bào), 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] 汪小帆, 李翔, 陳關(guān)榮. 網(wǎng)絡(luò)科學(xué)導(dǎo)論[M].北京: 高等教育出版社, 2012.

(責(zé)任編輯李進(jìn))

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

國(guó)家社會(huì)科學(xué)基金(14CTQ044)；國(guó)家自然科學(xué)基金(70974084, 61174150)；北京市優(yōu)秀博士學(xué)位論文指導(dǎo)教師科技項(xiàng)目(20121002704)

莊倩(1984-)，女，黑龍江肇東人，博士，講師，主要研究方向?yàn)閺?fù)雜系統(tǒng)的演化機(jī)理。

N94

A