具有雙峰效應(yīng)特性的復(fù)雜網(wǎng)絡(luò)模型研究

劉勝久，李天瑞，珠 杰,3，王紅軍

(1.西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院，成都 611756；2.四川省云計(jì)算與智能技術(shù)高校重點(diǎn)實(shí)驗(yàn)室，成都 611756；3.西藏大學(xué)計(jì)算機(jī)科學(xué)系，拉薩 850000)

具有雙峰效應(yīng)特性的復(fù)雜網(wǎng)絡(luò)模型研究

劉勝久1,2，李天瑞1,2，珠 杰1,2,3，王紅軍1,2

(1.西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院，成都 611756；2.四川省云計(jì)算與智能技術(shù)高校重點(diǎn)實(shí)驗(yàn)室，成都 611756；3.西藏大學(xué)計(jì)算機(jī)科學(xué)系，拉薩 850000)

為解決BA網(wǎng)絡(luò)模型采用增長(zhǎng)與擇優(yōu)處理節(jié)點(diǎn)之間的連接而導(dǎo)致節(jié)點(diǎn)連接數(shù)目無(wú)限增長(zhǎng)等不足，通過(guò)對(duì)BA網(wǎng)絡(luò)模型的節(jié)點(diǎn)連接策略改進(jìn)，即通過(guò)引入節(jié)點(diǎn)最大連接數(shù)目，設(shè)置新增節(jié)點(diǎn)連接數(shù)目亞線性增長(zhǎng)并采用Logistic函數(shù)得到了一種度分布具有雙峰效應(yīng)特性的BE網(wǎng)絡(luò)模型，并給出了其若干性質(zhì)。該模型可應(yīng)用于解釋經(jīng)濟(jì)、社會(huì)等現(xiàn)實(shí)生活中的兩極分化現(xiàn)象，而且通過(guò)調(diào)整其參數(shù)可實(shí)現(xiàn)峰的移動(dòng)和縮放，在極限情況下BE模型可退化成BA模型。

復(fù)雜網(wǎng)絡(luò); 無(wú)標(biāo)度; 雙峰效應(yīng); Logistic函數(shù)

0 引言

復(fù)雜網(wǎng)絡(luò)最初屬于圖論的研究范疇，起源于歐拉對(duì)著名的哥尼斯堡七橋問(wèn)題的研究，對(duì)復(fù)雜網(wǎng)絡(luò)的系統(tǒng)性研究可追溯到上世紀(jì)中葉。20世紀(jì)60年代，Erdos和Renyi提出了一種完全隨機(jī)的網(wǎng)絡(luò)模型——ER隨機(jī)網(wǎng)絡(luò)，由此建立起的隨機(jī)圖理論被公認(rèn)為是在數(shù)學(xué)上開創(chuàng)了復(fù)雜網(wǎng)絡(luò)理論的系統(tǒng)性研究[1]，并引領(lǐng)了后續(xù)近半個(gè)世紀(jì)對(duì)復(fù)雜網(wǎng)絡(luò)的研究。ER網(wǎng)絡(luò)模型采用隨機(jī)方式處理節(jié)點(diǎn)之間的連接，由此得到的網(wǎng)絡(luò)度分布呈泊松分布，與真實(shí)網(wǎng)絡(luò)并不完全相符。1999年Barabasi和Albert采用增長(zhǎng)與擇優(yōu)處理節(jié)點(diǎn)之間的連接，提出了BA網(wǎng)絡(luò)模型[2]。BA網(wǎng)絡(luò)模型揭示了復(fù)雜網(wǎng)絡(luò)的無(wú)標(biāo)度性質(zhì)，構(gòu)造出節(jié)點(diǎn)的度分布服從冪律分布的無(wú)標(biāo)度網(wǎng)絡(luò)。由于BA網(wǎng)絡(luò)模型可較好地解釋真實(shí)網(wǎng)絡(luò)的部分特性，受到了人們極大的關(guān)注，對(duì)其改進(jìn)也成為復(fù)雜網(wǎng)絡(luò)研究的重點(diǎn)，并相繼提出了確定性無(wú)標(biāo)度網(wǎng)絡(luò)模型[3]、局域演化網(wǎng)絡(luò)模型[4]等多種網(wǎng)絡(luò)模型。BA兩種網(wǎng)絡(luò)模型所對(duì)應(yīng)的小世界網(wǎng)絡(luò)節(jié)點(diǎn)度分布不同于ER隨機(jī)網(wǎng)絡(luò)的泊松分布，但是這二個(gè)網(wǎng)絡(luò)模型的節(jié)點(diǎn)度分布均只有一個(gè)尖峰，屬于典型的單峰分布。在現(xiàn)實(shí)生活中，常常出現(xiàn)類似于兩極分化的雙峰效應(yīng)現(xiàn)象，而經(jīng)典的網(wǎng)絡(luò)模型對(duì)此難以刻畫。本文通過(guò)對(duì)BA網(wǎng)絡(luò)模型新增節(jié)點(diǎn)連接數(shù)目、既有節(jié)點(diǎn)連接概率及節(jié)點(diǎn)最大連接數(shù)目的改進(jìn)，構(gòu)建出一個(gè)度分布具有雙峰效應(yīng)特性的復(fù)雜網(wǎng)絡(luò)模型，可應(yīng)用于解釋經(jīng)濟(jì)、社會(huì)等領(lǐng)域中的兩極分化現(xiàn)象。

設(shè)圖G=(V,E)是一個(gè)無(wú)向無(wú)環(huán)無(wú)權(quán)圖，其中V={v1,v2,…,vi,…}(1≤i≤|V|)是網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合，E={e1,e2,…,ej,…}(1≤j≤|E|)是網(wǎng)絡(luò)中所有邊的集合，且有E?V×V。|V|表示圖G中的節(jié)點(diǎn)數(shù)目，|E|表示圖G中的邊數(shù)目。

定義1[5]圖G中節(jié)點(diǎn)vi的度d(vi)是指圖中與該節(jié)點(diǎn)直接相連的節(jié)點(diǎn)的數(shù)目。

對(duì)于擁有|V|個(gè)節(jié)點(diǎn)的圖G而言，d(vi)的最小值對(duì)應(yīng)于vi為孤立節(jié)點(diǎn)，即沒(méi)有任何節(jié)點(diǎn)與vi相連，此時(shí)有d(vi)=0；d(vi)的最大值對(duì)應(yīng)于除vi外的所有節(jié)點(diǎn)均與vi相連，此時(shí)有d(vi)=|V|-1，故有0≤d(vi)≤|V|-1。

定義2[5]圖G的節(jié)點(diǎn)度分布是指圖G中節(jié)點(diǎn)度的概率分布或頻率分布(統(tǒng)稱分布)。

度分布是對(duì)一個(gè)圖中節(jié)點(diǎn)度數(shù)的總體描述，對(duì)于隨機(jī)圖而言，其度分布指的是圖中節(jié)點(diǎn)度數(shù)的概率分布。對(duì)于任一非負(fù)整數(shù)d，度數(shù)為d的節(jié)點(diǎn)在圖G中所有節(jié)點(diǎn)中所占的比例P(d)表述為[6]

(1)

顯然有：

(2)

當(dāng)然，也可以用圖G中節(jié)點(diǎn)度的頻數(shù)來(lái)描述度分布，此時(shí)式(1)及式(2)表述為

(3)

(4)

在描述圖G的度分布時(shí)，式(1)與式(3)和式(2)與式(4)的效果是一樣的。

定義3[5]圖G的階數(shù)是指圖G中的節(jié)點(diǎn)數(shù)目|V|。

圖的階數(shù)是描述圖的規(guī)模的重要參數(shù)。

1 研究現(xiàn)狀

1.1 復(fù)雜網(wǎng)絡(luò)模型研究現(xiàn)狀

當(dāng)前對(duì)復(fù)雜網(wǎng)絡(luò)模型的研究主要集中兩個(gè)方面：對(duì)BA無(wú)標(biāo)網(wǎng)絡(luò)模型等經(jīng)典網(wǎng)絡(luò)模型的研究與改進(jìn)及新型網(wǎng)絡(luò)模型的構(gòu)建等。

在對(duì)經(jīng)典網(wǎng)絡(luò)模型的研究方面，王杰等[7]以復(fù)雜網(wǎng)絡(luò)理論為基礎(chǔ)，分析海運(yùn)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)具有無(wú)標(biāo)度特性，并改進(jìn)了BA網(wǎng)絡(luò)模型中的節(jié)點(diǎn)連接概率，通過(guò)實(shí)驗(yàn)驗(yàn)證了海運(yùn)網(wǎng)絡(luò)具有小世界網(wǎng)絡(luò)特征。Galiceanu等[8]對(duì)具有無(wú)標(biāo)度網(wǎng)絡(luò)特性的聚合物進(jìn)行研究，借鑒動(dòng)力學(xué)研究方法，對(duì)松弛度量和靜態(tài)行為進(jìn)行研究，重點(diǎn)分析了剛度參數(shù)和網(wǎng)絡(luò)規(guī)模對(duì)其動(dòng)力特性的影響，尤其是對(duì)其連通性的影響。辜芳琴[9]及曹玉芬[10]等對(duì)BA網(wǎng)絡(luò)模型等無(wú)標(biāo)度網(wǎng)絡(luò)模型從不同的視角進(jìn)行了研究。

在對(duì)新型網(wǎng)絡(luò)模型的研究方面，劉浩然等[11]基于節(jié)點(diǎn)批量到達(dá)的Poisson網(wǎng)絡(luò)模型提出了一種具有容侵優(yōu)化特性的無(wú)標(biāo)度拓?fù)淠Ｐ停⒃跇?gòu)建拓?fù)鋾r(shí)引入剩余能量調(diào)節(jié)因子和節(jié)點(diǎn)度調(diào)節(jié)因子，得到了一種容錯(cuò)性與容侵性兼具且冪律指數(shù)可調(diào)的無(wú)標(biāo)度拓?fù)浣Y(jié)構(gòu)。Emmerich等[12]對(duì)嵌入式無(wú)標(biāo)度網(wǎng)絡(luò)的結(jié)構(gòu)和功能特性進(jìn)行研究，并對(duì)比分析了嵌入式無(wú)標(biāo)度網(wǎng)絡(luò)與非嵌入式無(wú)標(biāo)度網(wǎng)絡(luò)的異同，發(fā)現(xiàn)空間嵌入對(duì)網(wǎng)絡(luò)的化學(xué)距離和脆弱性影響顯著。韓麗[13]及Ruiz等[14]針對(duì)真實(shí)網(wǎng)絡(luò)的特點(diǎn)構(gòu)造出不同的無(wú)標(biāo)度網(wǎng)絡(luò)模型。

復(fù)雜網(wǎng)絡(luò)是復(fù)雜系統(tǒng)的高度抽象，得到了人們極大的關(guān)注。周濤等[15]列出了目前復(fù)雜網(wǎng)絡(luò)研究面臨的最主要的10個(gè)挑戰(zhàn)，對(duì)復(fù)雜網(wǎng)絡(luò)的研究具有重要的指導(dǎo)意義。此外，對(duì)通信網(wǎng)絡(luò)[16]、社交網(wǎng)絡(luò)[17]等其他類型真實(shí)網(wǎng)絡(luò)的研究也是復(fù)雜網(wǎng)絡(luò)研究的重點(diǎn)。

由上表明對(duì)BA無(wú)標(biāo)度網(wǎng)絡(luò)模型等經(jīng)典網(wǎng)絡(luò)模型的持續(xù)改進(jìn)是復(fù)雜網(wǎng)絡(luò)研究中的一個(gè)重要內(nèi)容。其次，如何將經(jīng)典網(wǎng)絡(luò)模型與真實(shí)世界的各項(xiàng)特性結(jié)合起來(lái)，以構(gòu)建出新的網(wǎng)絡(luò)模型是復(fù)雜網(wǎng)絡(luò)研究的另一大趨勢(shì)。

1.2 雙峰效應(yīng)與兩極分化

雙峰效應(yīng)是指化學(xué)元素中鑭系元素的原子半徑隨原子序數(shù)的增長(zhǎng)并不是單調(diào)減小，而是在Eu和Yb處出現(xiàn)峰和在Ce處出現(xiàn)谷的現(xiàn)象[18]。除此之外，原子體積、密度、原子的熱膨脹系數(shù)、第三電離子能、前三個(gè)電離能的總和、原子的電負(fù)性、一些化合物的熔點(diǎn)、沸點(diǎn)等也出現(xiàn)這種效應(yīng)。在現(xiàn)實(shí)生活中，雙峰效應(yīng)突出的表現(xiàn)為經(jīng)濟(jì)、社會(huì)等領(lǐng)域中的兩極分化現(xiàn)象。對(duì)兩極分化的成因，有地區(qū)差距、城鄉(xiāng)差距、分配差異等不同的理論[19]，但都有失偏頗，對(duì)其根源仍莫衷一是。目前較認(rèn)可的說(shuō)法是多種內(nèi)因與外因綜合作用的結(jié)果，是社會(huì)發(fā)展階段的必然，但迄今仍然缺乏直觀、形象的模型或理論對(duì)此給出可信、合理的解釋。

復(fù)雜網(wǎng)絡(luò)的兩極分化現(xiàn)象在真實(shí)網(wǎng)絡(luò)中廣泛存在，典型的代表之一便是萬(wàn)維網(wǎng)[20]。萬(wàn)維網(wǎng)的度分布高度彌散，呈現(xiàn)出重尾分布形式的冪律分布，具有明顯的兩極分化傾向。此外，科學(xué)家合作網(wǎng)絡(luò)中某一節(jié)點(diǎn)的近鄰節(jié)點(diǎn)的介數(shù)分布也具有兩極分化特性[21]，稱為漏斗效應(yīng)，也具備雙峰效應(yīng)的特點(diǎn)。由于BA無(wú)標(biāo)度網(wǎng)絡(luò)可對(duì)復(fù)雜網(wǎng)絡(luò)的兩極分化現(xiàn)象進(jìn)行一定程度的刻畫，對(duì)BA無(wú)標(biāo)度網(wǎng)絡(luò)的研究成為復(fù)雜網(wǎng)絡(luò)研究的重點(diǎn)。

1.3 Logistic函數(shù)

Logistic函數(shù)是一種常見的S形函數(shù)，是Verhulst在研究人口增長(zhǎng)時(shí)命名的，其提出的人口增長(zhǎng)模型被命名為L(zhǎng)ogistic模型，區(qū)別于Malthus模型[22]。

Malthus模型的微分方程形式表述為

(5)

Logistic模型的微分方程形式表述為

(6)

Malthus模型的實(shí)質(zhì)是指數(shù)增長(zhǎng)，而Logistic模型是阻滯增長(zhǎng)。按照Malthus模型，人口數(shù)量是沒(méi)有上限的，即人口可以無(wú)限增長(zhǎng)，這顯然不符合自然規(guī)律。當(dāng)人口數(shù)量不太大時(shí)，Malthus模型——指數(shù)增長(zhǎng)模型可以較好地反映人口增長(zhǎng)的特點(diǎn)[23]，但人口的增長(zhǎng)會(huì)帶來(lái)能源消耗及資源消耗的增長(zhǎng)，而能源與資源的總量是一定的，也即在人口增長(zhǎng)的同時(shí)，自然資源、環(huán)境條件等因素對(duì)人口持續(xù)增長(zhǎng)的阻滯作用會(huì)越來(lái)越顯著。當(dāng)人口數(shù)量較少時(shí)，人口的相對(duì)增長(zhǎng)率可以視為常數(shù)，但當(dāng)人口增加到一定數(shù)量時(shí)，相對(duì)增長(zhǎng)率則會(huì)隨著人口的持續(xù)增加而逐漸減少，此時(shí)Malthus模型并不適用，而Logistic模型——阻滯增長(zhǎng)模型就更為適用了。Logistic模型在其他領(lǐng)域也得到了許多成功的應(yīng)用[24-25]。

本文擬將Logistic模型應(yīng)用于網(wǎng)絡(luò)模型的節(jié)點(diǎn)連接中，對(duì)經(jīng)典的BA網(wǎng)絡(luò)模型進(jìn)行改進(jìn)，構(gòu)建出一個(gè)度分布呈現(xiàn)出雙峰效應(yīng)特性的BE(Bimodal Effect)網(wǎng)絡(luò)模型。

2 具有雙峰效應(yīng)特性的BE復(fù)雜網(wǎng)絡(luò)模型

2.1 經(jīng)典復(fù)雜網(wǎng)絡(luò)模型的不足

經(jīng)典的BA網(wǎng)絡(luò)模型在新增節(jié)點(diǎn)與既有節(jié)點(diǎn)建立連接時(shí)采用擇優(yōu)連接的策略，隱含著一個(gè)假設(shè)：一個(gè)節(jié)點(diǎn)可以與任意多個(gè)節(jié)點(diǎn)建立連接，即節(jié)點(diǎn)的連接數(shù)目是沒(méi)有上限且可以無(wú)限增長(zhǎng)。由此得到的網(wǎng)絡(luò)度分布呈單峰形態(tài)的冪律分布，即節(jié)點(diǎn)的度分布只有一個(gè)峰值。在實(shí)際情況中，這個(gè)假設(shè)是不成立的。一個(gè)節(jié)點(diǎn)維持與另一個(gè)節(jié)點(diǎn)的連接需要消耗能源與資源，而不可能與任意多個(gè)節(jié)點(diǎn)建立連接，必然存在最優(yōu)連接數(shù)目與最大連接數(shù)目。理論與實(shí)驗(yàn)均表明，在真實(shí)網(wǎng)絡(luò)中，這樣的最大連接數(shù)目M是存在的，如在社交網(wǎng)絡(luò)中，鄧巴數(shù)字表明，M=150，被稱為150定律[26]。不同的網(wǎng)絡(luò)有不同的最大連接數(shù)目M，可通過(guò)理論分析、實(shí)驗(yàn)測(cè)試或經(jīng)驗(yàn)知識(shí)等得到M。

此外，在經(jīng)典的BA網(wǎng)絡(luò)模型中，新增節(jié)點(diǎn)自始至終總是選擇固定數(shù)目的既有節(jié)點(diǎn)并與之建立連接。在實(shí)際情況中，這個(gè)假設(shè)也不盡合理。隨著節(jié)點(diǎn)數(shù)目的增長(zhǎng)而導(dǎo)致網(wǎng)絡(luò)規(guī)模的擴(kuò)大，一方面，新增節(jié)點(diǎn)在與既有節(jié)點(diǎn)建立連接時(shí)會(huì)有更多數(shù)目的既有節(jié)點(diǎn)可供選擇，另一方面，更大規(guī)模的網(wǎng)絡(luò)意味著有更多數(shù)目的既有節(jié)點(diǎn)期待與新增節(jié)點(diǎn)建立連接。這樣，新增節(jié)點(diǎn)與既有節(jié)點(diǎn)建立連接的數(shù)目不應(yīng)設(shè)定為常數(shù)C，而應(yīng)設(shè)定為網(wǎng)絡(luò)規(guī)模即節(jié)點(diǎn)數(shù)目|V|的函數(shù)f。但f的增長(zhǎng)速率不能超過(guò)節(jié)點(diǎn)數(shù)目的增長(zhǎng)速率，應(yīng)滿足0

2.2 一種具有雙峰效應(yīng)特性的復(fù)雜網(wǎng)絡(luò)構(gòu)建方法

經(jīng)典的BA網(wǎng)絡(luò)模型的要點(diǎn)一是節(jié)點(diǎn)增長(zhǎng)，二是度數(shù)高的節(jié)點(diǎn)優(yōu)先連接。它是基于初始網(wǎng)絡(luò)G0，逐個(gè)添加節(jié)點(diǎn)，每個(gè)新增節(jié)點(diǎn)均與固定數(shù)目的n個(gè)既有節(jié)點(diǎn)建立連接且優(yōu)先選擇度數(shù)高的節(jié)點(diǎn)建立連接，并添加m個(gè)節(jié)點(diǎn)，該模型可記為BA(G0,n,m)。對(duì)于某個(gè)既有節(jié)點(diǎn)vi而言，若其在原網(wǎng)絡(luò)中的度為d(vi)，則新加入的節(jié)點(diǎn)與其建立連接的概率pi為

(7)

即新增節(jié)點(diǎn)與既有節(jié)點(diǎn)建立連接的概率pi與既有節(jié)點(diǎn)的已有連接數(shù)目成正比，表述為

pi∝d(vi)

(8)

我們對(duì)BA(G0,n,m)模型進(jìn)行3個(gè)方面的改進(jìn)，得到了一個(gè)度分布具有雙峰效應(yīng)特性的BE網(wǎng)絡(luò)模型，記為BE(G0,f,m,M)。其表示基于初始網(wǎng)絡(luò)G0，每個(gè)新增節(jié)點(diǎn)均與f(|V|)個(gè)節(jié)點(diǎn)建立連接，共添加m個(gè)節(jié)點(diǎn)，且新增節(jié)點(diǎn)通過(guò)Logistic函數(shù)選擇既有節(jié)點(diǎn)進(jìn)行連接以及最大連接數(shù)目為M。BA和BE兩種網(wǎng)絡(luò)模型的對(duì)比如表1所示。

表1 BA與BE兩種網(wǎng)絡(luò)模型的對(duì)比Tab.1 Comparison of Network Models between BA and BE

對(duì)BA網(wǎng)絡(luò)模型進(jìn)行3個(gè)方面的改進(jìn)：

1) 設(shè)定網(wǎng)絡(luò)中節(jié)點(diǎn)的最大連接數(shù)目為常數(shù)M，而不是無(wú)窮大；

2)采用Logistic模型連接代替擇優(yōu)連接來(lái)處理新增節(jié)點(diǎn)與既有節(jié)點(diǎn)之間的連接。于是新增節(jié)點(diǎn)與度為d(vi)的既有節(jié)點(diǎn)vi建立連接的概率pi可以表述為

(9)

對(duì)BA網(wǎng)絡(luò)模型及其改進(jìn)模型——BE網(wǎng)絡(luò)模型進(jìn)行分析，可以得到以下結(jié)論。

定理1 BE網(wǎng)絡(luò)模型中新增節(jié)點(diǎn)與既有節(jié)點(diǎn)vi建立連接的概率pi與既有節(jié)點(diǎn)的已有連接數(shù)目d(vi)及剩余連接數(shù)目(M-d(vi))二者的乘積成正比，即：

(10)

證明：對(duì)于任意的既有節(jié)點(diǎn)vi而言，其與新增節(jié)點(diǎn)建立連接的概率等于新增節(jié)點(diǎn)與該節(jié)點(diǎn)建立連接的概率pi，如式(9)所示。對(duì)于式(9)右邊分式的分母有：

(11)

式(11)與節(jié)點(diǎn)vi無(wú)關(guān)，對(duì)任意節(jié)點(diǎn)而言均相等。故pi只與式(9)右邊分式的分子有關(guān)，即為式(10)所示。定理1得證。

定理2 在極限情況下BE網(wǎng)絡(luò)模型與BA網(wǎng)絡(luò)模型是等價(jià)的。

證明：對(duì)BE網(wǎng)絡(luò)模型BE(G0,f,m,M)而言，在極限情況下，當(dāng)M→∞且f取線性函數(shù)——常數(shù)函數(shù)f=n0≤|V0|時(shí)，有：

(12)

此時(shí)BE(G0,f,m,M)可表述為BE(G0,n0,m)，與BA(G0,n,m)等價(jià)，即當(dāng)M→∞且f取常數(shù)函數(shù)時(shí)，BE網(wǎng)絡(luò)模型就是BA網(wǎng)絡(luò)模型。定理2得證。

定理2表明在極限情況下，選擇合適的新增節(jié)點(diǎn)連接數(shù)目、既有節(jié)點(diǎn)連接概率以及節(jié)點(diǎn)最大連接數(shù)目，BE網(wǎng)絡(luò)模型可以退化成BA網(wǎng)絡(luò)模型，即BA網(wǎng)絡(luò)模型是BE網(wǎng)絡(luò)模型的特例。

此外，由于節(jié)點(diǎn)的最大連接數(shù)目為M的前提條件對(duì)任意新增節(jié)點(diǎn)仍然適用，即新增節(jié)點(diǎn)的節(jié)點(diǎn)連接數(shù)目也不能超過(guò)M。于是可以得到定理3。

定理3 對(duì)BE模型BE(G0,f,m,M)而言，f、V0、m、M四者應(yīng)滿足f(|V0|+m)≤M，其中V0為圖G0的節(jié)點(diǎn)集合。

證明：用反證法。假設(shè)f(|V0|+m)>M，對(duì)BE模型BE(G0,f,m,M)而言，當(dāng)初始網(wǎng)絡(luò)G0新增第m個(gè)節(jié)點(diǎn)時(shí)，對(duì)該新增節(jié)點(diǎn)而言，與之相連的節(jié)點(diǎn)數(shù)目為f(|V0|+m)，由于節(jié)點(diǎn)的最大連接數(shù)目為M，而f(|V0|+m)>M，與前提條件矛盾，故假設(shè)不成立。定理3得證。

2.3 具有雙峰效應(yīng)特性的復(fù)雜網(wǎng)絡(luò)仿真分析

從圖1-5可以看出，具有雙峰效應(yīng)特性的復(fù)雜網(wǎng)絡(luò)模型——BE(G0,f,m,M)的度分布不同于隨機(jī)網(wǎng)絡(luò)的泊松分布、小世界網(wǎng)絡(luò)的指數(shù)分布、無(wú)標(biāo)度網(wǎng)絡(luò)的冪律分布或其他形式的單峰分布，而是呈現(xiàn)出雙峰分布的特點(diǎn)，其中BE3尤為顯著。從BE2、BE3、BE4可以看出，在新增節(jié)點(diǎn)數(shù)目m不變的情況下，通過(guò)調(diào)整最大連接數(shù)目M，可以實(shí)現(xiàn)兩個(gè)尖峰的移動(dòng)及縮放，且尖峰的移動(dòng)及縮放與M正相關(guān)；從BE1、BE3、BE5可以看出，在最大連接數(shù)目M不變的情況下，通過(guò)調(diào)整新增節(jié)點(diǎn)數(shù)目m，也可以實(shí)現(xiàn)兩個(gè)尖峰的移動(dòng)及縮放，但尖峰的移動(dòng)及縮放與m負(fù)相關(guān)。通過(guò)合理地設(shè)置并調(diào)整新增節(jié)點(diǎn)數(shù)目及最大連接數(shù)目可以實(shí)現(xiàn)單峰分布及雙峰分布的相互轉(zhuǎn)化。特別地，在極端情況下，雙峰分布也會(huì)退化成單峰分布，如BE5所示，驗(yàn)證了在最大連接數(shù)目M趨近于無(wú)窮且新增節(jié)點(diǎn)連接數(shù)目函數(shù)f為常數(shù)的情況下，BE網(wǎng)絡(luò)模型就是BA無(wú)標(biāo)度網(wǎng)絡(luò)模型。選擇其他類型的亞線性函數(shù)f可以得到類似的結(jié)論。

圖1 BE1= BE(G0,f,5 000,400)的網(wǎng)絡(luò)度分布圖Fig.1 Degree distribution of BE1=BE(G0,f,5 000,400)

圖2 BE2= BE(G0,f,10 000,300)的網(wǎng)絡(luò)度分布圖Fig.2 Degree distribution of BE2=BE(G0,f,10 000,300)

圖3 BE3= BE(G0,f,10 000,400)的網(wǎng)絡(luò)度分布圖Fig.3 Degree distribution of BE3=BE(G0,f,10 000,400)

從圖1-5還可以看出，在節(jié)點(diǎn)連接數(shù)目存在上限、既有節(jié)點(diǎn)采用Logistic函數(shù)與新增節(jié)點(diǎn)建立連接且新增節(jié)點(diǎn)連接數(shù)目亞線性增長(zhǎng)的情況下，出現(xiàn)了類似雙峰效應(yīng)的兩極分化現(xiàn)象。經(jīng)濟(jì)、社會(huì)等領(lǐng)域中兩極分化現(xiàn)象的自然出現(xiàn)、漫長(zhǎng)演化及最終消亡等可以通過(guò)BE網(wǎng)絡(luò)模型中參數(shù)m及M的協(xié)同變化體現(xiàn)出來(lái)。在BE網(wǎng)絡(luò)模型中，其度分布呈現(xiàn)自然的雙峰分布，這可以理解為兩極分化的自然出現(xiàn)；隨著m及M的變化，BE網(wǎng)絡(luò)模型中會(huì)出現(xiàn)峰的移動(dòng)及縮放，這可以理解為兩極分化的漫長(zhǎng)演化；最終，隨著m及M的調(diào)整，BE網(wǎng)絡(luò)演化的最終結(jié)果是雙峰退化成單峰，這可以理解為兩極分化的最終消亡。因此，BE網(wǎng)絡(luò)模型在一定程度可用于刻畫經(jīng)濟(jì)、社會(huì)發(fā)展的歷程中出現(xiàn)的兩極分化現(xiàn)象。

圖4 BE4= BE(G0,f,10 000,500)的網(wǎng)絡(luò)度分布圖Fig.4 Degree distribution of BE4=BE(G0,f,10 000,500)

圖5 BE5= BE(G0,f,20 000,400)的網(wǎng)絡(luò)度分布圖Fig.5 Degree distribution of BE5=BE(G0,f,20 000,400)

3 結(jié)論

經(jīng)典的BA無(wú)標(biāo)度網(wǎng)絡(luò)模型采用增長(zhǎng)與擇優(yōu)連接策略處理節(jié)點(diǎn)之間的連接，隱含著節(jié)點(diǎn)連接數(shù)目可以無(wú)限增長(zhǎng)等方面假設(shè)，與實(shí)際情況不完全相符。本文對(duì)BA網(wǎng)絡(luò)模型進(jìn)行了3個(gè)方面的改進(jìn)：1)引入節(jié)點(diǎn)最大連接數(shù)目；2)設(shè)置新增節(jié)點(diǎn)連接數(shù)目亞線性增長(zhǎng)；3)采用Logistic函數(shù)，從而得到一種度分布具有雙峰效應(yīng)特性的BE網(wǎng)絡(luò)模型，有別于經(jīng)典網(wǎng)絡(luò)模型的泊松分布、指數(shù)分布、冪律分布等其他形式的單峰分布。在極限情況下，BE網(wǎng)絡(luò)模型會(huì)退化成經(jīng)典的BA網(wǎng)絡(luò)模型。BE網(wǎng)絡(luò)模型節(jié)點(diǎn)最大連接數(shù)目及新增節(jié)點(diǎn)數(shù)目等參數(shù)的協(xié)同變化會(huì)導(dǎo)致峰的移動(dòng)及縮放，這可以較好地解釋經(jīng)濟(jì)、社會(huì)等領(lǐng)域中的兩極分化的自然出現(xiàn)、漫長(zhǎng)演化及最終消亡。后續(xù)工作的重點(diǎn)是結(jié)合真實(shí)網(wǎng)絡(luò)的各項(xiàng)特性對(duì)BE網(wǎng)絡(luò)模型進(jìn)行深入的分析研究，包括如何通過(guò)參數(shù)的合理設(shè)置來(lái)分析雙峰移動(dòng)及縮放的具體特點(diǎn)，進(jìn)而實(shí)現(xiàn)對(duì)雙峰分布形態(tài)的精準(zhǔn)調(diào)控以分析雙峰分布未來(lái)的發(fā)展趨勢(shì)。此外，將BE網(wǎng)絡(luò)模型度分布雙峰效應(yīng)的特性與經(jīng)濟(jì)、社會(huì)等領(lǐng)域中的兩極分化結(jié)合起來(lái)研究，分析兩極分化的成因、趨勢(shì)與特點(diǎn)也是后續(xù)研究的重要內(nèi)容。

[1]Erdos P,Renyi A.On random graphs I[J].Publicationes Mathematicae,1959,6:290-297.

[2]Barabasi A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.

[3]Barabasi A L,Ravasz E,Vicsek T.Deterministic scale-free networks[J].Physica A,2001,299(3/4):559-564.

[4]Li X,Chen G R.A local-world evolving network model[J].Physica A,2003,328(1/2):274-286.

[5]張先迪,李正良.圖論及其應(yīng)用[M].北京:高等教育出版社,2005.

[6]Newman M E J.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256.

[7]王杰,李雪.基于改進(jìn)BA模型的海運(yùn)復(fù)雜網(wǎng)絡(luò)演化研究[J].武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版),2013,37(3):496-500.Wang Jie,Li Xue.Analysis of shipping complex network evolving based on improved BA model[J].Journal of Wuhan University of Technology(Transportation Science & Engineering),2013,37(3):496-500.

[8]Galiceanu M,Reis A S,Dolgushev M.Dynamics of semiflexible scale-free polymer networks[J].Journal of Chemical Physics,2014,141(14):144902.

[9]辜芳琴，樊鎖海.BA 無(wú)標(biāo)度網(wǎng)絡(luò)的雙向演化模型[J].暨南大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,34(5):475-478.Gu Fangqin,Fan Suohai.The two-way evolution model of a BA scale-free network[J].Journal of Jinan University(Natural Science & Medicine Edition),2013,34(5):475-478.

[10] 曹玉芬,侯振挺,范偉平.隨機(jī) BA模型的度分布[J].數(shù)學(xué)理論與應(yīng)用,2009,29(2):24-26.Cao Yufen,Hou Zhenting,Fan Weiping.Degree-distribution of a variant of BA model[J].Mathematical theory and Applications,2009,29(2):24-26.

[11] 劉浩然,尹文曉,董明如,等.一種強(qiáng)容侵能力的無(wú)線傳感器網(wǎng)絡(luò)無(wú)標(biāo)度拓?fù)淠Ｐ脱芯縖J].物理學(xué)報(bào),2014,63(9):090503.Liu Haoran,Yin Wenxiao,Dong Mingru,et al.Study on the scale-free topology model with strong intrusion-tolerance ability in wireless sensor networks[J].Acta Physica Sinica,2014,63(9):090503.

[12] Emmerich T,Bunde A,Havlin S.Structural and functional properties of spatially embedded scale-free networks[J].Physical Review E,2014,89 (6):062806.

[13] 韓麗,劉彬,李雅倩,等.能量異構(gòu)的無(wú)線傳感器網(wǎng)絡(luò)加權(quán)無(wú)標(biāo)度拓?fù)溲芯縖J].物理學(xué)報(bào),2014,63(15):150504.Han Li,Liu Bin,Li Yaqian,et al.Studies on weighted scale-free topology in energy heterogeneous wireless sensor network[J].Acta Physica Sinica,2014,63(15):150504.

[14] Ruiz V E,Mitchell D G V,Greening S G,et al.Topology of whole-brain functional MRI networks:Improving the truncated scale-free model[J].Physica A,2014,405:151-158.

[15] 周濤,張子柯,陳關(guān)榮,等.復(fù)雜網(wǎng)絡(luò)研究的機(jī)遇與挑戰(zhàn)[J].電子科技大學(xué)學(xué)報(bào),2014,43(1):1-5.Zhou Tao,Zhang Zike,Chen Guanrong,et al.The opportunities and challenges of complex networks research[J].Journal of University of Electronic Science and Technology of China,2014,43(1):1-5.

[16] Rangan S,Rappaport T S,Erkip E.Millimeter-wave cellular wireless networks:Potentials and challenges[J].Proceedings of the IEEE,2014,102(3):366-385.

[17] Liang Xiaohui,Zhang Kuan,Shen Xuemin,et al.Security and privacy in mobile social networks:Challenges and solutions[J].IEEE Wireless Communications,2014,21(1):33-41.

[18] Mei Bo,Bi Jinshun,Bu Jianhui,et al.Transconductance bimodal effect of PDSOI submicron H-gate MOSFETs[J].Journal of Semiconductors,2013,34(1):014004.

[19] 衛(wèi)興華.我國(guó)當(dāng)前貧富兩極分化現(xiàn)象及其根源[J].西北師大學(xué)報(bào)(社會(huì)科學(xué)版),2012,49(5):1-9.Wei Xinghua.Understanding the polarization between the rich and the poor in China[J].Journal of Northwest Normal University(Social Sciences),2012,49(5):1-9.

[20] Albert R,Jeong H,Barabasi A L.Diameter of the World Wide Web[J].Nature,1999,401(6749):130-131.

[21] 郭世澤,陸哲明.復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論[M].北京:科學(xué)出版社,2012.

[22] Taira K.Introduction to diffusive logistic equations in population dynamics[J].Journal of Applied Mathematics and Computing,2002,9(2):289-347.

[23] Qu J G,Cui Y H,Yang A M,et al.The study for the prediction model of China population growth[J].Journal of Computers,2011,6(10):2076-2083.

[24] Wattimena R K,Kramadibrata S,Sidi I D,et al.Developing coal pillar stability chart using logistic regression[J].International Journal of Rock Mechanics and Mining Sciences,2014,58(2):55-60.

[25] Idlango M A,Gear J A,Shepherd J J.Survival to extinction in a slowly varying harvested logistic population model[J].Applied Mathematics Letters,2014,26(11):1035-1040.

[26] Arnaboldi V,Guazzini A,Passarella A.Egocentric online social networks:Analysis of key features and prediction of tie strength in Facebook[J].Computer Communications,2013,36(10/11):1130-1144.

(責(zé)任編輯 耿金花)

Research on Complex Network Model with the Bimodal Effect

LIU Shengjiu1,2,LI Tianrui1,2,ZHU Jie1,2,3,WANG Hongjun1,2

(1.School of Information Science and Technology,Southwest Jiaotong University,Chengdu 611756,China；2.Key Lab of Cloud Computing and Intelligent Technique,Sichuan Province,Chengdu 611756,China；3.Department of Computer Science,Tibetan University,Lasa 850000,China)

The method of growth and preferential attachment applied by the classic BA scale-free network model to deal with connections between nodes of network will result in unlimited connections and other defects.This paper improves the method of connections of BA network model by introducing the maximum number of connections,having a sub-linear growth in the number of connections of new nodes and using Logistic function.Then a new network model named BE with a bimodal degree distribution is obtained.Its several properties are also provided.This model may be applied to explain the socio-economic polarization in the real world well.Moreover,the shifting and zooming of the peak may be achieved by adjusting its parameters.BE network model will be degenerated to BA network model in the limiting case.

complex network; scale-free; bimodal effect; logistic function

1672-3813(2017)01-0046-06；

10.13306/j.1672-3813.2017.01.007

2015-10-08：

2016-04-28

國(guó)家自然基金項(xiàng)目(61573292，61262058，61152001)；中國(guó)科學(xué)院自動(dòng)化研究所復(fù)雜系統(tǒng)管理與控制重點(diǎn)實(shí)驗(yàn)室開放課題(20110102)

劉勝久(1988-)，男，湖北隨州人，博士，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)，自然語(yǔ)言處理等。

TP393.0

A