王小剛,閆光輝,周 寧

(蘭州交通大學(xué)電子與信息工程學(xué)院,甘肅蘭州 730070)

1 引言

復(fù)雜網(wǎng)絡(luò)是基于圖論的復(fù)雜系統(tǒng)建模方式,已成為涉及自然科學(xué)、社會(huì)科學(xué)和工程學(xué)等諸多鄰域的重要交叉研究課題[1-4].復(fù)雜網(wǎng)絡(luò)研究一般基于某些量化的結(jié)構(gòu)或動(dòng)力學(xué)特性,如度分布、模塊度、相似性、中心性、隨機(jī)游走等[5-9].而復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)呈現(xiàn)出各種復(fù)雜、異構(gòu)甚至是無(wú)序和不確定的情況[10],需要多樣性的網(wǎng)絡(luò)或節(jié)點(diǎn)結(jié)構(gòu)信息度量和分析方式.

信息熵[11]作為度量復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的有力工具近些年日益受到重視.復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)熵基于一定的結(jié)構(gòu)量定義熵,如文獻(xiàn)[1]中給出基于度序列分布的熵,可以用來(lái)評(píng)價(jià)網(wǎng)絡(luò)總體的規(guī)則性,熵越高網(wǎng)絡(luò)越隨機(jī);文獻(xiàn)[12]給出的Wu熵基于節(jié)點(diǎn)度衡量節(jié)點(diǎn)分布均勻程度,熵越大網(wǎng)絡(luò)越均勻;文獻(xiàn)[13]提出介數(shù)熵描述權(quán)重網(wǎng)絡(luò)的結(jié)構(gòu)特性,比度熵能更有效地描述有權(quán)復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)信息;文獻(xiàn)[14-15]基于節(jié)點(diǎn)最短路徑定義距離熵,并討論了極值情況,有助于研究網(wǎng)絡(luò)的構(gòu)造特性.另外,學(xué)者也從復(fù)雜網(wǎng)絡(luò)的代數(shù)特征和動(dòng)力學(xué)特征出發(fā)定義和研究結(jié)構(gòu)熵,如文獻(xiàn)[16-17]基于拉普拉斯矩陣的特征值定義熵,通過(guò)分析節(jié)點(diǎn)移除導(dǎo)致的熵值變化,度量異構(gòu)性及節(jié)點(diǎn)重要性,可以有效發(fā)現(xiàn)網(wǎng)絡(luò)中的關(guān)鍵結(jié)構(gòu)特征;文獻(xiàn)[18]基于指數(shù)鄰接矩陣定義游走熵,有助于揭示網(wǎng)絡(luò)的動(dòng)力學(xué)特性;文獻(xiàn)[19]基于樹(shù)結(jié)構(gòu)和隨機(jī)游走定義復(fù)雜網(wǎng)絡(luò)高維熵,以表示和檢測(cè)復(fù)雜網(wǎng)絡(luò)的真實(shí)結(jié)構(gòu).

以上提到的熵都是宏觀熵.宏觀熵針對(duì)整個(gè)網(wǎng)絡(luò),度量某種結(jié)構(gòu)量的總體分布特性[20].與之相對(duì)應(yīng)的是節(jié)點(diǎn)微觀熵,一般用來(lái)表示節(jié)點(diǎn)的局部結(jié)構(gòu)信息,如文獻(xiàn)[21]給出基于節(jié)點(diǎn)與其他節(jié)點(diǎn)最短距離分布的熵,從而發(fā)現(xiàn)中心節(jié)點(diǎn);文獻(xiàn)[22]提出一種基于鄰域度分布的節(jié)點(diǎn)熵,用于節(jié)點(diǎn)相似性評(píng)價(jià).目前文獻(xiàn)中已有的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)熵主要是宏觀熵,微觀熵比較少.宏觀熵關(guān)注網(wǎng)絡(luò)整體結(jié)構(gòu)信息忽略局部,而現(xiàn)有微觀熵主要基于鄰域交互和最短距離,局限性較大,需要一種節(jié)點(diǎn)熵能從更靈活尺度上度量節(jié)點(diǎn)多層鄰居的分布特征.

基于節(jié)點(diǎn)熵可以構(gòu)造相對(duì)熵來(lái)對(duì)比節(jié)點(diǎn)間的相似性[22-23].節(jié)點(diǎn)相似性是重要的結(jié)構(gòu)特征,有很多重要的用途,如社區(qū)檢測(cè)、鏈路預(yù)測(cè)、節(jié)點(diǎn)分類.常見(jiàn)的相似性方法有:

1)基于共同鄰居的方法[8,24],一般采用節(jié)點(diǎn)對(duì)之間公共鄰居的數(shù)目,公共鄰居的度等結(jié)構(gòu)信息進(jìn)行相似性計(jì)算,如JACCARD算法,共同鄰居算法.這種方法計(jì)算簡(jiǎn)單,但只考慮了淺層局部的信息;2)基于路徑的方法[8,24],考慮兩個(gè)節(jié)點(diǎn)的路徑連接來(lái)計(jì)算相似性,包括基于局部路徑的算法如局部路徑(local path,LP)算法和全局路徑的算法如KATZ.基于路徑的方法容易使大度或大介數(shù)節(jié)點(diǎn)成為一般節(jié)點(diǎn)的相似節(jié)點(diǎn).全局路徑算法考慮整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)及路徑,當(dāng)規(guī)模很大時(shí),難以計(jì)算,一般使用具有少量階數(shù)的局部路徑算法;3)基于隨機(jī)游走的方法[8],此類算法根據(jù)節(jié)點(diǎn)間游走時(shí)間或到達(dá)概率等特性建立相似性模型,有全局隨機(jī)游走算法如平均通勤時(shí)間(average commute time,ACT)算法和局部性游走算法如迭代隨機(jī)游走(superposed random walk,SRW)算法;在大型網(wǎng)絡(luò)上全局游走算法復(fù)雜度太高,實(shí)際上多使用局部隨機(jī)游走算法;但局部游走算法受最短路徑等結(jié)構(gòu)元素影響較大.和基于路徑的方法類似,這種方法也會(huì)使大度節(jié)點(diǎn)成為一般性相似節(jié)點(diǎn);4)基于節(jié)點(diǎn)結(jié)構(gòu)相對(duì)熵的方法,這類方法通過(guò)對(duì)比節(jié)點(diǎn)間某種結(jié)構(gòu)量的分布一致性程度計(jì)算相似性.目前這種方法比較少,文獻(xiàn)[22]提出一種基于鄰域度分布的局部相對(duì)熵(local relative entropy,LRE)的相似性度量方法,文獻(xiàn)[23]基于節(jié)點(diǎn)距離分布相對(duì)熵(distance distribution relative entropy,DDRE)研究節(jié)點(diǎn)間的相似性.LRE只是考慮了鄰域節(jié)點(diǎn)的度信息相似性,DDRE只考慮了最短路徑.這些都沒(méi)有考慮多階鄰居分布特征下的節(jié)點(diǎn)相似性.

本文提出一種節(jié)點(diǎn)的多階鄰接分布熵(multi-layer adjacency entropy,MAE),用于度量節(jié)點(diǎn)多階鄰居的分布信息,提供研究節(jié)點(diǎn)和網(wǎng)絡(luò)結(jié)構(gòu)特征的一種中觀視角:對(duì)任意節(jié)點(diǎn),選取合適的階數(shù)k,避免過(guò)于龐大復(fù)雜的計(jì)算,又不局限于淺層,得到一定尺度下節(jié)點(diǎn)周邊結(jié)構(gòu)特征的一種信息表示.進(jìn)而定義多階鄰接分布相對(duì)熵(multi-layer adjacency relative entropy,MARE),研究基于相對(duì)熵的節(jié)點(diǎn)相似性.

2 多階鄰接分布熵

多階鄰接分布熵(MAE)是一種節(jié)點(diǎn)局部熵,度量節(jié)點(diǎn)k階內(nèi)鄰居節(jié)點(diǎn)在各階上的分布特征信息,以下給出MAE相關(guān)的定義和定理.

令G(V,E)為無(wú)向復(fù)雜網(wǎng)絡(luò),V是節(jié)點(diǎn)集合,E是邊集合,n是節(jié)點(diǎn)個(gè)數(shù).

定義1i,j ∈V,d(i,j)表示i到j(luò)的最短距離.定義

為節(jié)點(diǎn)i的離心率,

為G的直徑,

為G的半徑[25].

定義2i,j ∈V,定義與i相距為k的節(jié)點(diǎn)數(shù)為

其中:若d(i,j)=k,則有δ(d(i,j)=k)=1,否則δ(d(i,j)=k)=0.當(dāng)k=0時(shí),令=1,表示節(jié)點(diǎn)0步可達(dá)自身.

定義3={j|d(i,j)=k,j ∈V}表示與節(jié)點(diǎn)i最短路徑為k的所有節(jié)點(diǎn)集合,集合中的節(jié)點(diǎn)稱為i的k階鄰居.

定義4定義節(jié)點(diǎn)i的多階鄰接分布熵(MAE)為

其中:log是以2為底的對(duì)數(shù),k是階數(shù).MAE是一種香農(nóng)信息熵.

定義5相對(duì)熵用于衡量?jī)蓚€(gè)隨機(jī)分布p(x)和q(x)的差距,其基本定義為j的k階MAE相對(duì)熵(MARE)如下:

定理2對(duì)于節(jié)點(diǎn)i,當(dāng)k ＞σ(i)時(shí),節(jié)點(diǎn)的熵不再增大,即節(jié)點(diǎn)的MAE熵在離心率處收斂;當(dāng)k ＞ρ(G)時(shí)網(wǎng)絡(luò)的任何節(jié)點(diǎn)熵不再增大,即網(wǎng)絡(luò)的MAE熵在其直徑處收斂.

2) 當(dāng)k ＞ρ(G),對(duì)于所有節(jié)點(diǎn)i ∈V,必有k ＞σ(i). 證畢.

定義6由定義1和定理2,對(duì)v ∈V,稱離心率σ(v)為節(jié)點(diǎn)v最大MAE影響力尺度;稱直徑ρ(G)為網(wǎng)絡(luò)的最大MAE影響力尺度.

定理3對(duì)于k階MAE熵,孤立節(jié)點(diǎn)的熵最小,值為0;1到k階分布節(jié)點(diǎn)數(shù)完全均勻時(shí)節(jié)點(diǎn)MAE熵達(dá)到最大值,最大值為

3 計(jì)算MAE熵基本算法

4 網(wǎng)絡(luò)節(jié)點(diǎn)相似性指標(biāo)

4.1 互相似性指標(biāo)

基于MAE相對(duì)熵,在尺度k下對(duì)比兩個(gè)節(jié)點(diǎn)的局部結(jié)構(gòu)相似性.相對(duì)熵越小,兩個(gè)節(jié)點(diǎn)越相似.如果i以j為最相似節(jié)點(diǎn),那么j也應(yīng)視i為最相似節(jié)點(diǎn).一個(gè)節(jié)點(diǎn)可以和多個(gè)節(jié)點(diǎn)相似.設(shè)Φi是節(jié)點(diǎn)i視為最相似的節(jié)點(diǎn)集合,即有

R是相對(duì)熵矩陣,其元素rij是節(jié)點(diǎn)i對(duì)j的相對(duì)熵,Ri是i對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)1,···,n的相對(duì)熵組成的向量.若i ∈Φj,且j ∈Φi,則i,j互為最相似,

是互最相似對(duì)節(jié)點(diǎn)集合.定義互相似性指標(biāo)為

4.2 傳播影響力

如果節(jié)點(diǎn)相似,其傳播影響力也應(yīng)該相似[22-23],可以采用SIR模型[26]來(lái)進(jìn)行驗(yàn)證.在SIR模型中,節(jié)點(diǎn)分為3種狀態(tài):易感狀態(tài)(I),節(jié)點(diǎn)未被感染,可能會(huì)變成感染狀態(tài);感染狀態(tài)(U),節(jié)點(diǎn)已被感染,可以傳染疾病;免疫狀態(tài)(R),結(jié)點(diǎn)不會(huì)再傳染,也不再被感染.

步驟1分別計(jì)算以每個(gè)節(jié)點(diǎn)作為傳播源(U),其他節(jié)點(diǎn)易傳染(I)的狀態(tài)下,按一定概率傳染100步每步網(wǎng)絡(luò)節(jié)點(diǎn)的感染率指i節(jié)點(diǎn)作為傳染源第t步網(wǎng)絡(luò)感染率,t ∈[1,2,···,100].

步驟2計(jì)算所有互最相似節(jié)點(diǎn)對(duì)之間每步感染率差值的絕對(duì)值之和t ∈[1,2,···,100].

步驟3得到

5 實(shí)驗(yàn)和分析

實(shí)驗(yàn)用網(wǎng)絡(luò)數(shù)據(jù)集中Sw,Sf,Rm由程序生成,其余數(shù)據(jù)集來(lái)自http://konect.uni-koblenz.de/networks/,見(jiàn)表1所示.

表1 網(wǎng)絡(luò)數(shù)據(jù)集Table 1 Network datasets

5.1 互相似指標(biāo)分析

由定理2,當(dāng)k ＞ρ(G)時(shí),所有節(jié)點(diǎn)的熵不再增加,一般應(yīng)取k≤ρ(G).對(duì)于尺度t的選取,取決于需要在多大的尺度上考察節(jié)點(diǎn)的相似性.表2是在5階尺度下MARE與LRE[22],JACCARD,KATZ[8]幾種方法互相似指標(biāo)對(duì)比.通過(guò)表2,可以看出基于MARE相對(duì)熵的相似性方法取得了較好的相似比.所有10個(gè)網(wǎng)絡(luò)中,MARE 互相似比超過(guò)了KATZ.除了Karate網(wǎng)絡(luò)的9個(gè)網(wǎng)絡(luò)上,MARE互相似比超過(guò)了JACCARD.在Jazz,Polbooks,Dolphins,Astroph,Rm和Sw這6個(gè)網(wǎng)絡(luò)上,MARE 的運(yùn)行結(jié)果好于LRE;在Chicago 和Egofacebook網(wǎng)絡(luò)上MARE和LRE方法互相似比一樣;僅在Karate和SF上,MARE熵互相似性指標(biāo)不如LRE,這是因?yàn)榫W(wǎng)絡(luò)結(jié)構(gòu)特征不同,而每一種相似性方法體現(xiàn)了一定的結(jié)構(gòu)比較角度,并無(wú)絕對(duì)優(yōu)劣之分.在后面的傳播影響力指標(biāo)實(shí)驗(yàn)上,MARE在所有網(wǎng)絡(luò)上表現(xiàn)比LRE更好.

表2 互相似比Table 2 Mutual similarity ratio

設(shè)MARE相對(duì)熵矩陣為R,其元素rij為節(jié)點(diǎn)i對(duì)節(jié)點(diǎn)j的相對(duì)熵,根據(jù)相對(duì)熵的定義,R不對(duì)稱.令H=R+RT,則H為對(duì)稱矩陣,hij為H中元素,通過(guò)hij=1-hij/max(hij),歸一化每個(gè)元素,得到標(biāo)準(zhǔn)化的相似性矩陣,其值在[0,1]之間.1為完全相似,0為完全不相似.LRE相對(duì)熵矩陣做同樣對(duì)稱化和歸一化處理.JACCARD相似性矩陣和KATZ相似性矩陣進(jìn)行同樣的歸一化處理.

下面基于相似性矩陣?yán)L制熱力圖(圖1),直觀地看一下Jazz網(wǎng)絡(luò)的相似性.圖1熱力圖坐標(biāo)為節(jié)點(diǎn)標(biāo)號(hào),體現(xiàn)節(jié)點(diǎn)間的相似性程度.可以看出,Jazz網(wǎng)絡(luò)如果基于KATZ 方法度量,總體上節(jié)點(diǎn)之間相似性較低,JACCARD方法下相似性狀況比KATZ要好些,LRE方法下相似性更好些,很多節(jié)點(diǎn)間的相似性值超過(guò)了0.8,MAE 熵視角下節(jié)點(diǎn)間相似程度最高,可以說(shuō)在MAE熵視角下該網(wǎng)絡(luò)同構(gòu)性很高.

圖1 Jazz網(wǎng)絡(luò)相似性熱力圖Fig.1 Similarity heat map of Jazz

下面以Jazz網(wǎng)絡(luò)和Chicago為例,給出幾種相似性方法的相似性散點(diǎn)圖,橫坐標(biāo)和縱坐標(biāo)都為節(jié)點(diǎn)編號(hào),每個(gè)橫坐標(biāo)節(jié)點(diǎn)和其對(duì)應(yīng)的最相似點(diǎn)為一散點(diǎn).從全局性相似性度量的角度考慮的話,散點(diǎn)應(yīng)該分散在二維平面上,而不是集中于對(duì)角線附近或堆在局部.如果節(jié)點(diǎn)a以b為最相似,b也應(yīng)識(shí)別a為最相似點(diǎn),體現(xiàn)在圖上就是對(duì)稱.

圖2 是Jazz 網(wǎng)絡(luò)4 種相似性散點(diǎn)圖,可以看出,MARE方法具有較好的對(duì)稱性,說(shuō)明該指標(biāo)較好地衡量了相似性.JACCARD方法基于共同鄰居衡量相似性,相似節(jié)點(diǎn)集中在每個(gè)節(jié)點(diǎn)的附近,所以主要沿對(duì)角線聚集.KATZ是基于路徑的相似性,度大的節(jié)點(diǎn)處在多個(gè)路徑的可能性更多,與較多或者大多節(jié)點(diǎn)相似的概率更大[23],Jazz 度最大的5 個(gè)節(jié)點(diǎn)依次是[66,6,19,22,89],這個(gè)在圖2(c)中得到了體現(xiàn).

圖2 Jazz網(wǎng)絡(luò)節(jié)點(diǎn)互最相似散點(diǎn)圖Fig.2 Scatter diagram of most similar nodes in Jazz

圖3是Chicago網(wǎng)絡(luò)4種相似性散點(diǎn)圖.Chicago網(wǎng)絡(luò)度分布相對(duì)均勻,沒(méi)有特別大度的節(jié)點(diǎn).而此網(wǎng)絡(luò)有一些介數(shù)很大的節(jié)點(diǎn),介數(shù)排前5 的節(jié)點(diǎn)標(biāo)號(hào)為[1155,1156,1146,1154,1152],介數(shù)依次為[251953,209291,93440,90713,88642],意味著很多路徑通過(guò)這些節(jié)點(diǎn),所以在KATZ方法中被很多節(jié)點(diǎn)視為最相似,在圖3(c)中體現(xiàn)為一條橫線.JACCARD和KATZ兩種方法相似,介數(shù)較大的點(diǎn)都與其他點(diǎn)相似得更多,但這個(gè)效果KATZ體現(xiàn)得更明顯.該網(wǎng)絡(luò)的LRE相似性對(duì)稱強(qiáng),因網(wǎng)絡(luò)中有大量度相同的節(jié)點(diǎn),按照LRE方法易被判為相似節(jié)點(diǎn),所以在圖3(d)中體現(xiàn)為很密集的散點(diǎn)圖.圖3(a)體現(xiàn)了MARE方法下Chicago網(wǎng)絡(luò)整體很強(qiáng)的相似對(duì)稱性,同時(shí)又避免了很多同度節(jié)點(diǎn)造成的片面相似性.

圖3 Chicago網(wǎng)絡(luò)節(jié)點(diǎn)互最相似散點(diǎn)圖Fig.3 Scatter diagram of most similar nodes in Chicago

5.2 互相似節(jié)點(diǎn)傳播分析

圖4 互最相似節(jié)點(diǎn)各步感染率差值Fig.4 Variance of infection probability of mutual most similar nodes in networks

6 結(jié)束語(yǔ)

熵可以度量復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)的結(jié)構(gòu)信息,本文提出節(jié)點(diǎn)的多階鄰接分布熵,用于表示k階內(nèi)鄰居節(jié)點(diǎn)的分布特征,熵越高,說(shuō)明分布越均衡,反之越不均衡.隨著階數(shù)k增大,節(jié)點(diǎn)的MAE熵也增大,并在離心率處收斂,k增大到網(wǎng)絡(luò)的直徑時(shí),所有節(jié)點(diǎn)的MAE熵不再增加,即網(wǎng)絡(luò)的MAE熵收斂.MAE熵代表的節(jié)點(diǎn)多階鄰居分布狀態(tài)提供一種新的角度分析節(jié)點(diǎn)間相似性和網(wǎng)絡(luò)整體的異構(gòu)性.通過(guò)定義相應(yīng)的多階鄰居分布相對(duì)熵,度量節(jié)點(diǎn)之間的相似性.實(shí)驗(yàn)表明這種度量方式效果明顯,具有較好的互相似比;通過(guò)疾病傳播模型,以這種方式度量的互最相似節(jié)點(diǎn)傳播感染率平均差距最小,說(shuō)明是一種合理有效的節(jié)點(diǎn)相似性度量方式.