面向復雜網絡的節點相似性度量*

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

1.山西大學 計算機與信息技術學院，太原 030006

2.山西大學 計算智能與中文信息處理教育部重點實驗室，太原 030006

1 引言

自然界中存在大量的復雜網絡[1-2]，如社會網絡、技術網絡、信息網絡和生物網絡。通常可以用一個圖G=(V,E)來描述復雜網絡，其中V表示復雜網絡中個體集合，E表示個體間聯系的集合。在復雜網絡的傳播與免疫[3]、同步與控制[4]等實際問題[5-8]中，度量節點之間的相似性是一項基礎且具有挑戰性的工作。

研究者已經提出了各種方法度量節點之間的相似性，如基于鄰域節點的相似性指標和基于路徑的相似性指標。基于鄰域節點的相似性指標考慮了節點之間的公共鄰居的信息，如Jaccard 指標[9]和余弦相似性[10]考慮了公共鄰居的個數，局部樸素貝葉斯方法[11]、互信息方法[12]和局部相對熵方法[13]考慮了公共鄰居節點的權重。復雜網絡中節點的鄰域信息代表一種淺層局部結構的視圖，僅使用節點的鄰域信息難以準確地體現節點之間的相似性。基于路徑的相似性指標考慮了節點之間的最短路徑數目，如Katz指標[14]；或節點之間的到達概率，如局部隨機游走[15]、最大熵隨機游走[16]等。基于路徑的相似性指標使得大度節點成為一般性節點，即許多節點的最相似節點是大度節點。

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

2 相關工作

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

2.1 基于鄰域節點的相似性

基于鄰域節點的相似性指標考慮了節點之間的公共鄰居的信息，即兩個節點的公共鄰居的信息重合率越高，則這兩個節點越相似。Jaccard 指標[9]和余弦相似性[10]（cosine index）考慮了節點之間的公共鄰居節點個數并進行標準化。局部貝葉斯方法[11]（local naive Bayes，LNB）假設不同的公共鄰居節點對節點之間的相似性具有不同的影響，并通過貝葉斯方法評估節點之間的相似性。互信息方法[12]（mutual information，MI）定義了節點之間的公共鄰居的似然函數來度量節點之間的相似性。

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

其中：

上述基于鄰域節點的相似性度量方法主要考慮了節點的鄰域信息。然而，鄰域信息僅代表一種淺層局部結構，難以準確地體現節點之間的相似性。

2.2 基于路徑的相似性

基于路徑的相似性指標考慮了節點之間的路徑信息，如最短路徑的數目、節點之間達到的概率等。

Katz 指標[14]考慮了網中節點之間的所有路徑，其定義如式（2）所示。

局部隨機游走方法[15]（local random walk，LRW）是基于隨機游走策略來度量節點之間的相似性，其定義如式（3）所示。

最大熵隨機游走方法[16]（maximal entropy random walk，MERW）假設網絡中的節點偏向與中心性節點相連，通過最大化熵函數度量節點之間的相似性。

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

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

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

3.1 節點距離分布

復雜網絡中每個節點的距離分布為Pi={pi(k)}，pi(k)的計算公式如下：

其中,Ni(k)是距離節點vi的最短路徑長度為k的節點個數。

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

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

由此可得節點18 的距離分布為：

Fig.1 Distance from node 18 and node 19 to other nodes in an example network,respectively圖1 在實例網絡中節點18 和19 與其他節點的距離

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

類似地，節點19 的距離分布為：

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

復雜網絡中n個節點的距離分布{P1,P2,…,Pn}包含詳細的網絡拓撲信息，如節點的度、第k步到達的節點個數、節點所在的連通分支規模、網絡的平均度、網絡的直徑、節點的接近中心性和平均路徑長度等。

（1）節點vi的度

（2）第k步到達的節點個數

（3）節點vi所在的連通分支規模

（4）網絡的平均度

（5）網絡的直徑

（6）節點vi的接近中心性（CC）

（7）網絡的平均路徑長度

網絡的節點距離分布包含了詳細的拓撲信息。因此，考慮節點的距離分布信息可以刻畫節點之間的結構差異。通過節點的距離分布研究節點之間的相似性,可能會更準確地度量節點之間的相似性。

3.2 節點之間的相似性

信息論中，相對熵也稱KL-散度（Kullback-Leibler divergence），常用于度量兩個概率分布在統計上的差異。本文使用相對熵度量兩個節點距離分布的差異，相對熵越小，則兩個節點的距離分布越相似，反之亦然。相對熵的定義如式（4）所示。

當pi(k)=0 或者pj(k)=0 時，=0 。由式（4）可知，相對熵是非對稱的。因此本文對節點之間的相對熵進行轉化，即：

由此定義相似性矩陣S：

表1 顯示了在實例網絡中每個節點最相似的3個節點。可以看出與節點2 最相似的節點是17、13、6，與節點13 最相似的節點是17、2、4，與節點17 最相似的節點是2、13、6，即節點2、13、17 具有相似的距離分布。

Table 1 3 most similar nodes of each node in example network under DDRE表1 在實例網絡中DDRE 方法下每個節點最相似的3 個節點

表2 展示了在實例網絡中，LRE 方法和DDRE 方法的對比結果。在LRE 方法下，=1.000 0，=0.9538，=0.946 7。節點18 和節點19 具有相同的度數及相同的局部結構。根據LRE 方法定義的節點局部結構可知，相比于節點10，節點18 與節點21 有相似的局部結構，因此節點18 與節點21 更相似。然而，當進一步考慮局部結構的鄰域時，節點18 與節點10 有更為相似的結構。因此，LRE 方法未能較準確地區分節點18 與節點19、21 和10 之間的相似性，且在數值上也未能明顯地區分節點18 與節點19、21 和10 之間的相似性。在本文DDRE 相似性度量下，=0.906 3，=0.819 7，=0.944 2。盡管節點18 與節點10 沒有共同的一步到達的節點，然而當考慮多步到達的節點時，節點18 與節點10 更為相似。此外，在數值上DDRE 方法很好地區分了節點18 與節點19、21 和10 之間的相似性。

Table 2 Contrast result between LRE and DDRE in example network表2 在實例網絡中LRE 和DDRE 方法對比結果

3.3 DDRE 相似性理論分析

本文以ER 隨機圖和BA 無標度網絡為例，分析基于節點的距離分布的相似性對SIR 傳播的定性影響。記s(t)、i(t)和r(t)分別為SIR 模型中時刻t的易感人群、感染人群和移除人群占整個人群的比例，則有s(t)+i(t)+r(t)=1。SIR 模型的微分方程描述如下：

其中，θ為傳播概率，δ為恢復概率。則可得到移除人群的穩態值為：

根據ER 隨機圖構造過程可知，ER 隨機圖中節點度服從泊松分布，即節點的度數近似相同。設網絡的平均度為＜k＞，隨機選取一個節點，網絡中大約有＜k＞個節點與該節點之間的距離為1，大約有＜k＞2個節點與該節點之間的距離為2，以此類推。因此節點的距離分布：

因此，節點之間的相似性難以區分。此外，以每個節點作為初始傳播源，即s0=1-，i0=，r0=0，當網絡規模足夠大時，SIR 模型中移除人群的穩態值為r=1-e-θr/δ，即節點之間具有相似的傳播能力。在BA 無標度網絡中節點度服從冪律分布，節點的距離分布差異較大，利用相對熵較準確地度量了節點之間的差異性。因此，DDRE 相似性度量在BA 無標度網絡中對稱性表現較好。

4 實驗結果與分析

本章中，3 個經典人工網絡和6 個真實網絡用于分析DDRE 方法，并選擇Katz 指標、局部隨機游走（LRW）、最大熵隨機游走（MERW）、Jaccard 指標、余弦相似性（Cosine）、局部貝葉斯方法（LNB）、互信息（MI）和局部相對熵方法（LRE）進行比較。

4.1 數據集

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

Table 3 Real network data sets表3 真實網絡數據集

4.2 對稱性

在本節中，網絡中互為最相似的節點比例用于度量不同相似性方法的有效性。若節點vi最相似的節點是vj，且節點vj最相似的節點是vi，則節點vi和節點vj互為最相似的節點。網絡中節點之間的對稱性定義如下：

其中，nms表示互為最相似的節點個數。本文使用散點圖表示每個節點及其對應的最相似的節點之間的關系。若相似性度量方法準確地度量了節點之間的相似性，則節點之間的對稱性γ值較大[13]。此外，在節點及其對應的最相似的節點的散點圖中，節點應盡可能地分散在二維平面上，而不是集中在對角線附近，或呈現一條直線，即多數節點與同一節點最相似。

圖2 展示了在不同相似性度量在美國航空網絡中互為最相似節點的散點圖。X-軸代表網絡的節點標號，Y-軸代表最相似的節點標號。

圖2（a）和圖2（b）分別展示了在Jaccard 指標和余弦相似性度量下，節點與其最相似的節點之間的散點圖。由圖可知，最相似的節點集中分布在對角線附近。Jaccard 指標和余弦相似性是基于節點之間的公共鄰居數來度量節點之間的相似性，公共鄰居越多，則節點之間越相似，因此最相似的節點分布在對應節點附近，即在散點圖中最相似的節點分布在對角線附近。盡管Jaccard 指標和余弦相似性度量下，節點的對稱性較好，然而由散點圖可知僅考慮一步路徑到達的節點難以準確地刻畫節點之間的相似性。

圖2（c）和圖2（d）分別展示Katz 指標和局部隨機游走（LRW）度量下，節點與其最相似的節點之間的散點圖。由圖可知，存在多個節點與同一個節點相似。Katz 指標和局部隨機游走是基于路徑度量節點之間的相似性，度數較大的節點越容易處于不同節點之間路徑之間，因此存在較大的概率使得多數節點與大度節點相似。在美國航空網絡中，節點118 是度數最大的節點，節點261 是度數次大的節點，與圖2（c）和圖2（d）相對應。局部貝葉斯方法（LNB）、最大熵隨機游走（MERW）和互信息（MI）度量節點之間的相似性時，同樣出現多數節點與大度節點相似，如圖2（e）、圖2（f）和圖2（g）所示。因此，基于路徑的節點相似性度量下，網絡節點的對稱性較差，且使得大度節點成為一般性節點。

Fig.2 Most similar node of each node in US air lines network圖2 美國航空網絡中每個節點的最相似的節點

圖2（h）展示了局部相對熵方法（LRE）度量下，節點與其最相似的節點之間的散點圖。由圖可知，節點的最相似節點并沒有分布在對角線附近，也沒有出現多數節點與大度節點相似。然而，LRE 方法僅基于局部結構（一步到達的節點）度量節點之間的相似性，未能準確地度量節點之間的相似性。此外，當網絡規模增大時,節點之間的對稱性明顯下降,如表4 所示。

圖2（i）展示了本文DDRE 度量下，節點與其最相似的節點之間的散點圖。由圖可知，節點的最相似節點并沒有分布在對角線附近，也沒有出現多數節點與大度節點相似。DDRE 是基于節點的距離分布來度量節點之間的相似性，考慮了多步路徑對節點相似性的影響，同時避免了大度節點成為一般性節點。此外，當網絡規模增大時，節點仍然保持了良好的對稱性，如表4 所示。

9 種相似性度量方法在Email network、Yeast network、Soc_CMU network、Bio_dmela network 和PGP network 具有類似的性能表現。表4 給出了在不同的相似性度量下節點之間的對稱性。本文DDRE 方法表現較好。

此外，本文在人工網絡上探索DDRE 相似性方法適用的網絡結構。在ER 隨機圖、WS 小世界網絡和BA 無標度網絡上與其他8 種方法對比。由表4 可知，DDRE 方法在BA 無標度網絡中性能最好。在BA 無標度網絡中，節點的度分布服從冪律分布，因此節點的距離分布差異性較大，DDRE 方法可以較為準確地度量節點之間的相似性，即DDRE 方法適用于度量具有冪律分布的網絡。

4.3 互為最相似節點的影響力

在本節中，疾病傳播模型用于評估不同相似性度量方法的有效性。若兩個節點互為最相似的節點，則這兩個節點可能有相同的能力影響其他節點。為了驗證DDRE 方法的合理性，本文使用經典的SIR模型[21]來模擬網絡中的傳播，比較不同方法的結果。

在SIR 模型中節點分為三種狀態：易感狀態（S）、感染狀態（I）、免疫狀態（R）。易感狀態表示節點尚未感染疾病，可以變成感染狀態；感染狀態表示節點可以傳播疾病；免疫狀態表示節點不會感染疾病，也不會傳播疾病。當網絡中節點成為感染狀態，則該節點以概率θ感染其鄰居節點，且以概率δ恢復成免疫狀態。當網絡中不存在感染節點時，該過程結束。本文取感染概率θ=0.3，恢復概率δ=1。

在SIR 模型中，將每個節點作為初始傳播源，即當前節點處于I 狀態，其余節點處于S 狀態，以θ=0.3，δ=1 在網絡中傳播，直到沒有I 狀態的節點停止。在傳播過程中記錄每一步感染節點的比例和免疫節點的比例，并計算節點與其對應最相似的節點在每一步的差異，其差異值定義如下：

其中，i表示當前節點，i′表示節點i最相似的節點。表示節點i在第j步是網絡中處于感染狀態的節點比例（或處于免疫狀態的節點比例）。表示節點i′在第j步是網絡中處于感染狀態的節點比例（或處于免疫狀態的節點比例）。網絡中所有節點在第j步時的方差為：

Table 4 Symmetry of nodes under each method表4 每個方法的互為相似性節點比例

在實驗過程中，將每個節點作為初始傳播源并記錄傳播過程中每一步的感染比例和恢復比例。本文取100 次的平均作為最終的結果。圖3 展示了在不同的網絡中，不同相似性度量方法下每一步的感染方差。X軸表示傳播的步數，Y軸表示對應步數下所有節點的感染方差。圖4 展示了在不同的網絡中，不同相似性度量方法下每一步的免疫方差。X軸表示傳播的步數，Y軸表示對應步數下所有節點的免疫方差。由圖3 和圖4 可知，具有相似的節點對稱性的相似性度量方法的曲線相近。因此，本文DDRE 方法驗證了在SIR 模型下互為最相似的節點對的傳播能力相似。

Fig.3 Variance of nodes’infection probability in different networks圖3 不同網絡中所有節點的感染方差

Fig.4 Variance of nodes’recovery probability in different networks圖4 不同網絡中所有節點的免疫方差

5 總結

本文提出了一種基于節點距離分布和相對熵的相似性度量指標DDRE。節點的距離分布以一種簡潔的方式包含了詳細的拓撲信息，且節點的距離分布可以刻畫網絡中局部結構的差異。通過生成節點的距離分布，利用相對熵度量節點之間的差異進而得到節點之間的相似性。通過與8 個相似性指標在6個真實網絡上進行對比實驗，結果表明DDRE 方法在對稱性和SIR 模型中影響其他節點的能力方面表現出良好的性能。

度量復雜網絡中節點之間的相似性是一項基礎且具有挑戰的工作。目前，節點的相似性廣泛用于社區檢測和鏈路預測，且相似性度量還有許多潛在的研究方向，如基于節點之間的相似性進行網絡抽樣，在抽樣網絡中比較復雜度較高的算法的性能。從節點相似性角度研究網絡抽樣可能會為人們提供新的角度去研究抽樣算法。