劉洪娟,馬 躍,周福才

1(中國(guó)科學(xué)院 沈陽(yáng)計(jì)算技術(shù)研究所有限公司,沈陽(yáng) 110168) 2(東北大學(xué) 軟件學(xué)院,沈陽(yáng) 110819)

1 引 言

近年來(lái),隨著人們對(duì)大量實(shí)證網(wǎng)絡(luò)研究的不斷深入,許多復(fù)雜網(wǎng)絡(luò)模型不斷涌出.按照是否考慮邊的權(quán)重,這些網(wǎng)絡(luò)模型可以簡(jiǎn)單分為兩類(lèi),一類(lèi)是無(wú)權(quán)網(wǎng)絡(luò)模型,另一類(lèi)是加權(quán)網(wǎng)絡(luò)模型.無(wú)權(quán)網(wǎng)絡(luò)中比較經(jīng)典的有ER隨機(jī)圖模型[1],WS小世界網(wǎng)絡(luò)[2],NW小世界模型[3]以及無(wú)標(biāo)度網(wǎng)絡(luò)模型BA模型[4].無(wú)權(quán)網(wǎng)絡(luò)模型只描述網(wǎng)絡(luò)節(jié)點(diǎn)之間是否有邊存在,并不能描述節(jié)點(diǎn)之間聯(lián)系的強(qiáng)弱.而在很多實(shí)證網(wǎng)絡(luò)中,網(wǎng)絡(luò)中各節(jié)點(diǎn)相互作用的強(qiáng)度是不同的[5].例如,在Internet網(wǎng)絡(luò)和通信網(wǎng)絡(luò)中,各設(shè)備之間的流量會(huì)存在很大的差別,與非主干網(wǎng)相比,主干網(wǎng)絡(luò)的流量可能會(huì)大很多.在交通網(wǎng)絡(luò)中,主干道的通行量與普通道路的通行量有著非常大的差別[6,7].在社交網(wǎng)絡(luò)中,不同用戶(hù)之間通信的頻率和數(shù)據(jù)量的大小是不同的[8].

最初研究的加權(quán)網(wǎng)絡(luò)是邊權(quán)固定的模型,比較典型的是文獻(xiàn)[9]提出的YJBT模型、文獻(xiàn)[10]提出的ZTZH模型和文獻(xiàn)[11]提出的AK模型.YJBT模型是利用BA模型生成的無(wú)標(biāo)度加權(quán)網(wǎng)絡(luò)模型,為新添加節(jié)點(diǎn)增加連邊時(shí),是以節(jié)點(diǎn)度的大小作為建立連接的概率,演化模型的度分布和強(qiáng)度分布均遵循冪律分布,強(qiáng)度分布的冪指數(shù)與增加連邊的個(gè)數(shù)有關(guān).ZTZH模型將節(jié)點(diǎn)的度和適應(yīng)度結(jié)合起來(lái)確定連邊的權(quán)重.AK模型在網(wǎng)絡(luò)結(jié)構(gòu)的演化中引入連邊權(quán)重的增長(zhǎng),考慮節(jié)點(diǎn)強(qiáng)度在選擇連接節(jié)點(diǎn)中的作用,點(diǎn)強(qiáng)度越大的節(jié)點(diǎn)被連接到的概率越大.這3個(gè)模型考慮了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化,會(huì)為每個(gè)新連邊設(shè)置權(quán)重,但沒(méi)有關(guān)注新節(jié)點(diǎn)和新連邊的引入可能會(huì)引起權(quán)重的變化.例如,一條新路的開(kāi)通會(huì)影響已有道路的交通流量.

考慮加權(quán)網(wǎng)絡(luò)整體結(jié)構(gòu)特征和連邊權(quán)重的變化,文獻(xiàn)[12]提出了一個(gè)加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)模型,即BBV模型.該模型第一次在網(wǎng)絡(luò)拓?fù)溲莼^(guò)程中探討連邊權(quán)重的演化,其節(jié)點(diǎn)度、連邊權(quán)重和節(jié)點(diǎn)強(qiáng)度的分布都符合冪律分布的特點(diǎn),解析求解和數(shù)值模擬結(jié)果均表明,其冪指數(shù)值大小在[2,3]區(qū)間內(nèi).基于BBV網(wǎng)絡(luò)模型,文獻(xiàn)[13]以一個(gè)群組的總體節(jié)點(diǎn)強(qiáng)度作為優(yōu)先連接的概率,提出了一個(gè)基于群組優(yōu)先機(jī)制的加權(quán)網(wǎng)絡(luò)模型.文獻(xiàn)[14]構(gòu)建了一個(gè)優(yōu)先交互網(wǎng)絡(luò)模型,在固定網(wǎng)絡(luò)規(guī)模的情況下,每一個(gè)邊的增加包括邊權(quán)重的增加和優(yōu)先交互的增加.文獻(xiàn)[15]依據(jù)節(jié)點(diǎn)的權(quán)重建立了節(jié)點(diǎn)的能量模型,提出的加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)模型具有較高的集聚系數(shù).文獻(xiàn)[16]提出的加權(quán)網(wǎng)絡(luò)模型具有多個(gè)社團(tuán)結(jié)構(gòu),新節(jié)點(diǎn)和新邊的增加均在隨機(jī)選定的社團(tuán)中進(jìn)行,在增加節(jié)點(diǎn)和邊的同時(shí),還考慮采用淘汰機(jī)制刪除網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊.采用該方法生成的網(wǎng)絡(luò)具有良好的社團(tuán)結(jié)構(gòu)特性.

此外,還有一些學(xué)者提出了有向加權(quán)網(wǎng)絡(luò)的概念,考慮節(jié)點(diǎn)之間連邊的方向性,如Web頁(yè)面跳轉(zhuǎn)網(wǎng)絡(luò)和食物鏈網(wǎng)等.文獻(xiàn)[17]提出一種結(jié)合方向性的加權(quán)網(wǎng)絡(luò)模型,以不用的概率在原有網(wǎng)絡(luò)中或新節(jié)點(diǎn)與已有節(jié)點(diǎn)之間增加連邊,在擇優(yōu)連接中,為新邊的入節(jié)點(diǎn)和出節(jié)點(diǎn)設(shè)置不同的概率.文獻(xiàn)[18]借鑒森林火災(zāi)模型的研究思路,提出一種具有稠密冪律特征的有向加權(quán)網(wǎng)絡(luò)演化模型,在新節(jié)點(diǎn)與網(wǎng)絡(luò)中新增連邊的端點(diǎn)的鄰居節(jié)點(diǎn)之間增加連邊.文獻(xiàn)[19]提出了基于強(qiáng)度的有向加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)模型,分別考慮節(jié)點(diǎn)作為出邊節(jié)點(diǎn)和入邊節(jié)點(diǎn)的概率.實(shí)驗(yàn)結(jié)果表明,強(qiáng)度分布和度分布的冪律指數(shù)與網(wǎng)絡(luò)大小無(wú)關(guān),與基本邊權(quán)重和權(quán)重增加有關(guān).

然而,現(xiàn)有加權(quán)網(wǎng)絡(luò)模型并不能真實(shí)地反映實(shí)際網(wǎng)絡(luò)的演化特征.以社交網(wǎng)絡(luò)為例,每一時(shí)刻,不僅要考慮新用戶(hù)與已有用戶(hù)之間建立好友關(guān)系,還要考慮兩個(gè)已有用戶(hù)之間建立好友關(guān)系.此外,在選擇建立好友關(guān)系的用戶(hù)時(shí),只考慮用戶(hù)的強(qiáng)度,并沒(méi)有考慮用戶(hù)之間的相似程度.為此,基于BBV加權(quán)網(wǎng)絡(luò)模型,本文提出一種結(jié)合相似度的新型網(wǎng)絡(luò)演化模型,該模型改進(jìn)了已有的連邊增長(zhǎng)方式,不僅考慮新節(jié)點(diǎn)與已有節(jié)點(diǎn)之間建立新邊,同時(shí)考慮已有節(jié)點(diǎn)之間建立新邊的情況.該模型提出了節(jié)點(diǎn)之間相似度的概念,改進(jìn)了現(xiàn)有的擇優(yōu)連接機(jī)制,將節(jié)點(diǎn)強(qiáng)度和節(jié)點(diǎn)之間相似度結(jié)合起來(lái)作為節(jié)點(diǎn)被選擇的概率.該模型改進(jìn)了現(xiàn)有的權(quán)重演化機(jī)制,能夠自適應(yīng)地進(jìn)行權(quán)重的動(dòng)態(tài)跟新.理論分析和實(shí)驗(yàn)分析結(jié)果表明,該模型能夠更加準(zhǔn)確地描述實(shí)際網(wǎng)絡(luò),產(chǎn)生的網(wǎng)絡(luò)具有無(wú)標(biāo)度網(wǎng)絡(luò)的特性.

2 新型加權(quán)網(wǎng)絡(luò)模型的設(shè)計(jì)

2.1 相關(guān)研究

一個(gè)包含N個(gè)節(jié)點(diǎn)考慮權(quán)重的復(fù)雜網(wǎng)絡(luò)可以表示為G=(V,E),其中,節(jié)點(diǎn)的集合為V={1,2,…,N},連邊的集合為E∈V×V.假設(shè)εij為節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的連邊,wij為連邊εij的權(quán)重,如果節(jié)點(diǎn)i和j之間沒(méi)有連邊,則wij=0.W=[wij]為對(duì)應(yīng)的權(quán)重矩陣.ki表示第i個(gè)節(jié)點(diǎn)的度,即節(jié)點(diǎn)i與其它節(jié)點(diǎn)之間存在的連邊數(shù).si表示第i個(gè)節(jié)點(diǎn)的強(qiáng)度,定義為:

其中,v(i)為節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)構(gòu)成的集合.

2.2 節(jié)點(diǎn)相似度的定義

現(xiàn)有加權(quán)網(wǎng)絡(luò)模型的演化規(guī)則主要基于強(qiáng)度優(yōu)先連接,即強(qiáng)度大的節(jié)點(diǎn)有更大的概率被選中作為連接節(jié)點(diǎn).然而,這樣的演化規(guī)則不足以描述某些實(shí)際網(wǎng)絡(luò)的變化情況.在社交網(wǎng)絡(luò)中,一個(gè)新用戶(hù)可能不想與最受歡迎的用戶(hù)建立好友關(guān)系,而是選擇與他具有更多相似特征的用戶(hù)建立好友關(guān)系.在科學(xué)家合作網(wǎng)絡(luò)中,一個(gè)新用戶(hù)不會(huì)選擇與合作人數(shù)最多的科學(xué)家建立合作關(guān)系,而會(huì)選擇與他研究方向和研究?jī)?nèi)容相似的科學(xué)家建立合作關(guān)系.為了解決這個(gè)實(shí)際問(wèn)題,本文提出節(jié)點(diǎn)屬性與相似度這兩個(gè)概念,將節(jié)點(diǎn)強(qiáng)度與相似度結(jié)合起來(lái)共同決定連接的概率.

節(jié)點(diǎn)屬性是能夠反映一個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中具有的特征和發(fā)揮的作用的內(nèi)在屬性的值.例如,在社交網(wǎng)絡(luò)中,用戶(hù)的節(jié)點(diǎn)屬性可以是他的年齡、興趣、職業(yè)、工作單位、家鄉(xiāng)、畢業(yè)學(xué)校等.在科學(xué)家合作網(wǎng)絡(luò)中,科學(xué)家的節(jié)點(diǎn)屬性可能是他的學(xué)科、研究方向、就職單位和學(xué)術(shù)兼職等.具有相同節(jié)點(diǎn)屬性的兩個(gè)用戶(hù)建立好友關(guān)系的可能性會(huì)更大.這里,設(shè)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)均包括k個(gè)屬性,節(jié)點(diǎn)n的屬性向量為pn=(pn1,pn2,…,pnk),其中,pni為節(jié)點(diǎn)n的第i個(gè)屬性的值.若節(jié)點(diǎn)n與節(jié)點(diǎn)i的k個(gè)屬性中有h個(gè)屬性的值相等,則節(jié)點(diǎn)n與節(jié)點(diǎn)i的相似度tni定義為:

由相似度的定義可以看出,相似度取值為0～1之間的小數(shù).相似度的值越大,兩個(gè)節(jié)點(diǎn)之間的相似程度越高.

2.3 新型加權(quán)網(wǎng)絡(luò)模型的演化

本文創(chuàng)新性地提出了一個(gè)結(jié)合相似度的具有自適應(yīng)演化機(jī)制的新型加權(quán)網(wǎng)絡(luò)模型,演化規(guī)則如下:

2.3.1 初始設(shè)定

網(wǎng)絡(luò)初始是一個(gè)有m0個(gè)節(jié)點(diǎn)構(gòu)成的全連接網(wǎng)絡(luò),每個(gè)節(jié)點(diǎn)都有一個(gè)屬性向量p,每個(gè)連邊的初始權(quán)重為w0.

2.3.2 改進(jìn)的連邊增長(zhǎng)方式

網(wǎng)絡(luò)中每增加一個(gè)新的節(jié)點(diǎn),會(huì)相應(yīng)地增加新的連邊.在增加新的連邊時(shí),除了在新節(jié)點(diǎn)與已有節(jié)點(diǎn)之間增加連邊,本模型還考慮了在已有節(jié)點(diǎn)之間增加連邊,使得模型更具通用性.每一個(gè)時(shí)間步長(zhǎng)t,會(huì)有一個(gè)新節(jié)點(diǎn)n和m條連邊加入到網(wǎng)絡(luò)中.其中,m=m1+m2,在新節(jié)點(diǎn)與已有節(jié)點(diǎn)之間新增的連邊有m1條,在已有節(jié)點(diǎn)之間新增的連邊有m2條.新增加連邊的權(quán)重也為w0.

2.3.3 改進(jìn)的擇優(yōu)連接機(jī)制

在連邊的增長(zhǎng)中,本模型設(shè)置了擇優(yōu)連接機(jī)制選擇連邊的節(jié)點(diǎn).擇優(yōu)連接概率在考慮節(jié)點(diǎn)強(qiáng)度的基礎(chǔ)上,考慮了節(jié)點(diǎn)之間的相似度,使得模型與實(shí)證網(wǎng)絡(luò)更加接近.

對(duì)于新加入的節(jié)點(diǎn)n,已有節(jié)點(diǎn)i被選擇為與之連接節(jié)點(diǎn)的概率為:

(1)

其中,tni為節(jié)點(diǎn)n與節(jié)點(diǎn)i之間的相似度.這樣確定的擇優(yōu)連接概率同時(shí)兼顧了節(jié)點(diǎn)強(qiáng)度和節(jié)點(diǎn)之間的相似度.

對(duì)于已有的節(jié)點(diǎn),節(jié)點(diǎn)i和節(jié)點(diǎn)j被選擇作為新邊的兩個(gè)節(jié)點(diǎn)的概率為:

(2)

其中,tij為節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的相似度.

2.3.4 提出的權(quán)重自適應(yīng)演化機(jī)制

與BA無(wú)標(biāo)度網(wǎng)絡(luò)模型不同的是,本文引入了連邊權(quán)重的自適應(yīng)動(dòng)態(tài)演化機(jī)制.所有新增加的連邊的權(quán)重都為w0,但是,隨著新節(jié)點(diǎn)和新連邊的加入,已有節(jié)點(diǎn)的強(qiáng)度和已有連邊的權(quán)重會(huì)動(dòng)態(tài)更新.新節(jié)點(diǎn)與已有節(jié)點(diǎn)之間增加連邊的權(quán)重演化與已有節(jié)點(diǎn)之間增加連邊的權(quán)重演化有所不同.

a)新節(jié)點(diǎn)與已有節(jié)點(diǎn)i之間增加新邊,節(jié)點(diǎn)i上新連邊的引入會(huì)重新分配節(jié)點(diǎn)i與已有鄰居節(jié)點(diǎn)之間連邊的權(quán)重.對(duì)于節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)j∈v(i),連邊εij的權(quán)重wij按照如下規(guī)則進(jìn)行演化:

wij→wij+Δwij

(3)

(4)

其中,Δwij為權(quán)重的增加值,δ表示由于增加新邊導(dǎo)致節(jié)點(diǎn)i權(quán)重的額外增加.這里為了研究方便,δ取做常數(shù).δ的值按等比例的方式分配到節(jié)點(diǎn)i及其鄰居節(jié)點(diǎn)之間的各個(gè)連邊上.權(quán)重分配方式如圖1所示.

在圖1中,當(dāng)增加一個(gè)新節(jié)點(diǎn)n時(shí),節(jié)點(diǎn)i被選擇作為與節(jié)點(diǎn)n連接的節(jié)點(diǎn),新的連邊εni的權(quán)重為w0.考慮節(jié)點(diǎn)i有兩個(gè)鄰居節(jié)點(diǎn)j1和j2的情況,連邊εij1和εij2分別獲得權(quán)重增加Δwij1和Δwij2.

因此,節(jié)點(diǎn)i的強(qiáng)度會(huì)依據(jù)以下規(guī)則動(dòng)態(tài)更新:

si→si+w0+δ

(5)

事實(shí)上,當(dāng)δ?w0時(shí),表明節(jié)點(diǎn)i已經(jīng)存在的邊受到新增加連邊的影響很小;當(dāng)δ≈w0時(shí),新連邊對(duì)已有邊的影響是適中的;當(dāng)δ?w0時(shí),新連邊對(duì)已有邊會(huì)帶來(lái)“爆炸性”的影響.

b)已有的兩個(gè)節(jié)點(diǎn)i和j之間增加新邊,由于i和j之間可能已經(jīng)有連邊,這里沒(méi)有權(quán)重的額外增加,即:

wij→wij+w0

si→si+w0

sj→sj+w0

值得注意的是,本節(jié)提出的連邊權(quán)重演化機(jī)制是有實(shí)際應(yīng)用背景的.例如,在航空交通網(wǎng)絡(luò)中,除了在新建立的機(jī)場(chǎng)與已有機(jī)場(chǎng)之間增加航線(xiàn),在已有機(jī)場(chǎng)之間也應(yīng)該增加航線(xiàn),以便滿(mǎn)足游客不斷變化的需求.所以,本文在新節(jié)點(diǎn)和已有節(jié)點(diǎn)之間,以及已有節(jié)點(diǎn)之間同時(shí)增加新邊.這些新增加的航線(xiàn)能夠吸引更多的顧客,同時(shí)會(huì)增加相關(guān)機(jī)場(chǎng)的顧客流量,相應(yīng)地會(huì)增加相鄰航線(xiàn)載客量,與本文在權(quán)重演化中描述的δ和Δwij表示的含義相同.

本節(jié)給出的網(wǎng)絡(luò)模型不僅考慮了增長(zhǎng)和擇優(yōu)連接,而且設(shè)計(jì)了將節(jié)點(diǎn)強(qiáng)度與節(jié)點(diǎn)之間相似度結(jié)合的擇優(yōu)連接概率.理論分析和仿真結(jié)果表明,該網(wǎng)絡(luò)模型中節(jié)點(diǎn)的強(qiáng)度分布和度分布都符合冪律分布.

3 新型加權(quán)網(wǎng)絡(luò)模型的理論分析

本節(jié)將從理論的角度分析提出的加權(quán)網(wǎng)絡(luò)模型具有無(wú)標(biāo)度統(tǒng)計(jì)特性,應(yīng)用文獻(xiàn)[20]提出的平均場(chǎng)理論方法與連續(xù)介質(zhì)理論,研究網(wǎng)絡(luò)演化數(shù)據(jù)中第i個(gè)節(jié)點(diǎn)的狀態(tài)是如何隨時(shí)間演化的,對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的強(qiáng)度分布和度分布分別進(jìn)行解析求解.

3.1 節(jié)點(diǎn)強(qiáng)度分布

加權(quán)網(wǎng)絡(luò)模型的節(jié)點(diǎn)強(qiáng)度服從冪律分布,通過(guò)定理1給出.

證明：每個(gè)時(shí)間步長(zhǎng)t,網(wǎng)絡(luò)中會(huì)增加一個(gè)節(jié)點(diǎn),對(duì)網(wǎng)絡(luò)演化的研究可以通過(guò)研究時(shí)間t時(shí),第i個(gè)節(jié)點(diǎn)強(qiáng)度si(t)和度ki(t)的平均值的演化來(lái)實(shí)現(xiàn).當(dāng)一個(gè)新的節(jié)點(diǎn)n加入到網(wǎng)絡(luò)中時(shí),網(wǎng)絡(luò)中的已有節(jié)點(diǎn)i的強(qiáng)度si(t)會(huì)增加,或者是由于與i直接連接的邊,或者是由于與i的鄰居節(jié)點(diǎn)相連的邊.因此,根據(jù)連續(xù)性理論,將k,s和t均看作連續(xù)變量,節(jié)點(diǎn)強(qiáng)度si(t)的演化方程為:

(6)

其中,第1項(xiàng)為m1條新邊加入時(shí),節(jié)點(diǎn)i與新節(jié)點(diǎn)n建立連邊時(shí)增加的強(qiáng)度;第2項(xiàng)為m1條新邊加入時(shí),節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)j與新節(jié)點(diǎn)n建立連邊時(shí),對(duì)節(jié)點(diǎn)i的強(qiáng)度的增加量.同理,第3項(xiàng)為在已有節(jié)點(diǎn)之間增加m2條新邊時(shí),節(jié)點(diǎn)i的強(qiáng)度的增加量.

由網(wǎng)絡(luò)演化機(jī)制可知,每增加一條連邊,網(wǎng)絡(luò)的強(qiáng)度增加2(w0+δ),網(wǎng)絡(luò)強(qiáng)度的總增加量為∑lsl≈2m(w0+δ)t.公式(6)可以變換為如下表達(dá)式:

(7)

由初始條件si(t=ti)=mw0,ti為節(jié)點(diǎn)i進(jìn)入網(wǎng)絡(luò)的時(shí)刻,可以得到公式(7)的解為:

(8)

定義p(s,t)為網(wǎng)絡(luò)在t時(shí)刻節(jié)點(diǎn)的強(qiáng)度為s的概率.在t時(shí)刻,網(wǎng)絡(luò)中任一節(jié)點(diǎn)的強(qiáng)度小于s的概率可以表述為:

(9)

(10)

對(duì)s求導(dǎo)可得p(s,t)的概率密度函數(shù):

當(dāng)t→∞時(shí),可以得到穩(wěn)態(tài)的強(qiáng)度分布為:

3.2 節(jié)點(diǎn)度分布

加權(quán)網(wǎng)絡(luò)模型的節(jié)點(diǎn)度分布服從冪律分布,通過(guò)定理2給出.

證明：與公式(6)類(lèi)似地,節(jié)點(diǎn)度ki(t)的演化方程為:

(11)

結(jié)合公式(6)和公式(11),可以得到:

(12)

由初始條件si(t=ti)=mw0,ki(t=ti)=m,對(duì)公式(12)兩邊同時(shí)進(jìn)行積分,可以得到:

(13)

p(k)～K-γ

(14)

事實(shí)上,度分布p(k)不是嚴(yán)格遵循冪律分布,但如果進(jìn)行變換K=k-a(a為常數(shù)),p(K)～K-γ嚴(yán)格遵循冪律分布.

證畢.

3.3 冪指數(shù)分析

根據(jù)定理1和定理2給出的冪律分布,當(dāng)網(wǎng)絡(luò)增長(zhǎng)的時(shí)間步足夠大時(shí),即網(wǎng)絡(luò)規(guī)模足夠大時(shí),網(wǎng)絡(luò)大小對(duì)冪律分布的影響可以忽略.因此,節(jié)點(diǎn)度和節(jié)點(diǎn)強(qiáng)度的冪指數(shù)與網(wǎng)絡(luò)規(guī)模大小無(wú)關(guān),而與基本連邊權(quán)重w0和權(quán)重增加δ有關(guān).

(15)

A對(duì)δ的偏導(dǎo)數(shù)為:

(16)

4 新型加權(quán)網(wǎng)絡(luò)模型的實(shí)驗(yàn)驗(yàn)證與結(jié)果分析

本節(jié)給出一組實(shí)驗(yàn)結(jié)果,進(jìn)一步驗(yàn)證理論分析的結(jié)果.初始網(wǎng)絡(luò)包含少量節(jié)點(diǎn),按照第2節(jié)給出的模型不斷增加節(jié)點(diǎn)和邊的個(gè)數(shù),并更新點(diǎn)的權(quán)重和邊的權(quán)重,對(duì)最終生成的網(wǎng)絡(luò)進(jìn)行分析.取初始節(jié)點(diǎn)數(shù)m0為5,每增加1個(gè)節(jié)點(diǎn),引入連邊數(shù)總數(shù)m為3,其中,m1=2,m2=1,初始的連邊權(quán)重w0為1,引入新邊導(dǎo)致的權(quán)重增加值δ=1,經(jīng)過(guò)計(jì)算機(jī)模擬最終生成的網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)N取2000.為了避免單次運(yùn)行結(jié)果的誤差,本節(jié)給出的最終結(jié)果為10次運(yùn)行結(jié)果的平均值.

4.1 無(wú)標(biāo)度特性

本節(jié)驗(yàn)證加權(quán)網(wǎng)絡(luò)的無(wú)標(biāo)度特性.實(shí)驗(yàn)得到的加權(quán)網(wǎng)絡(luò)節(jié)點(diǎn)度分布如圖2所示,節(jié)點(diǎn)強(qiáng)度分布如圖3所示.

圖2 加權(quán)網(wǎng)絡(luò)的節(jié)點(diǎn)度分布圖Fig.2 Degree distribution of the weighted network

從圖2和圖3的結(jié)果圖可以看出,加權(quán)網(wǎng)絡(luò)的節(jié)點(diǎn)度分布和強(qiáng)度分布均符合冪律分布.

為了驗(yàn)證節(jié)點(diǎn)強(qiáng)度與節(jié)點(diǎn)度之間的關(guān)系,給出二者之間的關(guān)系圖如圖4所示.

圖3 加權(quán)網(wǎng)絡(luò)的節(jié)點(diǎn)強(qiáng)度分布圖Fig.3 Distribution of node strength of the weighted network

圖4 節(jié)點(diǎn)強(qiáng)度與度之間的關(guān)系Fig.4 Relationship between node strength and degree

從圖4可以看出,節(jié)點(diǎn)度的值集中在小于30的范圍內(nèi),節(jié)點(diǎn)強(qiáng)度的值集中在小于200的范圍內(nèi).節(jié)點(diǎn)強(qiáng)度與度之間總體呈現(xiàn)為線(xiàn)性關(guān)系,這與公式(13)給出的理論分析結(jié)果一致.

4.2 平均路徑長(zhǎng)度

平均路徑長(zhǎng)度是一個(gè)非常重要的評(píng)估節(jié)點(diǎn)之間距離的性質(zhì).在無(wú)權(quán)網(wǎng)絡(luò)中,兩個(gè)節(jié)點(diǎn)之間的距離可以用連接兩個(gè)節(jié)點(diǎn)的最短路徑的邊數(shù)來(lái)定義,可以用來(lái)度量?jī)蓚€(gè)節(jié)點(diǎn)之間信息傳播的速度.平均路徑長(zhǎng)度(Average Path Length,APL)定義為整個(gè)網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間距離的平均值.一個(gè)網(wǎng)絡(luò)的平均路徑長(zhǎng)度越短,信息在網(wǎng)絡(luò)中傳播的效率越高.

基于加權(quán)網(wǎng)絡(luò)最短路徑的定義,一個(gè)網(wǎng)絡(luò)的平均最短路徑定義為:

(17)

圖5 平均路徑長(zhǎng)度的變化情況Fig.5 Variation of average path length

這里,本文計(jì)算了不同網(wǎng)絡(luò)規(guī)模情況下,加權(quán)網(wǎng)絡(luò)的平均路徑長(zhǎng)度,平均路徑長(zhǎng)度隨節(jié)點(diǎn)數(shù)量增加的變化情況如圖5所示.

從圖5的變化情況可以看出,該加權(quán)網(wǎng)絡(luò)模型的平均路徑長(zhǎng)度與網(wǎng)絡(luò)規(guī)模大小有關(guān),隨著節(jié)點(diǎn)數(shù)量的不斷增加,平均路徑長(zhǎng)度的值也隨之增加.

4.3 平均聚集系數(shù)

聚集系數(shù)用來(lái)考量復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)集團(tuán)化的程度,具體地,它描述的是一個(gè)節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)之間是否連接的情況.一個(gè)節(jié)點(diǎn)的聚集系數(shù)取值在[0,1]范圍之內(nèi).一個(gè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)聚集系數(shù)的平均值稱(chēng)為該網(wǎng)絡(luò)的聚集系數(shù),又稱(chēng)為平均聚集系數(shù)(Average Clustering Coefficient,ACC).

在無(wú)權(quán)網(wǎng)絡(luò)中,將一個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)之間實(shí)際的連邊數(shù)量與這些鄰居節(jié)點(diǎn)之間全連接的連接數(shù)量之比定義為該節(jié)點(diǎn)的聚集系數(shù).具體地,節(jié)點(diǎn)i的聚集系數(shù)定義為:

(18)

其中,ki表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)的數(shù)量,Ei表示節(jié)點(diǎn)i及其鄰居節(jié)點(diǎn)之間實(shí)際連邊的數(shù)量.

基于無(wú)權(quán)網(wǎng)絡(luò)的定義,文獻(xiàn)[21]擴(kuò)展得到了加權(quán)網(wǎng)絡(luò)聚集系數(shù)的定義,即為:

(19)

該定義引入了節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)構(gòu)成的三角形中的兩條邊的權(quán)重wij和wjk,其中aij、ajk和aki表示三角形中3個(gè)節(jié)點(diǎn)之間的連接關(guān)系.si(ki-1)的主要作用是進(jìn)行歸一化處理,這樣才能保證取值在0≤C2w(i)≤1范圍之內(nèi).

這里,本文計(jì)算了在不同網(wǎng)絡(luò)規(guī)模的情況下,加權(quán)網(wǎng)絡(luò)的平均聚集系數(shù),平均聚集系數(shù)隨節(jié)點(diǎn)數(shù)量增加的變化情況如圖6所示.

圖6 平均聚集系數(shù)隨節(jié)點(diǎn)數(shù)量的變化情況Fig.6 Average clustering coefficient of the network

從圖6可以看出,與平均路徑長(zhǎng)度不同,隨著整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的不斷增加,平均聚集系數(shù)的值會(huì)相應(yīng)地減少.

根據(jù)以上實(shí)驗(yàn)仿真結(jié)果,可以得出結(jié)論,本文所提加權(quán)網(wǎng)絡(luò)模型節(jié)點(diǎn)強(qiáng)度分布表現(xiàn)出冪律行為,度分布也表現(xiàn)出冪律行為;隨著網(wǎng)絡(luò)規(guī)模不斷變大,網(wǎng)絡(luò)的平均路徑長(zhǎng)度會(huì)隨之變長(zhǎng),平均聚集系數(shù)會(huì)隨之變小,這使得加權(quán)網(wǎng)絡(luò)表現(xiàn)出小世界特性.在網(wǎng)絡(luò)大小為2000時(shí),網(wǎng)絡(luò)的平均聚集系數(shù)大約為0.18,稍大于BBV網(wǎng)絡(luò)模型的0.15,表明該網(wǎng)絡(luò)更容易聚集,傳播速度會(huì)更快.

5 結(jié) 論

本文提出了一個(gè)能夠更加精確地描述真實(shí)網(wǎng)絡(luò)的加權(quán)網(wǎng)絡(luò)模型.該模型考慮了真實(shí)網(wǎng)絡(luò)的兩個(gè)重要特征:1)網(wǎng)絡(luò)節(jié)點(diǎn)之間建立連邊,僅采用節(jié)點(diǎn)強(qiáng)度作為優(yōu)先連接的概率是不科學(xué)的,兩個(gè)比較相似的節(jié)點(diǎn)之間連接的概率也是很大的;2)網(wǎng)絡(luò)演化中增加連邊時(shí),不僅新節(jié)點(diǎn)與已有節(jié)點(diǎn)之間會(huì)建立連邊,已有節(jié)點(diǎn)之間也會(huì)建立連邊.為此,本文考慮了已有節(jié)點(diǎn)之間增加連邊的情況,引入兩個(gè)節(jié)點(diǎn)之間相似度的概念,將節(jié)點(diǎn)強(qiáng)度與節(jié)點(diǎn)之間相似度結(jié)合在一起,共同決定節(jié)點(diǎn)被選擇連接的概率.理論分析和實(shí)驗(yàn)結(jié)果表明,該加權(quán)網(wǎng)絡(luò)模型具有無(wú)標(biāo)度特性和小世界特性,與現(xiàn)有的網(wǎng)絡(luò)模型相比,能夠更好地揭示現(xiàn)實(shí)世界中各種網(wǎng)絡(luò)的演化機(jī)制,具有廣泛的應(yīng)用前景.