穆俊芳，梁吉業(yè)+，鄭文萍，劉韶倩，王 杰

1.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，太原 030006

2.山西大學(xué) 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，太原 030006

1 引言

自然界中存在大量的復(fù)雜網(wǎng)絡(luò)[1-2]，如社會(huì)網(wǎng)絡(luò)、技術(shù)網(wǎng)絡(luò)、信息網(wǎng)絡(luò)和生物網(wǎng)絡(luò)。通?？梢杂靡粋€(gè)圖G=(V,E)來(lái)描述復(fù)雜網(wǎng)絡(luò)，其中V表示復(fù)雜網(wǎng)絡(luò)中個(gè)體集合，E表示個(gè)體間聯(lián)系的集合。在復(fù)雜網(wǎng)絡(luò)的傳播與免疫[3]、同步與控制[4]等實(shí)際問(wèn)題[5-8]中，度量節(jié)點(diǎn)之間的相似性是一項(xiàng)基礎(chǔ)且具有挑戰(zhàn)性的工作。

研究者已經(jīng)提出了各種方法度量節(jié)點(diǎn)之間的相似性，如基于鄰域節(jié)點(diǎn)的相似性指標(biāo)和基于路徑的相似性指標(biāo)?；卩徲蚬?jié)點(diǎn)的相似性指標(biāo)考慮了節(jié)點(diǎn)之間的公共鄰居的信息，如Jaccard 指標(biāo)[9]和余弦相似性[10]考慮了公共鄰居的個(gè)數(shù)，局部樸素貝葉斯方法[11]、互信息方法[12]和局部相對(duì)熵方法[13]考慮了公共鄰居節(jié)點(diǎn)的權(quán)重。復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的鄰域信息代表一種淺層局部結(jié)構(gòu)的視圖，僅使用節(jié)點(diǎn)的鄰域信息難以準(zhǔn)確地體現(xiàn)節(jié)點(diǎn)之間的相似性。基于路徑的相似性指標(biāo)考慮了節(jié)點(diǎn)之間的最短路徑數(shù)目，如Katz指標(biāo)[14]；或節(jié)點(diǎn)之間的到達(dá)概率，如局部隨機(jī)游走[15]、最大熵隨機(jī)游走[16]等。基于路徑的相似性指標(biāo)使得大度節(jié)點(diǎn)成為一般性節(jié)點(diǎn)，即許多節(jié)點(diǎn)的最相似節(jié)點(diǎn)是大度節(jié)點(diǎn)。

復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)距離分布[17]以一種簡(jiǎn)潔的方式包含了詳細(xì)的拓?fù)湫畔?，例如平均度、接近中心?closeness centrality，CC）、直徑和平均路徑長(zhǎng)度等，且刻畫(huà)了網(wǎng)絡(luò)中局部結(jié)構(gòu)差異。因此，考慮節(jié)點(diǎn)的距離分布信息研究節(jié)點(diǎn)之間的相似性，可能會(huì)更準(zhǔn)確地度量節(jié)點(diǎn)之間的相似性。本文定義了每個(gè)節(jié)點(diǎn)的距離分布，并在此基礎(chǔ)上采用相對(duì)熵提出了一種節(jié)點(diǎn)相似性度量方法（similarity measurement based on distance distribution and relative entropy，DDRE）。DDER 方法分為兩個(gè)步驟：第一步，根據(jù)節(jié)點(diǎn)之間的最短路徑生成每個(gè)節(jié)點(diǎn)的距離分布；第二步，根據(jù)節(jié)點(diǎn)的距離分布計(jì)算節(jié)點(diǎn)之間的相對(duì)熵進(jìn)而得到節(jié)點(diǎn)之間的相似性。為了驗(yàn)證DDRE方法的合理性，在6個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上與8 種相似性度量方法進(jìn)行比較，DDRE 方法在對(duì)稱(chēng)性和SIR 模型（susceptible-infectedremoved 模型）中影響其他節(jié)點(diǎn)的能力表現(xiàn)較好。

2 相關(guān)工作

復(fù)雜網(wǎng)絡(luò)可以用圖G=(V,E)表示，其中V是網(wǎng)絡(luò)G的節(jié)點(diǎn)集，E是網(wǎng)絡(luò)G的邊集，令n=|V|表示節(jié)點(diǎn)數(shù)，m=|E|表示邊數(shù)。除非特別聲明，本文僅考慮連通的簡(jiǎn)單無(wú)向圖，即網(wǎng)絡(luò)中沒(méi)有重邊和自環(huán)，且任意兩個(gè)節(jié)點(diǎn)可以通過(guò)有限步到達(dá)。網(wǎng)絡(luò)G中節(jié)點(diǎn)vi的鄰域記作={u|(u,vi)∈E,u∈V}表示圖G中與節(jié)點(diǎn)vi相鄰的節(jié)點(diǎn)集合，在不引起混淆的情況下，簡(jiǎn)記為Ni。節(jié)點(diǎn)vi的度=|Ni|表示網(wǎng)絡(luò)G中與節(jié)點(diǎn)vi關(guān)聯(lián)的邊數(shù)，簡(jiǎn)記為。Δ(G)和D(G)表示網(wǎng)絡(luò)G的最大度和直徑。

2.1 基于鄰域節(jié)點(diǎn)的相似性

基于鄰域節(jié)點(diǎn)的相似性指標(biāo)考慮了節(jié)點(diǎn)之間的公共鄰居的信息，即兩個(gè)節(jié)點(diǎn)的公共鄰居的信息重合率越高，則這兩個(gè)節(jié)點(diǎn)越相似。Jaccard 指標(biāo)[9]和余弦相似性[10]（cosine index）考慮了節(jié)點(diǎn)之間的公共鄰居節(jié)點(diǎn)個(gè)數(shù)并進(jìn)行標(biāo)準(zhǔn)化。局部貝葉斯方法[11]（local naive Bayes，LNB）假設(shè)不同的公共鄰居節(jié)點(diǎn)對(duì)節(jié)點(diǎn)之間的相似性具有不同的影響，并通過(guò)貝葉斯方法評(píng)估節(jié)點(diǎn)之間的相似性。互信息方法[12]（mutual information，MI）定義了節(jié)點(diǎn)之間的公共鄰居的似然函數(shù)來(lái)度量節(jié)點(diǎn)之間的相似性。

2018 年，Zhang 等人提出了局部相對(duì)方法（local relative entropy，LRE）[13]。LRE 方法首先尋找節(jié)點(diǎn)的局部結(jié)構(gòu)，即當(dāng)前節(jié)點(diǎn)及其鄰域節(jié)點(diǎn)，并計(jì)算局部結(jié)構(gòu)中度分布Pi={pi(k)|1 ≤k≤Δ(G)}作為當(dāng)前節(jié)點(diǎn)的概率分布，然后通過(guò)相對(duì)熵計(jì)算節(jié)點(diǎn)之間的差異DKL(Pi||Pj)，進(jìn)而給出節(jié)點(diǎn)之間的相似性，如式（1）所示。

其中：

上述基于鄰域節(jié)點(diǎn)的相似性度量方法主要考慮了節(jié)點(diǎn)的鄰域信息。然而，鄰域信息僅代表一種淺層局部結(jié)構(gòu)，難以準(zhǔn)確地體現(xiàn)節(jié)點(diǎn)之間的相似性。

2.2 基于路徑的相似性

基于路徑的相似性指標(biāo)考慮了節(jié)點(diǎn)之間的路徑信息，如最短路徑的數(shù)目、節(jié)點(diǎn)之間達(dá)到的概率等。

Katz 指標(biāo)[14]考慮了網(wǎng)中節(jié)點(diǎn)之間的所有路徑，其定義如式（2）所示。

局部隨機(jī)游走方法[15]（local random walk，LRW）是基于隨機(jī)游走策略來(lái)度量節(jié)點(diǎn)之間的相似性，其定義如式（3）所示。

最大熵隨機(jī)游走方法[16]（maximal entropy random walk，MERW）假設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)偏向與中心性節(jié)點(diǎn)相連，通過(guò)最大化熵函數(shù)度量節(jié)點(diǎn)之間的相似性。

上述基于路徑的相似性度量方法使得大度節(jié)點(diǎn)成為一般性節(jié)點(diǎn)，即許多節(jié)點(diǎn)最相似節(jié)點(diǎn)是大度節(jié)點(diǎn)。

3 基于距離分布的相似性度量

為了避免節(jié)點(diǎn)之間的相似性難以區(qū)分及大度節(jié)點(diǎn)成為一般性節(jié)點(diǎn)，本文提出了一種新的節(jié)點(diǎn)相似性度量DDRE。DDRE 相似性度量包括兩個(gè)主要階段：第一階段，根據(jù)節(jié)點(diǎn)之間的最短路徑生成每個(gè)節(jié)點(diǎn)的距離分布；第二階段，根據(jù)節(jié)點(diǎn)的距離分布計(jì)算每對(duì)節(jié)點(diǎn)之間的相對(duì)熵進(jìn)而得到節(jié)點(diǎn)之間的相似性。

3.1 節(jié)點(diǎn)距離分布

復(fù)雜網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的距離分布為Pi={pi(k)}，pi(k)的計(jì)算公式如下：

其中,Ni(k)是距離節(jié)點(diǎn)vi的最短路徑長(zhǎng)度為k的節(jié)點(diǎn)個(gè)數(shù)。

以圖1 中的實(shí)例網(wǎng)絡(luò)為例介紹節(jié)點(diǎn)的距離分布（紅色節(jié)點(diǎn)代表當(dāng)前節(jié)點(diǎn)，淺綠色、粉色、黃色、藍(lán)色、灰色和亮綠色節(jié)點(diǎn)分別代表從當(dāng)前節(jié)點(diǎn)出發(fā)經(jīng)過(guò)一步、兩步、三步、四步、五步和六步到達(dá)的節(jié)點(diǎn)）。圖1（a）和圖1（b）分別展示了節(jié)點(diǎn)18 和節(jié)點(diǎn)19 與其他節(jié)點(diǎn)最短路徑的情況。實(shí)例網(wǎng)絡(luò)的直徑D(G)=7，即每個(gè)節(jié)點(diǎn)的距離分布規(guī)模是8。根據(jù)路徑距離長(zhǎng)度，節(jié)點(diǎn)18依次可到達(dá)的節(jié)點(diǎn)個(gè)數(shù)N(i)={Ni(k)|0 ≤k≤D(G)},即：

N(18)={1,4,5,4,4,2,1,0}

由此可得節(jié)點(diǎn)18 的距離分布為：

Fig.1 Distance from node 18 and node 19 to other nodes in an example network,respectively圖1 在實(shí)例網(wǎng)絡(luò)中節(jié)點(diǎn)18 和19 與其他節(jié)點(diǎn)的距離

P18={0.05,0.19,0.24,0.19,0.19,0.10,0.05,0}

類(lèi)似地，節(jié)點(diǎn)19 的距離分布為：

P19={0.05,0.19,0.19,0.285,0.285,0,0,0}

復(fù)雜網(wǎng)絡(luò)中n個(gè)節(jié)點(diǎn)的距離分布{P1,P2,…,Pn}包含詳細(xì)的網(wǎng)絡(luò)拓?fù)湫畔?，如?jié)點(diǎn)的度、第k步到達(dá)的節(jié)點(diǎn)個(gè)數(shù)、節(jié)點(diǎn)所在的連通分支規(guī)模、網(wǎng)絡(luò)的平均度、網(wǎng)絡(luò)的直徑、節(jié)點(diǎn)的接近中心性和平均路徑長(zhǎng)度等。

（1）節(jié)點(diǎn)vi的度

（2）第k步到達(dá)的節(jié)點(diǎn)個(gè)數(shù)

（3）節(jié)點(diǎn)vi所在的連通分支規(guī)模

（4）網(wǎng)絡(luò)的平均度

（5）網(wǎng)絡(luò)的直徑

（6）節(jié)點(diǎn)vi的接近中心性（CC）

（7）網(wǎng)絡(luò)的平均路徑長(zhǎng)度

網(wǎng)絡(luò)的節(jié)點(diǎn)距離分布包含了詳細(xì)的拓?fù)湫畔?。因此，考慮節(jié)點(diǎn)的距離分布信息可以刻畫(huà)節(jié)點(diǎn)之間的結(jié)構(gòu)差異。通過(guò)節(jié)點(diǎn)的距離分布研究節(jié)點(diǎn)之間的相似性,可能會(huì)更準(zhǔn)確地度量節(jié)點(diǎn)之間的相似性。

3.2 節(jié)點(diǎn)之間的相似性

信息論中，相對(duì)熵也稱(chēng)KL-散度（Kullback-Leibler divergence），常用于度量?jī)蓚€(gè)概率分布在統(tǒng)計(jì)上的差異。本文使用相對(duì)熵度量?jī)蓚€(gè)節(jié)點(diǎn)距離分布的差異，相對(duì)熵越小，則兩個(gè)節(jié)點(diǎn)的距離分布越相似，反之亦然。相對(duì)熵的定義如式（4）所示。

當(dāng)pi(k)=0 或者pj(k)=0 時(shí)，=0 。由式（4）可知，相對(duì)熵是非對(duì)稱(chēng)的。因此本文對(duì)節(jié)點(diǎn)之間的相對(duì)熵進(jìn)行轉(zhuǎn)化，即：

由此定義相似性矩陣S：

表1 顯示了在實(shí)例網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)最相似的3個(gè)節(jié)點(diǎn)。可以看出與節(jié)點(diǎn)2 最相似的節(jié)點(diǎn)是17、13、6，與節(jié)點(diǎn)13 最相似的節(jié)點(diǎn)是17、2、4，與節(jié)點(diǎn)17 最相似的節(jié)點(diǎn)是2、13、6，即節(jié)點(diǎn)2、13、17 具有相似的距離分布。

Table 1 3 most similar nodes of each node in example network under DDRE表1 在實(shí)例網(wǎng)絡(luò)中DDRE 方法下每個(gè)節(jié)點(diǎn)最相似的3 個(gè)節(jié)點(diǎn)

表2 展示了在實(shí)例網(wǎng)絡(luò)中，LRE 方法和DDRE 方法的對(duì)比結(jié)果。在LRE 方法下，=1.000 0，=0.9538，=0.946 7。節(jié)點(diǎn)18 和節(jié)點(diǎn)19 具有相同的度數(shù)及相同的局部結(jié)構(gòu)。根據(jù)LRE 方法定義的節(jié)點(diǎn)局部結(jié)構(gòu)可知，相比于節(jié)點(diǎn)10，節(jié)點(diǎn)18 與節(jié)點(diǎn)21 有相似的局部結(jié)構(gòu)，因此節(jié)點(diǎn)18 與節(jié)點(diǎn)21 更相似。然而，當(dāng)進(jìn)一步考慮局部結(jié)構(gòu)的鄰域時(shí)，節(jié)點(diǎn)18 與節(jié)點(diǎn)10 有更為相似的結(jié)構(gòu)。因此，LRE 方法未能較準(zhǔn)確地區(qū)分節(jié)點(diǎn)18 與節(jié)點(diǎn)19、21 和10 之間的相似性，且在數(shù)值上也未能明顯地區(qū)分節(jié)點(diǎn)18 與節(jié)點(diǎn)19、21 和10 之間的相似性。在本文DDRE 相似性度量下，=0.906 3，=0.819 7，=0.944 2。盡管節(jié)點(diǎn)18 與節(jié)點(diǎn)10 沒(méi)有共同的一步到達(dá)的節(jié)點(diǎn)，然而當(dāng)考慮多步到達(dá)的節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)18 與節(jié)點(diǎn)10 更為相似。此外，在數(shù)值上DDRE 方法很好地區(qū)分了節(jié)點(diǎn)18 與節(jié)點(diǎn)19、21 和10 之間的相似性。

Table 2 Contrast result between LRE and DDRE in example network表2 在實(shí)例網(wǎng)絡(luò)中LRE 和DDRE 方法對(duì)比結(jié)果

3.3 DDRE 相似性理論分析

本文以ER 隨機(jī)圖和BA 無(wú)標(biāo)度網(wǎng)絡(luò)為例，分析基于節(jié)點(diǎn)的距離分布的相似性對(duì)SIR 傳播的定性影響。記s(t)、i(t)和r(t)分別為SIR 模型中時(shí)刻t的易感人群、感染人群和移除人群占整個(gè)人群的比例，則有s(t)+i(t)+r(t)=1。SIR 模型的微分方程描述如下：

其中，θ為傳播概率，δ為恢復(fù)概率。則可得到移除人群的穩(wěn)態(tài)值為：

根據(jù)ER 隨機(jī)圖構(gòu)造過(guò)程可知，ER 隨機(jī)圖中節(jié)點(diǎn)度服從泊松分布，即節(jié)點(diǎn)的度數(shù)近似相同。設(shè)網(wǎng)絡(luò)的平均度為＜k＞，隨機(jī)選取一個(gè)節(jié)點(diǎn)，網(wǎng)絡(luò)中大約有＜k＞個(gè)節(jié)點(diǎn)與該節(jié)點(diǎn)之間的距離為1，大約有＜k＞2個(gè)節(jié)點(diǎn)與該節(jié)點(diǎn)之間的距離為2，以此類(lèi)推。因此節(jié)點(diǎn)的距離分布：

因此，節(jié)點(diǎn)之間的相似性難以區(qū)分。此外，以每個(gè)節(jié)點(diǎn)作為初始傳播源，即s0=1-，i0=，r0=0，當(dāng)網(wǎng)絡(luò)規(guī)模足夠大時(shí)，SIR 模型中移除人群的穩(wěn)態(tài)值為r=1-e-θr/δ，即節(jié)點(diǎn)之間具有相似的傳播能力。在BA 無(wú)標(biāo)度網(wǎng)絡(luò)中節(jié)點(diǎn)度服從冪律分布，節(jié)點(diǎn)的距離分布差異較大，利用相對(duì)熵較準(zhǔn)確地度量了節(jié)點(diǎn)之間的差異性。因此，DDRE 相似性度量在BA 無(wú)標(biāo)度網(wǎng)絡(luò)中對(duì)稱(chēng)性表現(xiàn)較好。

4 實(shí)驗(yàn)結(jié)果與分析

本章中，3 個(gè)經(jīng)典人工網(wǎng)絡(luò)和6 個(gè)真實(shí)網(wǎng)絡(luò)用于分析DDRE 方法，并選擇Katz 指標(biāo)、局部隨機(jī)游走（LRW）、最大熵隨機(jī)游走（MERW）、Jaccard 指標(biāo)、余弦相似性（Cosine）、局部貝葉斯方法（LNB）、互信息（MI）和局部相對(duì)熵方法（LRE）進(jìn)行比較。

4.1 數(shù)據(jù)集

本文使用了經(jīng)典的人工網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)：ER 隨機(jī)圖、WS 小世界網(wǎng)絡(luò)、BA 無(wú)標(biāo)度網(wǎng)絡(luò)、US air lines network[18]、Email network[19]、Yeast network[20]、Soc_CMU network[18]、Bio_dmela network[18]和PGP network[18]。數(shù)據(jù)基本情況如表3 所示。由復(fù)雜網(wǎng)絡(luò)的小世界特性和“六度分割”可知，節(jié)點(diǎn)之間存在較短的最短路徑，因此為了降低時(shí)間復(fù)雜度，Katz 指標(biāo)中取參數(shù)l=3；局部隨機(jī)游走中同樣考慮路徑長(zhǎng)度為3 的影響。

Table 3 Real network data sets表3 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

4.2 對(duì)稱(chēng)性

在本節(jié)中，網(wǎng)絡(luò)中互為最相似的節(jié)點(diǎn)比例用于度量不同相似性方法的有效性。若節(jié)點(diǎn)vi最相似的節(jié)點(diǎn)是vj，且節(jié)點(diǎn)vj最相似的節(jié)點(diǎn)是vi，則節(jié)點(diǎn)vi和節(jié)點(diǎn)vj互為最相似的節(jié)點(diǎn)。網(wǎng)絡(luò)中節(jié)點(diǎn)之間的對(duì)稱(chēng)性定義如下：

其中，nms表示互為最相似的節(jié)點(diǎn)個(gè)數(shù)。本文使用散點(diǎn)圖表示每個(gè)節(jié)點(diǎn)及其對(duì)應(yīng)的最相似的節(jié)點(diǎn)之間的關(guān)系。若相似性度量方法準(zhǔn)確地度量了節(jié)點(diǎn)之間的相似性，則節(jié)點(diǎn)之間的對(duì)稱(chēng)性γ值較大[13]。此外，在節(jié)點(diǎn)及其對(duì)應(yīng)的最相似的節(jié)點(diǎn)的散點(diǎn)圖中，節(jié)點(diǎn)應(yīng)盡可能地分散在二維平面上，而不是集中在對(duì)角線附近，或呈現(xiàn)一條直線，即多數(shù)節(jié)點(diǎn)與同一節(jié)點(diǎn)最相似。

圖2 展示了在不同相似性度量在美國(guó)航空網(wǎng)絡(luò)中互為最相似節(jié)點(diǎn)的散點(diǎn)圖。X-軸代表網(wǎng)絡(luò)的節(jié)點(diǎn)標(biāo)號(hào)，Y-軸代表最相似的節(jié)點(diǎn)標(biāo)號(hào)。

圖2（a）和圖2（b）分別展示了在Jaccard 指標(biāo)和余弦相似性度量下，節(jié)點(diǎn)與其最相似的節(jié)點(diǎn)之間的散點(diǎn)圖。由圖可知，最相似的節(jié)點(diǎn)集中分布在對(duì)角線附近。Jaccard 指標(biāo)和余弦相似性是基于節(jié)點(diǎn)之間的公共鄰居數(shù)來(lái)度量節(jié)點(diǎn)之間的相似性，公共鄰居越多，則節(jié)點(diǎn)之間越相似，因此最相似的節(jié)點(diǎn)分布在對(duì)應(yīng)節(jié)點(diǎn)附近，即在散點(diǎn)圖中最相似的節(jié)點(diǎn)分布在對(duì)角線附近。盡管Jaccard 指標(biāo)和余弦相似性度量下，節(jié)點(diǎn)的對(duì)稱(chēng)性較好，然而由散點(diǎn)圖可知僅考慮一步路徑到達(dá)的節(jié)點(diǎn)難以準(zhǔn)確地刻畫(huà)節(jié)點(diǎn)之間的相似性。

圖2（c）和圖2（d）分別展示Katz 指標(biāo)和局部隨機(jī)游走（LRW）度量下，節(jié)點(diǎn)與其最相似的節(jié)點(diǎn)之間的散點(diǎn)圖。由圖可知，存在多個(gè)節(jié)點(diǎn)與同一個(gè)節(jié)點(diǎn)相似。Katz 指標(biāo)和局部隨機(jī)游走是基于路徑度量節(jié)點(diǎn)之間的相似性，度數(shù)較大的節(jié)點(diǎn)越容易處于不同節(jié)點(diǎn)之間路徑之間，因此存在較大的概率使得多數(shù)節(jié)點(diǎn)與大度節(jié)點(diǎn)相似。在美國(guó)航空網(wǎng)絡(luò)中，節(jié)點(diǎn)118 是度數(shù)最大的節(jié)點(diǎn)，節(jié)點(diǎn)261 是度數(shù)次大的節(jié)點(diǎn)，與圖2（c）和圖2（d）相對(duì)應(yīng)。局部貝葉斯方法（LNB）、最大熵隨機(jī)游走（MERW）和互信息（MI）度量節(jié)點(diǎn)之間的相似性時(shí)，同樣出現(xiàn)多數(shù)節(jié)點(diǎn)與大度節(jié)點(diǎn)相似，如圖2（e）、圖2（f）和圖2（g）所示。因此，基于路徑的節(jié)點(diǎn)相似性度量下，網(wǎng)絡(luò)節(jié)點(diǎn)的對(duì)稱(chēng)性較差，且使得大度節(jié)點(diǎn)成為一般性節(jié)點(diǎn)。

Fig.2 Most similar node of each node in US air lines network圖2 美國(guó)航空網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的最相似的節(jié)點(diǎn)

圖2（h）展示了局部相對(duì)熵方法（LRE）度量下，節(jié)點(diǎn)與其最相似的節(jié)點(diǎn)之間的散點(diǎn)圖。由圖可知，節(jié)點(diǎn)的最相似節(jié)點(diǎn)并沒(méi)有分布在對(duì)角線附近，也沒(méi)有出現(xiàn)多數(shù)節(jié)點(diǎn)與大度節(jié)點(diǎn)相似。然而，LRE 方法僅基于局部結(jié)構(gòu)（一步到達(dá)的節(jié)點(diǎn)）度量節(jié)點(diǎn)之間的相似性，未能準(zhǔn)確地度量節(jié)點(diǎn)之間的相似性。此外，當(dāng)網(wǎng)絡(luò)規(guī)模增大時(shí),節(jié)點(diǎn)之間的對(duì)稱(chēng)性明顯下降,如表4 所示。

圖2（i）展示了本文DDRE 度量下，節(jié)點(diǎn)與其最相似的節(jié)點(diǎn)之間的散點(diǎn)圖。由圖可知，節(jié)點(diǎn)的最相似節(jié)點(diǎn)并沒(méi)有分布在對(duì)角線附近，也沒(méi)有出現(xiàn)多數(shù)節(jié)點(diǎn)與大度節(jié)點(diǎn)相似。DDRE 是基于節(jié)點(diǎn)的距離分布來(lái)度量節(jié)點(diǎn)之間的相似性，考慮了多步路徑對(duì)節(jié)點(diǎn)相似性的影響，同時(shí)避免了大度節(jié)點(diǎn)成為一般性節(jié)點(diǎn)。此外，當(dāng)網(wǎng)絡(luò)規(guī)模增大時(shí)，節(jié)點(diǎn)仍然保持了良好的對(duì)稱(chēng)性，如表4 所示。

9 種相似性度量方法在Email network、Yeast network、Soc_CMU network、Bio_dmela network 和PGP network 具有類(lèi)似的性能表現(xiàn)。表4 給出了在不同的相似性度量下節(jié)點(diǎn)之間的對(duì)稱(chēng)性。本文DDRE 方法表現(xiàn)較好。

此外，本文在人工網(wǎng)絡(luò)上探索DDRE 相似性方法適用的網(wǎng)絡(luò)結(jié)構(gòu)。在ER 隨機(jī)圖、WS 小世界網(wǎng)絡(luò)和BA 無(wú)標(biāo)度網(wǎng)絡(luò)上與其他8 種方法對(duì)比。由表4 可知，DDRE 方法在BA 無(wú)標(biāo)度網(wǎng)絡(luò)中性能最好。在BA 無(wú)標(biāo)度網(wǎng)絡(luò)中，節(jié)點(diǎn)的度分布服從冪律分布，因此節(jié)點(diǎn)的距離分布差異性較大，DDRE 方法可以較為準(zhǔn)確地度量節(jié)點(diǎn)之間的相似性，即DDRE 方法適用于度量具有冪律分布的網(wǎng)絡(luò)。

4.3 互為最相似節(jié)點(diǎn)的影響力

在本節(jié)中，疾病傳播模型用于評(píng)估不同相似性度量方法的有效性。若兩個(gè)節(jié)點(diǎn)互為最相似的節(jié)點(diǎn)，則這兩個(gè)節(jié)點(diǎn)可能有相同的能力影響其他節(jié)點(diǎn)。為了驗(yàn)證DDRE 方法的合理性，本文使用經(jīng)典的SIR模型[21]來(lái)模擬網(wǎng)絡(luò)中的傳播，比較不同方法的結(jié)果。

在SIR 模型中節(jié)點(diǎn)分為三種狀態(tài)：易感狀態(tài)（S）、感染狀態(tài)（I）、免疫狀態(tài)（R）。易感狀態(tài)表示節(jié)點(diǎn)尚未感染疾病，可以變成感染狀態(tài)；感染狀態(tài)表示節(jié)點(diǎn)可以傳播疾病；免疫狀態(tài)表示節(jié)點(diǎn)不會(huì)感染疾病，也不會(huì)傳播疾病。當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)成為感染狀態(tài)，則該節(jié)點(diǎn)以概率θ感染其鄰居節(jié)點(diǎn)，且以概率δ恢復(fù)成免疫狀態(tài)。當(dāng)網(wǎng)絡(luò)中不存在感染節(jié)點(diǎn)時(shí)，該過(guò)程結(jié)束。本文取感染概率θ=0.3，恢復(fù)概率δ=1。

在SIR 模型中，將每個(gè)節(jié)點(diǎn)作為初始傳播源，即當(dāng)前節(jié)點(diǎn)處于I 狀態(tài)，其余節(jié)點(diǎn)處于S 狀態(tài)，以θ=0.3，δ=1 在網(wǎng)絡(luò)中傳播，直到?jīng)]有I 狀態(tài)的節(jié)點(diǎn)停止。在傳播過(guò)程中記錄每一步感染節(jié)點(diǎn)的比例和免疫節(jié)點(diǎn)的比例，并計(jì)算節(jié)點(diǎn)與其對(duì)應(yīng)最相似的節(jié)點(diǎn)在每一步的差異，其差異值定義如下：

其中，i表示當(dāng)前節(jié)點(diǎn)，i′表示節(jié)點(diǎn)i最相似的節(jié)點(diǎn)。表示節(jié)點(diǎn)i在第j步是網(wǎng)絡(luò)中處于感染狀態(tài)的節(jié)點(diǎn)比例（或處于免疫狀態(tài)的節(jié)點(diǎn)比例）。表示節(jié)點(diǎn)i′在第j步是網(wǎng)絡(luò)中處于感染狀態(tài)的節(jié)點(diǎn)比例（或處于免疫狀態(tài)的節(jié)點(diǎn)比例）。網(wǎng)絡(luò)中所有節(jié)點(diǎn)在第j步時(shí)的方差為：

Table 4 Symmetry of nodes under each method表4 每個(gè)方法的互為相似性節(jié)點(diǎn)比例

在實(shí)驗(yàn)過(guò)程中，將每個(gè)節(jié)點(diǎn)作為初始傳播源并記錄傳播過(guò)程中每一步的感染比例和恢復(fù)比例。本文取100 次的平均作為最終的結(jié)果。圖3 展示了在不同的網(wǎng)絡(luò)中，不同相似性度量方法下每一步的感染方差。X軸表示傳播的步數(shù)，Y軸表示對(duì)應(yīng)步數(shù)下所有節(jié)點(diǎn)的感染方差。圖4 展示了在不同的網(wǎng)絡(luò)中，不同相似性度量方法下每一步的免疫方差。X軸表示傳播的步數(shù)，Y軸表示對(duì)應(yīng)步數(shù)下所有節(jié)點(diǎn)的免疫方差。由圖3 和圖4 可知，具有相似的節(jié)點(diǎn)對(duì)稱(chēng)性的相似性度量方法的曲線相近。因此，本文DDRE 方法驗(yàn)證了在SIR 模型下互為最相似的節(jié)點(diǎn)對(duì)的傳播能力相似。

Fig.3 Variance of nodes’infection probability in different networks圖3 不同網(wǎng)絡(luò)中所有節(jié)點(diǎn)的感染方差

Fig.4 Variance of nodes’recovery probability in different networks圖4 不同網(wǎng)絡(luò)中所有節(jié)點(diǎn)的免疫方差

5 總結(jié)

本文提出了一種基于節(jié)點(diǎn)距離分布和相對(duì)熵的相似性度量指標(biāo)DDRE。節(jié)點(diǎn)的距離分布以一種簡(jiǎn)潔的方式包含了詳細(xì)的拓?fù)湫畔?，且?jié)點(diǎn)的距離分布可以刻畫(huà)網(wǎng)絡(luò)中局部結(jié)構(gòu)的差異。通過(guò)生成節(jié)點(diǎn)的距離分布，利用相對(duì)熵度量節(jié)點(diǎn)之間的差異進(jìn)而得到節(jié)點(diǎn)之間的相似性。通過(guò)與8 個(gè)相似性指標(biāo)在6個(gè)真實(shí)網(wǎng)絡(luò)上進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果表明DDRE 方法在對(duì)稱(chēng)性和SIR 模型中影響其他節(jié)點(diǎn)的能力方面表現(xiàn)出良好的性能。

度量復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)之間的相似性是一項(xiàng)基礎(chǔ)且具有挑戰(zhàn)的工作。目前，節(jié)點(diǎn)的相似性廣泛用于社區(qū)檢測(cè)和鏈路預(yù)測(cè)，且相似性度量還有許多潛在的研究方向，如基于節(jié)點(diǎn)之間的相似性進(jìn)行網(wǎng)絡(luò)抽樣，在抽樣網(wǎng)絡(luò)中比較復(fù)雜度較高的算法的性能。從節(jié)點(diǎn)相似性角度研究網(wǎng)絡(luò)抽樣可能會(huì)為人們提供新的角度去研究抽樣算法。