基于模體的樸素貝葉斯鏈路預(yù)測(cè)方法

曾茜，韓華，馬媛媛

（武漢理工大學(xué) 理學(xué)院，武漢 430070）

0 概述

隨著網(wǎng)絡(luò)科學(xué)的不斷發(fā)展，在社會(huì)科學(xué)、自然科學(xué)、信息科學(xué)等領(lǐng)域中的復(fù)雜關(guān)系問題都可以通過復(fù)雜網(wǎng)絡(luò)來描述［1］。在復(fù)雜網(wǎng)絡(luò)中通常出現(xiàn)網(wǎng)絡(luò)未知或部分未知的情況，因此，對(duì)缺失信息的還原和預(yù)測(cè)是網(wǎng)絡(luò)研究過程的關(guān)鍵。鏈路預(yù)測(cè)是根據(jù)已知的網(wǎng)絡(luò)信息，預(yù)測(cè)尚未形成連邊的兩個(gè)節(jié)點(diǎn)之間產(chǎn)生鏈接的可能性，以預(yù)測(cè)未知鏈接［2］和未來鏈接［3］。鏈路預(yù)測(cè)被廣泛應(yīng)用在不同領(lǐng)域中，例如，在蛋白質(zhì)網(wǎng)絡(luò)中探究蛋白質(zhì)之間的相互作用［4-5］，在電商網(wǎng)絡(luò)中推送客戶感興趣的產(chǎn)品［6］，在社交網(wǎng)絡(luò)中推薦可能認(rèn)識(shí)的人［7］，在航空網(wǎng)絡(luò)中推測(cè)影響網(wǎng)絡(luò)演化的重要因素［8］等。

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

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

本文結(jié)合路徑模體特征與樸素貝葉斯理論，提出一種基于模體的局部樸素貝葉斯鏈路預(yù)測(cè)方法MLNB，以分析路徑結(jié)構(gòu)的模體特征對(duì)節(jié)點(diǎn)相似性的影響。定義路徑結(jié)構(gòu)上三角模體的聚集程度——模體密度，考慮模體密度對(duì)待測(cè)連邊的影響，通過構(gòu)建路徑的角色貢獻(xiàn)函數(shù)分析路徑的相似性貢獻(xiàn)，同時(shí)推導(dǎo)出基于共鄰節(jié)點(diǎn)的擴(kuò)展指標(biāo)。

1 基本概念

1.1 問題描述

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

1.2 相關(guān)指標(biāo)

在現(xiàn)有鏈路預(yù)測(cè)方法中常用的相似性指標(biāo)主要有8 個(gè)：

1）共鄰節(jié)點(diǎn)指標(biāo)。對(duì)于待預(yù)測(cè)節(jié)點(diǎn)x和節(jié)點(diǎn)y，如果共鄰節(jié)點(diǎn)個(gè)數(shù)越多，則x和y連邊的可能性越大。通過節(jié)點(diǎn)對(duì)x和y的相似性得分計(jì)算它們共鄰節(jié)點(diǎn)的個(gè)數(shù)，如式（1）所示：

2）Adamic-Adar指標(biāo)。AA 指標(biāo)考慮共鄰節(jié)點(diǎn)的度越小對(duì)鏈路形成的貢獻(xiàn)越大，在CN 指標(biāo)的基礎(chǔ)上為每個(gè)共鄰節(jié)點(diǎn)分配一個(gè)權(quán)重，權(quán)值定義為該共鄰節(jié)點(diǎn)度的對(duì)數(shù)的倒數(shù)。AA 指標(biāo)定義如式（2）所示：

其中：kω為節(jié)點(diǎn)ω的度。

3）資源分配指標(biāo)。對(duì)于未連接的節(jié)點(diǎn)x和節(jié)點(diǎn)y，在資源從節(jié)點(diǎn)x傳遞到節(jié)點(diǎn)y的過程中，每個(gè)共鄰節(jié)點(diǎn)的資源傳輸量與其度值成反比。RA 指標(biāo)定義如式（3）所示：

4）基于CN 指標(biāo)的局部樸素貝葉斯相似性指標(biāo)（LNBCN）。在CN 指標(biāo)的基礎(chǔ)上，LNBCN［17］考慮不同共鄰節(jié)點(diǎn)對(duì)鏈路形成的貢獻(xiàn)不同，定義了角色函數(shù)Rω來度量每個(gè)共鄰節(jié)點(diǎn)的貢獻(xiàn)，如式（4）所示：

其中：s為節(jié)點(diǎn)x和y相連的概率與不相連概率的比值。

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

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

7）局部路徑指標(biāo)。不同于上述6 種局部指標(biāo)，LP 指標(biāo)是一種半局部指標(biāo)，不僅考慮了二階路徑（即共鄰節(jié)點(diǎn)）的貢獻(xiàn)，也考慮了三階路徑對(duì)節(jié)點(diǎn)相似性的貢獻(xiàn)。LP 指標(biāo)計(jì)算如式（7）所示：

其中：A為網(wǎng)絡(luò)的鄰接矩陣；A2和A3分別為待測(cè)節(jié)點(diǎn)對(duì)的二階路徑數(shù)和三階路徑數(shù)；α為控制三階路徑權(quán)重的可調(diào)參數(shù)，一般取值為0.01。

8）Katz 指標(biāo)。全局相似性指標(biāo)Katz 計(jì)算節(jié)點(diǎn)x和y之間所有路徑的貢獻(xiàn)，其定義如式（8）所示：

2 本文方法

2.1 模體理論

模體是一種介于節(jié)點(diǎn)和社團(tuán)之間的網(wǎng)絡(luò)子圖，是在真實(shí)網(wǎng)絡(luò)中頻繁出現(xiàn)的結(jié)構(gòu)單元，可以很好地反映網(wǎng)絡(luò)的結(jié)構(gòu)和功能。模體的基本特性是在真實(shí)網(wǎng)絡(luò)中出現(xiàn)的頻率遠(yuǎn)高于其在規(guī)模相同的隨機(jī)網(wǎng)絡(luò)中出現(xiàn)的頻率。模體的基本統(tǒng)計(jì)特征如下：

1）模體的頻率。對(duì)于給定的含有n個(gè)節(jié)點(diǎn)的子圖M，如果子圖M是網(wǎng)絡(luò)的模體，那么模體M的頻率［22］定義如式（9）所示：

其中：n(M)表示該子圖在真實(shí)網(wǎng)絡(luò)中出現(xiàn)的次數(shù)；N表示含有n個(gè)節(jié)點(diǎn)的子圖出現(xiàn)的總次數(shù)。

2）模體的P值。模體M在隨機(jī)網(wǎng)絡(luò)中出現(xiàn)次數(shù)的頻率大于節(jié)點(diǎn)數(shù)量相同的真實(shí)網(wǎng)絡(luò)中出現(xiàn)次數(shù)的頻率。P值越小，說明真實(shí)網(wǎng)絡(luò)的模體特征越明顯［22］。

3）模體的Z得分。對(duì)于模體Mi，Nreali表示該模體在真實(shí)網(wǎng)絡(luò)中出現(xiàn)的次數(shù)，Nrandi表示該模體在隨機(jī)網(wǎng)絡(luò)中出現(xiàn)的次數(shù)。Nrandi的平均值為＜Nrandi＞，標(biāo)準(zhǔn)差為σrandi，則模體Mi在真實(shí)網(wǎng)絡(luò)中的Z得分［22］如式（10）所示：

網(wǎng)絡(luò)中模體的存在性可以根據(jù)上述模體概念和基本統(tǒng)計(jì)特征來檢驗(yàn)。在大多數(shù)無向網(wǎng)絡(luò)中，三節(jié)點(diǎn)模體是最常見的模體結(jié)構(gòu)。三節(jié)點(diǎn)構(gòu)成的兩種模體結(jié)構(gòu)如圖1 所示。Δ 型三角模體作為網(wǎng)絡(luò)中最小的完全圖，構(gòu)成網(wǎng)絡(luò)中信息傳播的局部單元，能反映網(wǎng)絡(luò)局部結(jié)構(gòu)中的聚集特性。本文基于網(wǎng)絡(luò)的三角模體特征，提出針對(duì)三角模體結(jié)構(gòu)的鏈路預(yù)測(cè)方法。

圖1 在無向網(wǎng)絡(luò)中三節(jié)點(diǎn)模體結(jié)構(gòu)示例Fig.1 Examples of three-nodes motif structure in undirected network

2.2 模體密度的分析與量化

LNBCN 指標(biāo)在CN 指標(biāo)的基礎(chǔ)上，區(qū)分每個(gè)共鄰節(jié)點(diǎn)對(duì)待測(cè)連邊的不同貢獻(xiàn)，進(jìn)一步提高預(yù)測(cè)精度，但忽略了經(jīng)過不同共鄰節(jié)點(diǎn)的路徑對(duì)待測(cè)連邊貢獻(xiàn)的差異性。在路徑上三角模體的聚集程度即模體密度，對(duì)待測(cè)節(jié)點(diǎn)間連邊的產(chǎn)生具有重要影響。本文引入不同的局部結(jié)構(gòu)圖進(jìn)行對(duì)比分析，3 種不同的節(jié)點(diǎn)連接方式如圖2 所示。

圖2 3 種不同的節(jié)點(diǎn)連接方式Fig.2 Three different node connection methods

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

上述分析表明，節(jié)點(diǎn)x和y產(chǎn)生連邊的可能性會(huì)因路徑模體特征的不同而不同。因此，本文考慮到每條路徑的模體特征對(duì)相似性有一定的影響，通過定義新的模體測(cè)度量來描述路徑結(jié)構(gòu)上模體的聚集程度。

在復(fù)雜網(wǎng)絡(luò)中邊聚類系數(shù)是刻畫局部三角環(huán)聚集程度的重要參數(shù)。根據(jù)邊聚類系數(shù)的定義，即一條邊的兩個(gè)端點(diǎn)與其共鄰節(jié)點(diǎn)之間所構(gòu)成的三角形數(shù)與所有可能包含該邊的三角形數(shù)的比值［26］，圖2（b）中節(jié)點(diǎn)x和節(jié)點(diǎn)ω形成的連邊exω的邊聚類系數(shù)計(jì)算如式（11）所示：

邊聚類系數(shù)準(zhǔn)確地描述了一條邊上三角模體的聚集程度。

定義1（模體密度（Motif Density，MD））對(duì)于網(wǎng)絡(luò)中任意的待測(cè)節(jié)點(diǎn)x和y，ω是節(jié)點(diǎn)對(duì)的共鄰節(jié)點(diǎn)，將路徑wxωy的模體密度定義為包含路徑wxωy的所有三角模體數(shù)目與所有可能包含該路徑的三角模體數(shù)目的比值，如式（12）所示：

2.3 基于模體的樸素貝葉斯相似性指標(biāo)

本文在對(duì)路徑結(jié)構(gòu)上模體密度進(jìn)行分析和量化后，基于模體密度來分析路徑的相似性貢獻(xiàn)，進(jìn)而在樸素貝葉斯指標(biāo)的基礎(chǔ)上提出改進(jìn)的鏈路預(yù)測(cè)方法。

根據(jù)文獻(xiàn)［17］，LNB 方法將共鄰節(jié)點(diǎn)ω的相似性貢獻(xiàn)函數(shù)計(jì)算為待測(cè)節(jié)點(diǎn)x和y之間連接與不連接的概率之比，如式（13）所示：

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

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

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

定義3（基于模體的樸素貝葉斯鏈路預(yù)測(cè)指標(biāo)）根據(jù)貝葉斯理論［17-19］，在所有經(jīng)過共鄰節(jié)點(diǎn)路徑的條件下，節(jié)點(diǎn)x和y連邊與不連邊概率的計(jì)算如式（15）和式（16）所示：

其中：W(x，y)表示經(jīng)過共鄰節(jié)點(diǎn)且連接節(jié)點(diǎn)x和y的所有路徑的集合。

假設(shè)每條路徑對(duì)待測(cè)連邊的貢獻(xiàn)是相互獨(dú)立的，則：

通過式（15）和式（16）相除的方式構(gòu)建相似性指標(biāo)，如式（19）所示：

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

顯然，s-1=也為常數(shù)，表示網(wǎng)絡(luò)中連邊存在和不存在的比值，可以忽略。

將式（14）、式（20）和式（21）代入式（19）中，等式兩邊取對(duì)數(shù)，得到其簡(jiǎn)化形式，如式（22）所示：

定義4（擴(kuò)展指標(biāo)）基于共鄰節(jié)點(diǎn)的相似性預(yù)測(cè)模型有很多經(jīng)典的預(yù)測(cè)指標(biāo)。受LNB 模型啟發(fā)，為進(jìn)一步驗(yàn)證MLNB 方法的有效性，本文把MLNB思想應(yīng)用到AA 指標(biāo)和RA 指標(biāo)上，得到MLNB 擴(kuò)展指標(biāo)，如式（23）和式（24）所示：

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

3.1 實(shí)驗(yàn)數(shù)據(jù)與預(yù)分析

為了評(píng)價(jià)MLNB 指標(biāo)的預(yù)測(cè)準(zhǔn)確性，本文在Football網(wǎng)絡(luò)［27］、USAir網(wǎng)絡(luò)［28］、C.elegans網(wǎng)絡(luò)［29］、FWMW 網(wǎng)絡(luò)［30］、FWEW 網(wǎng)絡(luò)［31］和FWFW 網(wǎng)絡(luò)［32］這6 個(gè)真實(shí)網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn)。不同的網(wǎng)絡(luò)具有不同的模體特征。當(dāng)網(wǎng)絡(luò)具有顯著的模體特征時(shí)，挖掘模體特征的鏈路預(yù)測(cè)方法在性能上顯著區(qū)別于傳統(tǒng)的鏈路預(yù)測(cè)方法。因此，本文在進(jìn)行仿真實(shí)驗(yàn)之前，首先要檢驗(yàn)網(wǎng)絡(luò)模體的存在性。本文基于2.1 節(jié)的模體基本理論以及Rand-ESU［33］算法，通過模體發(fā)現(xiàn)軟件FANMOD 對(duì)6 個(gè)網(wǎng)絡(luò)進(jìn)行模體存在性檢驗(yàn)。6 個(gè)網(wǎng)絡(luò)的特征參數(shù)及模體存在性檢驗(yàn)如表1 所示。從表1 可以看出，Z得分為正數(shù)，P值為0，說明以上6 種網(wǎng)絡(luò)都有三角模體特征，可以用來測(cè)試MLNB 方法的準(zhǔn)確度。

表1 6 個(gè)網(wǎng)絡(luò)的特征參數(shù)與模體存在性檢驗(yàn)Table 1 Feature parameters and motif existence test of six networks

3.2 評(píng)價(jià)指標(biāo)

為了量化鏈路預(yù)測(cè)方法的準(zhǔn)確性，一般將邊集E隨機(jī)劃分為訓(xùn)練集ET和測(cè)試集EP，滿足E=ET∪EP，并且ET∩EP=?。訓(xùn)練集ET作為可觀察到的已知網(wǎng)絡(luò)信息用于計(jì)算待測(cè)節(jié)點(diǎn)對(duì)的相似性分?jǐn)?shù)。測(cè)試集EP作為待預(yù)測(cè)的網(wǎng)絡(luò)信息用于驗(yàn)證預(yù)測(cè)的準(zhǔn)確性。本文使用AUC（Area Under the Curve）值［34］、精確度（P）［35］來評(píng)價(jià)鏈路預(yù)測(cè)方法。AUC 從整體上衡量方法的準(zhǔn)確性，P衡量局部預(yù)測(cè)的準(zhǔn)確性。

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

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

由于本文選取6 個(gè)真實(shí)網(wǎng)絡(luò)的規(guī)模不同，因此統(tǒng)一將各數(shù)據(jù)集邊數(shù)的10%作為L(zhǎng)的值。

3.3 仿真實(shí)驗(yàn)結(jié)果分析

本文實(shí)驗(yàn)針對(duì)6 個(gè)具有模體特征的網(wǎng)絡(luò)進(jìn)行仿真實(shí)驗(yàn)，采用隨機(jī)抽樣方法按9∶1 劃分訓(xùn)練集和測(cè)試集。為了消除隨機(jī)誤差的影響，對(duì)每個(gè)網(wǎng)絡(luò)進(jìn)行100 次獨(dú)立實(shí)驗(yàn)并取平均值。本文將提出的MLNBs指標(biāo)與局部屬性的CN 指標(biāo)、AA 指標(biāo)、RA 指標(biāo)、LNBs 指標(biāo)，半局部屬性的LP 指標(biāo)和全局屬性的Katz 指標(biāo)進(jìn)行對(duì)比。在多個(gè)不同類型網(wǎng)絡(luò)中MLNBs 指標(biāo)與現(xiàn)有指標(biāo)的AUC 值對(duì)比如表2所示。

表2 不同指標(biāo)的AUC 值對(duì)比Table 2 AUC values comparison among different indexs

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

在FWMW、FWEW、FWFW 這3 個(gè)食物鏈網(wǎng)絡(luò)中，MLNBs 系列指標(biāo)的AUC 值均優(yōu)于所有的基準(zhǔn)指標(biāo)。若以次優(yōu)的全局Katz 指標(biāo)為基準(zhǔn)，MLNBs 系列指標(biāo)的AUC 值在FWMW 網(wǎng)絡(luò)中至少提升了5%，在FWEW 網(wǎng)絡(luò)中至少提升了2%，在FWFW 網(wǎng)絡(luò)中至少提升了7%。從表1 可以看出，F(xiàn)WMW、FWEW、FWFW 網(wǎng)絡(luò)的三角模體平均頻率較大，說明食物鏈網(wǎng)絡(luò)中存在大量的三角模體，對(duì)于這類模體特征較為明顯的網(wǎng)絡(luò)，基于模體特征的MLNB 方法預(yù)測(cè)的效果更好，進(jìn)一步驗(yàn)證了MLNB 指標(biāo)針對(duì)此類網(wǎng)絡(luò)具有一定的的有效性和可行性。

在不同類型網(wǎng)絡(luò)中MLNBs 系列指標(biāo)與現(xiàn)有指標(biāo)的精確度對(duì)比如表3 所示，所有指標(biāo)的預(yù)測(cè)結(jié)果在0～0.28，大多數(shù)指標(biāo)的精確度小于0.2。

表3 不同指標(biāo)的精確度對(duì)比Table 3 Precision comparison among different indexs

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

3.4 魯棒性分析

為了進(jìn)一步分析MLNBs 指標(biāo)的魯棒性，本節(jié)在不同的訓(xùn)練集比例下研究MLNBs 指標(biāo)與基準(zhǔn)指標(biāo)預(yù)測(cè)結(jié)果的變化情況。在不同網(wǎng)絡(luò)中各指標(biāo)的預(yù)測(cè)值仍然是取100 次獨(dú)立實(shí)驗(yàn)的平均值。當(dāng)訓(xùn)練集比例從0.6 開始每次增加0.1 直到0.9 時(shí)，各指標(biāo)的AUC 值對(duì)比如圖3 所示。

圖3 在不同的訓(xùn)練集比例下各指標(biāo)的AUC 值對(duì)比Fig.3 AUC values comparison among various indexs under different training set proportions

從圖3 可以看出，當(dāng)訓(xùn)練集比例增加時(shí)，多數(shù)指標(biāo)的AUC 值隨之增大，這是由于訓(xùn)練集比例增加使網(wǎng)絡(luò)中共鄰節(jié)點(diǎn)數(shù)目和已知拓?fù)湫畔⒃黾樱A(yù)測(cè)性能也隨之提升。MLNBs 指標(biāo)的AUC 值隨訓(xùn)練集比例增大而增大。當(dāng)可觀測(cè)數(shù)據(jù)僅有60%時(shí)，除了USAir 和C.elegans 網(wǎng)絡(luò)中MLNBs 指標(biāo)相對(duì)局部相似性指標(biāo)變化范圍不大，在其余網(wǎng)絡(luò)中仍取得相對(duì)較優(yōu)的預(yù)測(cè)結(jié)果，表明MLNBs 指標(biāo)在不同網(wǎng)絡(luò)中具有較優(yōu)的魯棒性。LNBs 指標(biāo)在FWMW、FWEW、FWFW 網(wǎng)絡(luò)中并不遵從預(yù)測(cè)值隨訓(xùn)練集比例增大而增大的規(guī)律，說明這3 個(gè)網(wǎng)絡(luò)中LNBs 指標(biāo)對(duì)訓(xùn)練集比例變化的敏感程度不同。

當(dāng)訓(xùn)練集比例從0.6 開始每次增加0.1 直到0.9時(shí)，各指標(biāo)的精確度對(duì)比如圖4 所示。

圖4 在不同的訓(xùn)練集比例下各指標(biāo)的精確度對(duì)比Fig.4 Precision comparison among various indexs under different training set proportions

與AUC 值的變化規(guī)律相反，圖4 中各指標(biāo)的精確度隨訓(xùn)練集比例的增加而下降，這是由于精確度計(jì)算前L條邊預(yù)測(cè)的準(zhǔn)確率，訓(xùn)練集比例越大，前L條預(yù)測(cè)邊在測(cè)試集中的可能性越小，精確度就越小。當(dāng)可觀測(cè)數(shù)據(jù)僅有60%時(shí)，在各網(wǎng)絡(luò)中MLNBs指標(biāo)（MLNBCN、MLNBAA、MLNBRA）的精確度均優(yōu)于對(duì)應(yīng)的原始指標(biāo)（CN、AA、RA）和LNBs 指標(biāo)（LNBCN、LNBAA、LNBRA），相對(duì)LP 和Katz 指標(biāo)也有明顯提升，這表明MLNBs 指標(biāo)具有較優(yōu)的魯棒性。

無論訓(xùn)練集如何劃分，在圖3中Football和C.elegans網(wǎng)絡(luò)上的LP、Katz 指標(biāo)相較于MLNBs 指標(biāo)的AUC 值有一定的優(yōu)勢(shì)，而圖4 中LP、Katz 指標(biāo)的精確度都低于MLNBs 指標(biāo)，說明LP 和Katz 指標(biāo)并不是在所有評(píng)價(jià)指標(biāo)下都表現(xiàn)良好。因此，MLNBs 指標(biāo)在AUC 值和精確度兩種評(píng)價(jià)指標(biāo)測(cè)試下具有較優(yōu)的性能，與不同基準(zhǔn)指標(biāo)相比，在各網(wǎng)絡(luò)中具有較優(yōu)的魯棒性。

4 結(jié)束語

本文針對(duì)具有模體特征的網(wǎng)絡(luò)提出一種基于模體的樸素貝葉斯鏈路預(yù)測(cè)方法。從模體角度定義模體密度來描述路徑結(jié)構(gòu)上模體的聚集程度。考慮到路徑結(jié)構(gòu)上模體密度對(duì)鏈接形成的作用，構(gòu)建基于路徑的角色貢獻(xiàn)函數(shù)，以量化路徑的相似性貢獻(xiàn)。在此基礎(chǔ)上，結(jié)合樸素貝葉斯理論，推導(dǎo)MLNBCN及其擴(kuò)展指標(biāo)。實(shí)驗(yàn)結(jié)果表明，本文方法具有較優(yōu)的魯棒性，所提相似性指標(biāo)的AUC 值和精確度均優(yōu)于LNBs 指標(biāo)和CN、AA、RA 等基準(zhǔn)指標(biāo)。本文所提的鏈路預(yù)測(cè)方法僅針對(duì)無權(quán)無向、含有模體結(jié)構(gòu)的網(wǎng)絡(luò)，后續(xù)將本文方法MLNB 應(yīng)用到加權(quán)有向網(wǎng)絡(luò)中，研究加權(quán)有向網(wǎng)絡(luò)的模體特征對(duì)鏈路預(yù)測(cè)準(zhǔn)確度的影響。此外，設(shè)計(jì)適用于更多不同領(lǐng)域網(wǎng)絡(luò)的鏈路預(yù)測(cè)方法也是下一步的重點(diǎn)研究方向。