基于模體的樸素貝葉斯鏈路預測方法

曾茜，韓華，馬媛媛

（武漢理工大學 理學院，武漢 430070）

0 概述

隨著網絡科學的不斷發展，在社會科學、自然科學、信息科學等領域中的復雜關系問題都可以通過復雜網絡來描述［1］。在復雜網絡中通常出現網絡未知或部分未知的情況，因此，對缺失信息的還原和預測是網絡研究過程的關鍵。鏈路預測是根據已知的網絡信息，預測尚未形成連邊的兩個節點之間產生鏈接的可能性，以預測未知鏈接［2］和未來鏈接［3］。鏈路預測被廣泛應用在不同領域中，例如，在蛋白質網絡中探究蛋白質之間的相互作用［4-5］，在電商網絡中推送客戶感興趣的產品［6］，在社交網絡中推薦可能認識的人［7］，在航空網絡中推測影響網絡演化的重要因素［8］等。

現有鏈路預測方法從結構相似性［9］角度可以分為基于局部結構的方法（如共鄰節點指標（CN）［10］、Adamic-Adar（AA）［11］、資源分配指標（RA）［12］等）、基于半局部結構的方法（如局部路徑指標（LP）［13］）和基于全部結構的方法（如考慮全局路徑的Katz 指標［14］、節點偏好性隨機游走指標（DRW）［15］）?；诰植拷Y構的方法因計算復雜度低、適用性廣等優點備受研究人員的關注［16］，但這類方法大多簡單地假設每個共鄰節點對鏈路形成的貢獻一致。為此，文獻［17］提出局部樸素貝葉斯（LNB）模型，引入樸素貝葉斯理論來區分不同共鄰節點的貢獻，取得了較優的預測效果。文獻［18］提出樹增廣樸素貝葉斯預測（TAN）方法，引入樹增強樸素貝葉斯概率模型，緩解在共鄰節點之間強獨立性假設的問題。文獻［19］提出擴展局部樸素貝葉斯（ELNB）方法，通過對共鄰節點的角色貢獻函數進行擴展，揭示了微觀尺度下節點聚類系數對鏈路形成的作用。但這些方法都是基于共鄰節點的角色貢獻展開研究，忽略了路徑結構特征的貢獻。近年來，已有研究表明，考慮路徑結構周圍的拓撲信息能有效提升預測性能［20-21］。

此外，LNB 模型及其相關改進方法并未考慮網絡中的模體結構特征，而真實網絡（如食物鏈網絡、社交網絡）存在大量模體結構。針對含有模體特征的網絡，LNB 模型仍存在局限性問題。網絡模體的概念最早由文獻［22］提出，即在真實網絡中富集出現的由少量節點形成的小規模同構子圖。文獻［23］提出模體頂點度和邊度來衡量網絡中點和邊的重要性。文獻［24］提出三角模體度和四邊模體度的代數算法，設計基于模體特征的攻擊策略。文獻［25］依據樸素貝葉斯理論解釋了使用模體邊度進行鏈路預測的可行性，提出基于單模體邊度和雙模體邊度的鏈路預測方法，揭示了模體對鏈路形成的重要作用。隨著模體在復雜網絡中深入研究，模體頂點度和邊度已經不足以描述更復雜的拓撲特征，基于路徑結構的模體測度量有待提出。

本文結合路徑模體特征與樸素貝葉斯理論，提出一種基于模體的局部樸素貝葉斯鏈路預測方法MLNB，以分析路徑結構的模體特征對節點相似性的影響。定義路徑結構上三角模體的聚集程度——模體密度，考慮模體密度對待測連邊的影響，通過構建路徑的角色貢獻函數分析路徑的相似性貢獻，同時推導出基于共鄰節點的擴展指標。

1 基本概念

1.1 問題描述

本文給定一個無權無向網絡G=(V，E)，不考慮網絡中的重邊和自環，其中V和E分別表示網絡中所有節點的集合和所有邊的集合，全集U表示所有可能邊的集合。exy∈E表示節點x和節點y存在連邊，?E表示節點x和節點y不相連。網絡中節點總數為|V|=n，邊的總數為|E|=m，最大可能的邊的數量為|U|=。節點x的鄰居集合用Γ(x)來表示，節點x和節點y的共鄰節點集合表示為Γ(x，y)=Γ(x)∩Γ(y)。鏈路預測的目標是尋找集合U-E中缺失或暫未連接的邊。

1.2 相關指標

在現有鏈路預測方法中常用的相似性指標主要有8 個：

1）共鄰節點指標。對于待預測節點x和節點y，如果共鄰節點個數越多，則x和y連邊的可能性越大。通過節點對x和y的相似性得分計算它們共鄰節點的個數，如式（1）所示：

2）Adamic-Adar指標。AA 指標考慮共鄰節點的度越小對鏈路形成的貢獻越大，在CN 指標的基礎上為每個共鄰節點分配一個權重，權值定義為該共鄰節點度的對數的倒數。AA 指標定義如式（2）所示：

其中：kω為節點ω的度。

3）資源分配指標。對于未連接的節點x和節點y，在資源從節點x傳遞到節點y的過程中，每個共鄰節點的資源傳輸量與其度值成反比。RA 指標定義如式（3）所示：

4）基于CN 指標的局部樸素貝葉斯相似性指標（LNBCN）。在CN 指標的基礎上，LNBCN［17］考慮不同共鄰節點對鏈路形成的貢獻不同，定義了角色函數Rω來度量每個共鄰節點的貢獻，如式（4）所示：

其中：s為節點x和y相連的概率與不相連概率的比值。

5）基于AA 指標的局部樸素貝葉斯相似性指標（LNBAA）。將局部樸素貝葉斯原理與AA 指標相結合，LNBAA 定義如式（5）所示：

6）基于RA 指標的局部樸素貝葉斯相似性指標（LNBRA）。將局部樸素貝葉斯原理與RA 指標相結合，LNBRA 定義如式（6）所示：

7）局部路徑指標。不同于上述6 種局部指標，LP 指標是一種半局部指標，不僅考慮了二階路徑（即共鄰節點）的貢獻，也考慮了三階路徑對節點相似性的貢獻。LP 指標計算如式（7）所示：

其中：A為網絡的鄰接矩陣；A2和A3分別為待測節點對的二階路徑數和三階路徑數；α為控制三階路徑權重的可調參數，一般取值為0.01。

8）Katz 指標。全局相似性指標Katz 計算節點x和y之間所有路徑的貢獻，其定義如式（8）所示：

2 本文方法

2.1 模體理論

模體是一種介于節點和社團之間的網絡子圖，是在真實網絡中頻繁出現的結構單元，可以很好地反映網絡的結構和功能。模體的基本特性是在真實網絡中出現的頻率遠高于其在規模相同的隨機網絡中出現的頻率。模體的基本統計特征如下：

1）模體的頻率。對于給定的含有n個節點的子圖M，如果子圖M是網絡的模體，那么模體M的頻率［22］定義如式（9）所示：

其中：n(M)表示該子圖在真實網絡中出現的次數；N表示含有n個節點的子圖出現的總次數。

2）模體的P值。模體M在隨機網絡中出現次數的頻率大于節點數量相同的真實網絡中出現次數的頻率。P值越小，說明真實網絡的模體特征越明顯［22］。

3）模體的Z得分。對于模體Mi，Nreali表示該模體在真實網絡中出現的次數，Nrandi表示該模體在隨機網絡中出現的次數。Nrandi的平均值為＜Nrandi＞，標準差為σrandi，則模體Mi在真實網絡中的Z得分［22］如式（10）所示：

網絡中模體的存在性可以根據上述模體概念和基本統計特征來檢驗。在大多數無向網絡中，三節點模體是最常見的模體結構。三節點構成的兩種模體結構如圖1 所示。Δ 型三角模體作為網絡中最小的完全圖，構成網絡中信息傳播的局部單元，能反映網絡局部結構中的聚集特性。本文基于網絡的三角模體特征，提出針對三角模體結構的鏈路預測方法。

圖1 在無向網絡中三節點模體結構示例Fig.1 Examples of three-nodes motif structure in undirected network

2.2 模體密度的分析與量化

LNBCN 指標在CN 指標的基礎上，區分每個共鄰節點對待測連邊的不同貢獻，進一步提高預測精度，但忽略了經過不同共鄰節點的路徑對待測連邊貢獻的差異性。在路徑上三角模體的聚集程度即模體密度，對待測節點間連邊的產生具有重要影響。本文引入不同的局部結構圖進行對比分析，3 種不同的節點連接方式如圖2 所示。

圖2 3 種不同的節點連接方式Fig.2 Three different node connection methods

從圖2 可以看出，在3 種結構中均有一對待測節點x和y，以及待分析的路徑結構wxωy。從圖2（a）和圖2（b）可以看出，節點x和節點y的度值都相同，3 個共鄰節點的度值也都相同。但結構1 中路徑wxωy的Λ 型模體都不構成Δ 型模體，例如。在結構2 的路徑wxωy上Δ 型模體的聚集程度更高，這說明結構1 的路徑wxωy對Λ 型模體形成Δ 型模體起到抑制作用，結構2 的路徑wxωy對形成Δ 型模體有促進作用。對于三節點模體Λxωy，結構2 比結構1 形成三角模體Δxωy的可能性更大，即節點x和節點y產生連邊的可能性更大。從圖2（b）和圖2（c）可以看出，3 個共鄰節點既具有相同的度值，鄰居之間的連邊數也相同。根據LNBCN 原理，即用節點聚類系數來區分和量化不同共鄰節點的貢獻，由于在結構2 和結構3 中共鄰節點ω的聚類系數相同，因此對待測邊的貢獻相同。從圖2（c）可以看出，以節點ω為共鄰節點的任意待測節點對，例如(v1，v2)和(v3，v5)，節點ω對它們連邊的貢獻度都是相同的。LNBCN 方法僅考慮共鄰節點本身的局部特征屬性的差異化，卻忽略了共鄰節點與其待測節點之間連邊的局部結構差異。在結構2 中路徑wxωy上的Δ 型模體個數明顯更多，模體聚集程度明顯高于Λ 型模體，說明結構2 中路徑wxωy對形成Δ 型模體Δx，ω，y的促進作用更大，節點x和節點y更有可能形成連邊。在結構3 中3 對待預測節點(x，y)、(v1，v2)和(v3，v5)，路徑上的Δ 型模體聚集程度各不相同，分別對待測節點產生連邊的影響程度也不相同，不能簡單地用同一節點聚類系數來度量各自的貢獻。此外，從信息傳播路徑的角度，共鄰節點提供二階傳播路徑，模體聚集程度越高的二階路徑結構也能提供更多的三階傳播路徑，以圖2（b）為例，三階傳播路徑有，為節點x和y之間信息傳播提供更大的可能性。

上述分析表明，節點x和y產生連邊的可能性會因路徑模體特征的不同而不同。因此，本文考慮到每條路徑的模體特征對相似性有一定的影響，通過定義新的模體測度量來描述路徑結構上模體的聚集程度。

在復雜網絡中邊聚類系數是刻畫局部三角環聚集程度的重要參數。根據邊聚類系數的定義，即一條邊的兩個端點與其共鄰節點之間所構成的三角形數與所有可能包含該邊的三角形數的比值［26］，圖2（b）中節點x和節點ω形成的連邊exω的邊聚類系數計算如式（11）所示：

邊聚類系數準確地描述了一條邊上三角模體的聚集程度。

定義1（模體密度（Motif Density，MD））對于網絡中任意的待測節點x和y，ω是節點對的共鄰節點，將路徑wxωy的模體密度定義為包含路徑wxωy的所有三角模體數目與所有可能包含該路徑的三角模體數目的比值，如式（12）所示：

2.3 基于模體的樸素貝葉斯相似性指標

本文在對路徑結構上模體密度進行分析和量化后，基于模體密度來分析路徑的相似性貢獻，進而在樸素貝葉斯指標的基礎上提出改進的鏈路預測方法。

根據文獻［17］，LNB 方法將共鄰節點ω的相似性貢獻函數計算為待測節點x和y之間連接與不連接的概率之比，如式（13）所示：

其中：P(exy|ω)為ω的節點聚類系數，且滿足P(exy|ω)+。Rω表示 共鄰節點ω對待測節點產 生連邊和不產生連邊的貢獻比。由于這種貢獻函數的定義方式無法區分因路徑模體特征不同而產生的貢獻，為量化每條路徑對節點相似性的影響，采用模體密度來定義路徑的角色貢獻函數。

定義2（基于路徑模體密度的角色貢獻函數）將路徑wxωy的角色貢獻函數R(wxωy)定義為在路徑條件下，待測節點產生連邊和不產生連邊概率的比值，連邊概率用模體密度來表示，如式（14）所示：

其中：P(exy|wxωy)表示路徑wxωy對鏈接形成有促進作用，用該路徑的模 體密度來計算；表示路徑wxωy對鏈接形成有抑制作用。由式（14）可知，MMD(wxωy)越大，路徑wxωy的促進作用越大，抑制作用越小，路徑相似性貢獻R(wxωy)就越大，與2.2 節的分析相符。因此，本文利用R(wxωy)量化路徑wxωy對連邊相似性的貢獻是準確合理的。

定義3（基于模體的樸素貝葉斯鏈路預測指標）根據貝葉斯理論［17-19］，在所有經過共鄰節點路徑的條件下，節點x和y連邊與不連邊概率的計算如式（15）和式（16）所示：

其中：W(x，y)表示經過共鄰節點且連接節點x和y的所有路徑的集合。

假設每條路徑對待測連邊的貢獻是相互獨立的，則：

通過式（15）和式（16）相除的方式構建相似性指標，如式（19）所示：

其中：P(exy)和P()分別表示整體網絡中連邊存在和不存在的概率，均為常數。P(exy)和P()的計算如式（20）和式（21）所示：

顯然，s-1=也為常數，表示網絡中連邊存在和不存在的比值，可以忽略。

將式（14）、式（20）和式（21）代入式（19）中，等式兩邊取對數，得到其簡化形式，如式（22）所示：

定義4（擴展指標）基于共鄰節點的相似性預測模型有很多經典的預測指標。受LNB 模型啟發，為進一步驗證MLNB 方法的有效性，本文把MLNB思想應用到AA 指標和RA 指標上，得到MLNB 擴展指標，如式（23）和式（24）所示：

3 實驗與結果分析

3.1 實驗數據與預分析

為了評價MLNB 指標的預測準確性，本文在Football網絡［27］、USAir網絡［28］、C.elegans網絡［29］、FWMW 網絡［30］、FWEW 網絡［31］和FWFW 網絡［32］這6 個真實網絡上進行實驗。不同的網絡具有不同的模體特征。當網絡具有顯著的模體特征時，挖掘模體特征的鏈路預測方法在性能上顯著區別于傳統的鏈路預測方法。因此，本文在進行仿真實驗之前，首先要檢驗網絡模體的存在性。本文基于2.1 節的模體基本理論以及Rand-ESU［33］算法，通過模體發現軟件FANMOD 對6 個網絡進行模體存在性檢驗。6 個網絡的特征參數及模體存在性檢驗如表1 所示。從表1 可以看出，Z得分為正數，P值為0，說明以上6 種網絡都有三角模體特征，可以用來測試MLNB 方法的準確度。

表1 6 個網絡的特征參數與模體存在性檢驗Table 1 Feature parameters and motif existence test of six networks

3.2 評價指標

為了量化鏈路預測方法的準確性，一般將邊集E隨機劃分為訓練集ET和測試集EP，滿足E=ET∪EP，并且ET∩EP=?。訓練集ET作為可觀察到的已知網絡信息用于計算待測節點對的相似性分數。測試集EP作為待預測的網絡信息用于驗證預測的準確性。本文使用AUC（Area Under the Curve）值［34］、精確度（P）［35］來評價鏈路預測方法。AUC 從整體上衡量方法的準確性，P衡量局部預測的準確性。

AUC 值可解釋為隨機選擇一條缺失邊（即EP中的邊）的分數值大于隨機選擇一條不存在邊（即U-E中的邊）的分數值的概率。本文進行n次獨立抽取，如果有n′次缺失邊的分數值更高，n″次抽取兩條邊的分數值相等。AUC 值如式（25）所示：

精確度（P）計算前L條邊的預測準確率。將預測邊的相似性得分按照降序進行排序，如果在測試集中排名前L的有m條邊，那么精確度計算如式（26）所示：

由于本文選取6 個真實網絡的規模不同，因此統一將各數據集邊數的10%作為L的值。

3.3 仿真實驗結果分析

本文實驗針對6 個具有模體特征的網絡進行仿真實驗，采用隨機抽樣方法按9∶1 劃分訓練集和測試集。為了消除隨機誤差的影響，對每個網絡進行100 次獨立實驗并取平均值。本文將提出的MLNBs指標與局部屬性的CN 指標、AA 指標、RA 指標、LNBs 指標，半局部屬性的LP 指標和全局屬性的Katz 指標進行對比。在多個不同類型網絡中MLNBs 指標與現有指標的AUC 值對比如表2所示。

表2 不同指標的AUC 值對比Table 2 AUC values comparison among different indexs

從表2 可以看出，在每個網絡上MLNBs 系列指標（MLNBCN、MLNBAA、MLNBRA）的AUC 值均優于對應的原始指標（CN、AA、RA）和LNBs 指標（LNBCN、LNBAA、LNBRA），表明路徑模體密度對鏈路形成的可能性是有一定的影響。在MLNBs 系列指標中，MLNBRA 指標的AUC 值最高，MLNBAA指標次之，MLNBCN 指標最低，這說明懲罰度大的共鄰節點能夠有效提高預測精度。MLNBRA 指標的AUC 值在Football 網絡中僅次于LP 和Katz 指標，相差不超過1%，在剩余的網絡中MLNBRA 指標均具有較優的AUC 值。LP 指標在共同鄰居的基礎上考慮了三階路徑信息。Katz 指標考慮全局信息，時間復雜度相對較高。因此，LP 指標和Katz 指標的預測精度有一定優勢。而MLNBs 系列指標計算二階路徑的局部信息，時間復雜度低于LP 和Katz 指標。本文提出的MLNB 方法能解釋路徑模體聚集程度與節點對鏈接的關系，且復雜度低于半局部和全局方法，在含有模體的網絡上具有較優的適用性。

在FWMW、FWEW、FWFW 這3 個食物鏈網絡中，MLNBs 系列指標的AUC 值均優于所有的基準指標。若以次優的全局Katz 指標為基準，MLNBs 系列指標的AUC 值在FWMW 網絡中至少提升了5%，在FWEW 網絡中至少提升了2%，在FWFW 網絡中至少提升了7%。從表1 可以看出，FWMW、FWEW、FWFW 網絡的三角模體平均頻率較大，說明食物鏈網絡中存在大量的三角模體，對于這類模體特征較為明顯的網絡，基于模體特征的MLNB 方法預測的效果更好，進一步驗證了MLNB 指標針對此類網絡具有一定的的有效性和可行性。

在不同類型網絡中MLNBs 系列指標與現有指標的精確度對比如表3 所示，所有指標的預測結果在0～0.28，大多數指標的精確度小于0.2。

表3 不同指標的精確度對比Table 3 Precision comparison among different indexs

在USAir 網絡中，MLNBs 系列指標（MLNBCN、MLNBAA、MLNBRA）的精確度不僅優于對應的原始指標（CN、AA、RA）和LNBs 系列指標（LNBCN、LNBAA、LNBRA），而且相對半局部LP 指標和全局Katz 指標也有明顯提升。其中MLNBRA 指標的精確度最優，RA 和LNBRA 指標的精確度次優。精確度分析結果說明在USAir 網絡中，共鄰節點的度對鏈路的形成具有較大作用。在剩余的網絡中，MLNBs 系列指標的精確度均優于所有的基準指標。在所有網絡中，MLNBs 系列指標的精確度由大到小排序：MLNBRA>MLNBAA>MLNBCN。從表3 可以看出，基于模體特征的MLNB 指標的精確度相比局部和全局指標有較大幅度提升，證明了計算模體結構信息有助于提升預測性能。

3.4 魯棒性分析

為了進一步分析MLNBs 指標的魯棒性，本節在不同的訓練集比例下研究MLNBs 指標與基準指標預測結果的變化情況。在不同網絡中各指標的預測值仍然是取100 次獨立實驗的平均值。當訓練集比例從0.6 開始每次增加0.1 直到0.9 時，各指標的AUC 值對比如圖3 所示。

圖3 在不同的訓練集比例下各指標的AUC 值對比Fig.3 AUC values comparison among various indexs under different training set proportions

從圖3 可以看出，當訓練集比例增加時，多數指標的AUC 值隨之增大，這是由于訓練集比例增加使網絡中共鄰節點數目和已知拓撲信息增加，預測性能也隨之提升。MLNBs 指標的AUC 值隨訓練集比例增大而增大。當可觀測數據僅有60%時，除了USAir 和C.elegans 網絡中MLNBs 指標相對局部相似性指標變化范圍不大，在其余網絡中仍取得相對較優的預測結果，表明MLNBs 指標在不同網絡中具有較優的魯棒性。LNBs 指標在FWMW、FWEW、FWFW 網絡中并不遵從預測值隨訓練集比例增大而增大的規律，說明這3 個網絡中LNBs 指標對訓練集比例變化的敏感程度不同。

當訓練集比例從0.6 開始每次增加0.1 直到0.9時，各指標的精確度對比如圖4 所示。

圖4 在不同的訓練集比例下各指標的精確度對比Fig.4 Precision comparison among various indexs under different training set proportions

與AUC 值的變化規律相反，圖4 中各指標的精確度隨訓練集比例的增加而下降，這是由于精確度計算前L條邊預測的準確率，訓練集比例越大，前L條預測邊在測試集中的可能性越小，精確度就越小。當可觀測數據僅有60%時，在各網絡中MLNBs指標（MLNBCN、MLNBAA、MLNBRA）的精確度均優于對應的原始指標（CN、AA、RA）和LNBs 指標（LNBCN、LNBAA、LNBRA），相對LP 和Katz 指標也有明顯提升，這表明MLNBs 指標具有較優的魯棒性。

無論訓練集如何劃分，在圖3中Football和C.elegans網絡上的LP、Katz 指標相較于MLNBs 指標的AUC 值有一定的優勢，而圖4 中LP、Katz 指標的精確度都低于MLNBs 指標，說明LP 和Katz 指標并不是在所有評價指標下都表現良好。因此，MLNBs 指標在AUC 值和精確度兩種評價指標測試下具有較優的性能，與不同基準指標相比，在各網絡中具有較優的魯棒性。

4 結束語

本文針對具有模體特征的網絡提出一種基于模體的樸素貝葉斯鏈路預測方法。從模體角度定義模體密度來描述路徑結構上模體的聚集程度?？紤]到路徑結構上模體密度對鏈接形成的作用，構建基于路徑的角色貢獻函數，以量化路徑的相似性貢獻。在此基礎上，結合樸素貝葉斯理論，推導MLNBCN及其擴展指標。實驗結果表明，本文方法具有較優的魯棒性，所提相似性指標的AUC 值和精確度均優于LNBs 指標和CN、AA、RA 等基準指標。本文所提的鏈路預測方法僅針對無權無向、含有模體結構的網絡，后續將本文方法MLNB 應用到加權有向網絡中，研究加權有向網絡的模體特征對鏈路預測準確度的影響。此外，設計適用于更多不同領域網絡的鏈路預測方法也是下一步的重點研究方向。