融合樸素貝葉斯方法的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)

王潤(rùn)芳，陳增強(qiáng),2，劉忠信,2

（1. 南開(kāi)大學(xué) 人工智能學(xué)院，天津 300350; 2. 天津市智能機(jī)器人重點(diǎn)實(shí)驗(yàn)室，天津 300350）

現(xiàn)代社會(huì)中的信息呈爆炸式增長(zhǎng)，使得社會(huì)系統(tǒng)極具復(fù)雜性。研究表明，各種系統(tǒng)之間的交互信息可以通過(guò)對(duì)應(yīng)的復(fù)雜網(wǎng)絡(luò)表示，其中，網(wǎng)絡(luò)中的節(jié)點(diǎn)代表系統(tǒng)中的個(gè)體，連邊代表個(gè)體之間的關(guān)系[1]。網(wǎng)絡(luò)科學(xué)是專(zhuān)門(mén)用于研究各種復(fù)雜網(wǎng)絡(luò)系統(tǒng)的定性和定量規(guī)律的一門(mén)交叉學(xué)科[2]。然而，由于隱私政策和個(gè)體設(shè)置等原因，實(shí)際獲取的網(wǎng)絡(luò)連邊信息往往是不完整的，加大了網(wǎng)絡(luò)科學(xué)研究的難度。鏈路預(yù)測(cè)能夠?qū)θ笔畔⑦M(jìn)行還原和預(yù)測(cè)，是網(wǎng)絡(luò)科學(xué)研究的有力輔助工具，具有重要的理論研究和實(shí)際應(yīng)用價(jià)值。一方面，鏈路預(yù)測(cè)可以幫助人們理解各種復(fù)雜網(wǎng)絡(luò)的演化機(jī)制[3-4]，為不同演化模型的優(yōu)劣比較提供統(tǒng)一平臺(tái)；另一方面，鏈路預(yù)測(cè)的結(jié)果可以指導(dǎo)生物網(wǎng)絡(luò)中的實(shí)驗(yàn)，降低實(shí)驗(yàn)成本并提高準(zhǔn)確率，還可以建立網(wǎng)絡(luò)中的推薦系統(tǒng)[5]。

網(wǎng)絡(luò)中的鏈路預(yù)測(cè)，是指如何根據(jù)網(wǎng)絡(luò)中已知的節(jié)點(diǎn)和結(jié)構(gòu)信息，預(yù)測(cè)網(wǎng)絡(luò)中尚未產(chǎn)生連邊的兩個(gè)節(jié)點(diǎn)之間產(chǎn)生連接的可能性[6]，包括未來(lái)鏈接和未知鏈接的預(yù)測(cè)，常用的方法可分為兩大類(lèi)：基于相似性的方法和智能方法。

基于相似性方法的一個(gè)基本假設(shè)是：兩個(gè)節(jié)點(diǎn)越相似，在未來(lái)連接的可能性越大，而節(jié)點(diǎn)的相似程度可通過(guò)相似性指標(biāo)量化，即根據(jù)相似性指標(biāo)計(jì)算相似性得分，得分越高，兩個(gè)節(jié)點(diǎn)越相似。已有相似性指標(biāo)可分為三大類(lèi)：基于節(jié)點(diǎn)局部信息的方法，如共同鄰居(CN)[7]、Adamic-Adar(AA)[8]和資源分配(RA)[9]指標(biāo)等；基于全局路徑的方法，如Katz[7]和局部路徑(LP)[9]等；基于隨機(jī)游走的方法[10]。

上述方法中，基于節(jié)點(diǎn)局部信息的方法運(yùn)算復(fù)雜度最低，且預(yù)測(cè)準(zhǔn)確度較高，因此常被用作基準(zhǔn)指標(biāo)。呂琳媛等[11]對(duì)幾種基準(zhǔn)指標(biāo)的研究發(fā)現(xiàn)，無(wú)論是否加權(quán)，RA均表現(xiàn)最好，且無(wú)權(quán)指標(biāo)的性能均優(yōu)于加權(quán)指標(biāo)。由此得出：復(fù)雜網(wǎng)絡(luò)中的弱連接不容忽視，強(qiáng)調(diào)弱連接的貢獻(xiàn)可以極大提高預(yù)測(cè)準(zhǔn)確度。此外，作者意識(shí)到這些指標(biāo)存在共同缺點(diǎn)，即認(rèn)為所有共同鄰居對(duì)于節(jié)點(diǎn)對(duì)的貢獻(xiàn)相同。為此，Liu等[12]假設(shè)每個(gè)共同鄰居的貢獻(xiàn)不同，有些促進(jìn)鏈接的產(chǎn)生，有些則抑制，因此共同鄰居數(shù)量相同的節(jié)點(diǎn)對(duì)產(chǎn)生鏈接的概率可能不同。然后將樸素貝葉斯理論應(yīng)用到鏈路預(yù)測(cè)中，提出了局部樸素貝葉斯(LNB)模型。最近，Valverde-Rebaza等[13]認(rèn)為每個(gè)用戶(hù)可能同時(shí)屬于多個(gè)社團(tuán)，且扮演角色不同，預(yù)測(cè)時(shí)應(yīng)充分考慮用戶(hù)所屬的所有社團(tuán)信息。基于此思想，Valverde-Rebaza在文獻(xiàn)[14]中提出了基于重疊組的樸素貝葉斯(GNB)鏈路預(yù)測(cè)模型。此外，考慮到共同鄰居之間并非完全相互獨(dú)立，文獻(xiàn)[15]使用互信息量化共同鄰居的相關(guān)性，對(duì)LNB進(jìn)行推廣，提出了廣義的樹(shù)增廣樸素貝葉斯(TAN)概率模型，并擴(kuò)展到了CN、AA和RA指標(biāo)，在運(yùn)行效率和有效性等方面均優(yōu)于基準(zhǔn)方法。然而，上述方法僅考慮了共同鄰居的作用，忽略了節(jié)點(diǎn)自身的影響。閆玲玲等[16]提出了一種基于度和聚類(lèi)系數(shù)的新指標(biāo)，對(duì)中國(guó)航空網(wǎng)絡(luò)中的節(jié)點(diǎn)重要性進(jìn)行分析。Pujari等[17]認(rèn)為節(jié)點(diǎn)對(duì)的每個(gè)屬性代表不同信息，可以將所有屬性對(duì)應(yīng)特征進(jìn)行加權(quán)整合以提高預(yù)測(cè)性能。Li等[18]以新浪微博為研究對(duì)象，根據(jù)其自身特點(diǎn)提出了包含用戶(hù)臨近特征、屬性特征和拓?fù)涮卣鞯奶卣骷糜陬A(yù)測(cè)。但這些方法僅考慮了節(jié)點(diǎn)自身作用，忽略了共同鄰居的影響。

為解決上述問(wèn)題，本文基于局部樸素貝葉斯(LNB)模型提出了融合樸素貝葉斯(syncretic naive Bayes，SNB)模型。本文的主要貢獻(xiàn)如下。1)認(rèn)為鏈接的產(chǎn)生受到內(nèi)部和外部?jī)煞矫嬉蛩氐挠绊?。其中，?jié)點(diǎn)對(duì)自身特點(diǎn)屬于內(nèi)部影響，可以通過(guò)節(jié)點(diǎn)度量化；共同鄰居的作用屬于外部影響，可以通過(guò)LNB模型量化，將兩者結(jié)合提出一個(gè)新模型。2)模型的優(yōu)劣不僅體現(xiàn)在其自身的預(yù)測(cè)精確度上，還體現(xiàn)在它與其他思想的融合效果上，后者可以通過(guò)其在基準(zhǔn)指標(biāo)推廣后的預(yù)測(cè)精確度定性描述。因此，文中將SNB推廣到CN、AA和RA形式，說(shuō)明其具有普適性。

近些年，智能方法受到廣泛關(guān)注。已有研究包括支持向量機(jī)[19]、BP神經(jīng)網(wǎng)絡(luò)[20-21]、3層隱含的貝葉斯(3-HBP)鏈路預(yù)測(cè)模型[22]、最大熵模型[23]以及可變貝葉斯概率矩陣分解模型[24]等。與直接給節(jié)點(diǎn)對(duì)分配相似性得分不同，這些方法都是通過(guò)學(xué)習(xí)已知知識(shí)建立模型進(jìn)行預(yù)測(cè)，是將來(lái)的研究重點(diǎn)。

1 預(yù)備知識(shí)

本部分首先給出了鏈路預(yù)測(cè)的概念，然后介紹了本文的理論基礎(chǔ)——樸素貝葉斯理論，接著闡述了一些常用的基準(zhǔn)指標(biāo)，最后簡(jiǎn)要介紹了局部樸素貝葉斯(LNB)鏈路預(yù)測(cè)模型。

1.1 問(wèn)題描述

一個(gè)無(wú)權(quán)無(wú)向的網(wǎng)絡(luò)圖可表示為 G (V,E)，其中 V 代表節(jié)點(diǎn)集， E?V×V 代表節(jié)點(diǎn)之間的連邊集合，本文不考慮自環(huán)和重復(fù)邊。假設(shè)有兩個(gè)節(jié)點(diǎn) x?V,y?V ，則 exy=〈x,y〉∈E 表示節(jié)點(diǎn) x 和 y 之間存在鏈接，而〈x,y〉?E 表示節(jié)點(diǎn) x 和 y 之間不存在鏈接。網(wǎng)絡(luò)中所有可能連邊的集合為A， 則因此，不存在的連邊集合為 N=A-E 。文中 N (x) 代表節(jié)點(diǎn) x 的鄰居集合，則節(jié)點(diǎn) x 和節(jié)點(diǎn) y 的共同鄰居集合可以記為 N(x,y)=N(x)∩N(y)。

通常，按照某種比例 r 將網(wǎng)絡(luò)中所有連邊劃分為訓(xùn)練集 ET和測(cè)試集 EP。 其中， ET代表已知連邊集合， EP代表缺失連邊集合，鏈路預(yù)測(cè)的任務(wù)是根據(jù) ET建立模型預(yù)測(cè)出 EP中的連邊。

1.2 樸素貝葉斯理論

樸素貝葉斯分類(lèi)器簡(jiǎn)單易懂，受到了眾多學(xué)者的青睞。假設(shè) C 為類(lèi)變量， X=(X1,X2,···,Xn) 代表 n 維特征向量。根據(jù)貝葉斯理論，已知特征向量 X 求類(lèi)變量 C 取某值的概率為后驗(yàn)概率P(C|X)：

樸素貝葉斯的基本假設(shè)是：當(dāng)類(lèi)變量 C 取值固定時(shí)，各特征變量 Xi(i=1,2,···,n) 之間相互獨(dú)立，即

將式(2)代入式(1)可得

1.3 基準(zhǔn)指標(biāo)

1) 共同鄰居指標(biāo)(CN)

通常認(rèn)為，共同鄰居越多，節(jié)點(diǎn)對(duì)越相似。CN指標(biāo)通過(guò)直接計(jì)算共同鄰居數(shù)目來(lái)量化節(jié)點(diǎn)對(duì)的相似性[7]，定義如下：

2) Adamic-Adar指標(biāo)(AA)

AA指標(biāo)[8]以CN指標(biāo)為基礎(chǔ)，認(rèn)為度越大的共同鄰居對(duì)于節(jié)點(diǎn)對(duì)的貢獻(xiàn)越小。因此，可以通過(guò)懲罰度大的鄰居節(jié)點(diǎn)提高預(yù)測(cè)準(zhǔn)確度，其定義為

式中 kz表示節(jié)點(diǎn) z 的度。

3) 資源分配指標(biāo)(RA)

受到資源分配動(dòng)力學(xué)的啟發(fā)，RA指標(biāo)[9]根據(jù)資源在節(jié)點(diǎn)間的傳遞情況，結(jié)合懲罰大度節(jié)點(diǎn)的思想，定義了節(jié)點(diǎn)對(duì)的相似性：

1.4 LNB鏈路預(yù)測(cè)模型

LNB模型[11]假設(shè)節(jié)點(diǎn) x 和 y 是否連接取決于它們的共同鄰居集合，即節(jié)點(diǎn) x 和 y 在未來(lái)連接和未連接的概率為后驗(yàn)概率 P(exy|N(x,y)) 和根據(jù)貝葉斯理論有

將式(5)和式(6)分別代入式(3)和式(4)，然后兩式相除，得：

式中 P(exy)、分別表示節(jié)點(diǎn) x 和 y 連接與未連接的先驗(yàn)概率：

顯然， P(exy)、均為常數(shù)，則也為常數(shù)，表示網(wǎng)絡(luò)中存在邊與不存在邊的比值，可以忽略。而 P(exy|z) 表示節(jié)點(diǎn) z 的聚類(lèi)系數(shù)：

式中 T (z) 代表節(jié)點(diǎn) z 的 kz個(gè)鄰居之間真實(shí)存在的邊數(shù)。令表示 z 的鄰居之間連接與未連接的比值， Rz值越大，說(shuō)明節(jié)點(diǎn) z 的鄰居之間更傾向于相互連接，即節(jié)點(diǎn) z 的促進(jìn)作用越強(qiáng)。不同節(jié)點(diǎn)的 Rz值一般不同，因此稱(chēng) Rz為節(jié)點(diǎn) z 的角色函數(shù)。將式(8)、式(9)代入式(7)，等式兩邊取對(duì)數(shù)得：

將其推廣可得：

2 融合樸素貝葉斯鏈路預(yù)測(cè)模型

在介紹SNB模型之前，首先考慮一個(gè)問(wèn)題，節(jié)點(diǎn)之間鏈接的產(chǎn)生到底與什么因素有關(guān)？圖1給 出了3種不同的思路。

圖 1 CNs、LNBs、SNBs結(jié)構(gòu)示意Fig. 1 Structure schematic diagram of CNs， LNBs and SNBs

最簡(jiǎn)單的一種思路是：兩節(jié)點(diǎn)的共同鄰居數(shù)目越多，它們的興趣屬性等越接近，未來(lái)越有可能產(chǎn)生鏈接，這便是圖1(a)中CNs指標(biāo)的主要思想。因此，圖中節(jié)點(diǎn) c 和 d 的共同鄰居數(shù)目多，它們產(chǎn)生鏈接的可能性大于節(jié)點(diǎn) a 和 b。

在CNs的基礎(chǔ)上，有學(xué)者指出，每個(gè)共同鄰居扮演角色不同，對(duì)于節(jié)點(diǎn)對(duì)產(chǎn)生鏈接的貢獻(xiàn)不同，因此不能通過(guò)簡(jiǎn)單計(jì)算共同鄰居的數(shù)目得到相似性，而應(yīng)該累加共同鄰居的貢獻(xiàn)以得到最終的相似性分?jǐn)?shù)。按照此思想，圖1(b)中節(jié)點(diǎn) a 和b 的共同鄰居只有2個(gè)，但每個(gè)共同鄰居的鄰居之間大多存在鏈接，說(shuō)明這兩個(gè)共同鄰居對(duì)其鄰居間鏈接的產(chǎn)生有促進(jìn)作用；節(jié)點(diǎn) c 和節(jié)點(diǎn) d 的共同鄰居有3個(gè)，但每個(gè)共同鄰居的鄰居之間基本沒(méi)有鏈接，說(shuō)明這些共同鄰居對(duì)其鄰居間鏈接的產(chǎn)生有抑制作用。綜上，節(jié)點(diǎn) a 和 b 在未來(lái)產(chǎn)生鏈接的可能性更大。

實(shí)際生活中，節(jié)點(diǎn)間鏈接的產(chǎn)生不僅受到共同鄰居的影響，與其自身的活躍程度也是密不可分的。在共同鄰居數(shù)目相等的條件下，節(jié)點(diǎn)傾向于和更活躍的個(gè)體產(chǎn)生鏈接；當(dāng)共同鄰居數(shù)目不等時(shí)，如圖1(c)中，節(jié)點(diǎn) a 和 b 的共同鄰居少且均為促進(jìn)作用，但其自身的度比較?。还?jié)點(diǎn) c 與 d的共同鄰居多且均為抑制作用，但其自身的度比較大。共同鄰居與節(jié)點(diǎn)自身究竟誰(shuí)的作用更大，需要具體計(jì)算，這便是SNB模型的核心思想。

本文認(rèn)為，節(jié)點(diǎn) x 和 y 之間鏈接的產(chǎn)生受到內(nèi)部和外部因素的影響。其中，共同鄰居的作用屬于外部影響，根據(jù)LNB的相關(guān)知識(shí)，每個(gè)共同鄰居的作用不盡相同，或促進(jìn)或抑制。另一方面，鏈接的產(chǎn)生與節(jié)點(diǎn) x 和 y 自身的活躍程度密切相關(guān)，影響大小可以通過(guò)節(jié)點(diǎn)的度進(jìn)行量化。這意味著，度相同的兩對(duì)節(jié)點(diǎn)產(chǎn)生鏈接的概率會(huì)因共同鄰居貢獻(xiàn)不同而不同，受共同鄰居作用相同的兩對(duì)節(jié)點(diǎn)也會(huì)因其自身的度不同而產(chǎn)生差異?；诖怂枷?，本文綜合考慮了共同鄰居與節(jié)點(diǎn)對(duì)自身的作用，提出了融合樸素貝葉斯(SNB)鏈路預(yù)測(cè)模型。

在SNB模型下，節(jié)點(diǎn) x 和 y 產(chǎn)生鏈接的后驗(yàn)概率為：

由概率論相關(guān)知識(shí)，可得：將式(12)和式(13)分別代入式(10)和式(11)，可得：

由式(14)可知， rSx,NyBCN的值由3部分決定：共同鄰居的影響，可以通過(guò)LNB模型的式(7)得到；節(jié)點(diǎn) x 的度的影響 Rx以及節(jié)點(diǎn) y 的度的影響 Ry，可以通過(guò)下面的分析得到。其中，節(jié)點(diǎn) x 和 y 的度的影響統(tǒng)稱(chēng)為節(jié)點(diǎn)度的影響，圖2給出了式(14)的圖解?？梢钥闯觯粋€(gè)復(fù)雜的鏈路預(yù)測(cè)問(wèn)題可以分解為2個(gè)子問(wèn)題，箭頭左邊相當(dāng)于本文的SNB模型，箭頭右邊的第1部分相當(dāng)于只考慮共同鄰居的影響，屬于外部因素；第2部分相當(dāng)于只 考慮節(jié)點(diǎn)對(duì)自身的影響，屬于內(nèi)部因素。

圖 2 SNBs算法圖解Fig. 2 Algorithm diagram of SNBs

首先考慮式(14)中的第2項(xiàng)，即節(jié)點(diǎn) x 的度的影響。假設(shè)網(wǎng)絡(luò)中總的節(jié)點(diǎn)數(shù)為 m =|V|，已知x 和 y 連接，且它們的共同鄰居數(shù)為 n =|N(x,y)|，若節(jié)點(diǎn) x 產(chǎn)生新的鏈接，則新鏈接中另一個(gè)節(jié)點(diǎn)有 m-n-1-1 種可能，其中第1個(gè)1表示節(jié)點(diǎn) x不可能形成自環(huán)，第2個(gè)1表示節(jié)點(diǎn) x 和 y 不可能存在一條以上的連邊，即不考慮重復(fù)邊。進(jìn)一步的，若想要節(jié)點(diǎn) x 的度為 kx，則除了與它和節(jié)點(diǎn)y 的共同鄰居相連接外，還需要連接 kx-n-1 個(gè)節(jié)點(diǎn)，其中1表示它與節(jié)點(diǎn) y 已連接。對(duì)于后驗(yàn)概率 P (kx|exy,N(x,y))， 即在節(jié)點(diǎn) x 與 y 相連接且兩者的共同鄰居已知的條件下，求節(jié)點(diǎn) x 的度為 kx的概率，是一個(gè)如何在可與節(jié)點(diǎn) x 產(chǎn)生新鏈接的所有節(jié)點(diǎn)中選取 kx-n-1 個(gè)節(jié)點(diǎn)的組合問(wèn)題。因此，

同理可得：

然后考慮式(14)的第3項(xiàng)，即節(jié)點(diǎn) y 的度的影響。在式(14)中第2項(xiàng)已知條件的基礎(chǔ)上，已知節(jié)點(diǎn) x 的度為 kx。若節(jié)點(diǎn) y 產(chǎn)生新鏈接，則可與 y 形成新鏈接的另一個(gè)節(jié)點(diǎn)有 m -kx-1 種可能，其中 kx代表節(jié)點(diǎn) y 不可能與節(jié)點(diǎn) x 的鄰居相連，增加共同鄰居數(shù)，由于節(jié)點(diǎn) x 的鄰居已經(jīng)包括 y，所以節(jié)點(diǎn) y 不可能形成自環(huán)；1表示節(jié)點(diǎn) y與 x 不可能形成重復(fù)邊。進(jìn)一步的，若想要節(jié)點(diǎn)y 的度為 ky， 則除了與之相連的它和節(jié)點(diǎn) x 的共同鄰居外，還需要連接 ky-n-1 個(gè)節(jié)點(diǎn)，其中1表示節(jié)點(diǎn) y 與 x 已連接。則后驗(yàn)概率 P (ky|exy,N(x,y),kx)，即節(jié)點(diǎn) x 與 y 已連接且兩者的共同鄰居數(shù)和節(jié)點(diǎn)x 的度已知時(shí)，求節(jié)點(diǎn) y 的度為 ky的概率，是一個(gè)在可與 y 產(chǎn)生新鏈接的所有節(jié)點(diǎn)中選取 ky-n-1個(gè)節(jié)點(diǎn)的組合問(wèn)題：

同理，當(dāng)節(jié)點(diǎn) x 和 y 未連接時(shí)，節(jié)點(diǎn) x 的鄰居不包括 y。若節(jié)點(diǎn) y 產(chǎn)生新鏈接，則可與 y 形成新鏈接的另一個(gè)節(jié)點(diǎn)有 m -kx-1-1 種可能， 其中第1個(gè)1表示節(jié)點(diǎn) y 不可能形成自環(huán)，第2個(gè)1表示節(jié)點(diǎn) x 和 y 不可能連接。進(jìn)一步的，若想要節(jié)點(diǎn) y 的度為 ky， 它還需要連接 ky-n 個(gè)節(jié)點(diǎn)，則后驗(yàn)概率即在可與節(jié)點(diǎn) y 產(chǎn)生新鏈接的所有節(jié)點(diǎn)中選取 ky-n 個(gè)節(jié)點(diǎn)的組合問(wèn)題：

將式(7)，式(15)～(18)代入式(14)，可得：

受LNB模型的啟發(fā)，本文將SNBCN推廣到了AA和RA形式，以證明所提SNB模型的有效性。可以得到：

顯然，當(dāng)節(jié)點(diǎn) x 和 y 相連的節(jié)點(diǎn)全部相同時(shí)，SNB模型會(huì)退化為L(zhǎng)NB模型，則SNBCN、SNBAA和SNBRA指標(biāo)會(huì)退化為相應(yīng)的LNB指標(biāo)。

3 鏈路預(yù)測(cè)實(shí)驗(yàn)

所提SNB模型的有效性需要實(shí)驗(yàn)的驗(yàn)證，為此，本文將從以下幾個(gè)方面做詳細(xì)介紹。

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

本文采用的數(shù)據(jù)集為美國(guó)航空網(wǎng)絡(luò)(USAir)，包含332個(gè)機(jī)場(chǎng)和2 126條航線。網(wǎng)絡(luò)的聚類(lèi)系數(shù) C =0.749， 同配系數(shù) r =-0.208， 平均度 〈 k〉=12.81，平 均 最 短 距 離 〈d〉=2.74 ，度 異 質(zhì) 性3.46。原網(wǎng)絡(luò)為含權(quán)網(wǎng)絡(luò)，文中忽略了權(quán)重信息，將其當(dāng)作無(wú)權(quán)網(wǎng)絡(luò)處理。

3.2 基準(zhǔn)方法與評(píng)價(jià)指標(biāo)

1) 基準(zhǔn)方法

為方便評(píng)判SNB模型的性能優(yōu)劣，本文采用CN、AA和RA(記為CNs)與LNBCN、LNBAA和LNBRA(記為L(zhǎng)NBs)等作為基準(zhǔn)指標(biāo)。由于CNs和LNBs指標(biāo)在前文已作介紹，此處不再贅述。

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

鏈路預(yù)測(cè)算法多種多樣，需要統(tǒng)一的評(píng)價(jià)指標(biāo)對(duì)其進(jìn)行性能優(yōu)劣比較，本文選用AUC和精確度量化算法的準(zhǔn)確度。

AUC (area under the receiver operating characteristic curve)表示隨機(jī)從測(cè)試集 EP中選擇一條邊的分?jǐn)?shù)值比隨機(jī)選擇一條不存在的邊分?jǐn)?shù)高的概率[6]。假設(shè)一共進(jìn)行了 n 次獨(dú)立比較，其中有 n′次測(cè)試集里的邊得分高于不存在的邊得分，有 n′′次兩者得分相等，則AUC值為

精確度(precision)表示前 L 條預(yù)測(cè)邊中預(yù)測(cè)準(zhǔn)確的比例[6]。計(jì)算精確度時(shí)，將所有未知連邊(包括測(cè)試集中的邊和不存在的邊)按照其相似性分?jǐn)?shù)降序排列，然后選擇排名靠前的前 L 條邊，若有 m 條邊在測(cè)試集中，即有 m 條邊預(yù)測(cè)準(zhǔn)確，則

本實(shí)驗(yàn)中設(shè)置 L =100。

3.3 實(shí)驗(yàn)設(shè)置

本實(shí)驗(yàn)中訓(xùn)練集與測(cè)試集的劃分比例為9∶1。由于網(wǎng)絡(luò)中存在數(shù)據(jù)類(lèi)別不平衡問(wèn)題，即已知連邊與不存在連邊的數(shù)目相差很大，直接采取隨機(jī)采樣方式會(huì)嚴(yán)重影響預(yù)測(cè)效果。為此，本實(shí)驗(yàn)采用了分層采樣，在保證訓(xùn)練集與測(cè)試集中存在邊和不存在邊的比例與原網(wǎng)絡(luò)相同的條件下，隨機(jī)劃分?jǐn)?shù)據(jù)集。另外，為消除隨機(jī)誤差的影響，實(shí)驗(yàn)中采用了10折交叉驗(yàn)證方法，且重復(fù)10次后取平均值作為最終結(jié)果。

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

本部分通過(guò)兩方面內(nèi)容評(píng)估SNB模型的性能：與基準(zhǔn)指標(biāo)的預(yù)測(cè)結(jié)果比較；當(dāng)訓(xùn)練集大小發(fā)生變化時(shí)，預(yù)測(cè)結(jié)果的變化情況。

3.4.1 不同方法性能比較

當(dāng)按照9∶1的比例劃分訓(xùn)練集與測(cè)試集時(shí)，在USAir網(wǎng)絡(luò)得到的預(yù)測(cè)結(jié)果如表1所示?？梢钥闯觯?/p>

1) SNBs的AUC值最高，LNBs和CNs次之。說(shuō)明SNBs模型整體的預(yù)測(cè)準(zhǔn)確度最高。

2) SNBs比LNBs的AUC值高，說(shuō)明與單獨(dú)考慮共同鄰居相比，將共同鄰居與節(jié)點(diǎn)自身綜合考慮效果更好。

3) SNBs系列指標(biāo)中，SNBRA的AUC值最高，SNBAA次之，之后是SNBCN，LNBs系列指標(biāo)也有類(lèi)似規(guī)律，這與之前的認(rèn)識(shí)相符，即RA指標(biāo)預(yù)測(cè)效果優(yōu)于AA指標(biāo)，AA指標(biāo)預(yù)測(cè)效果優(yōu)于CN指標(biāo)，說(shuō)明懲罰大度節(jié)點(diǎn)確實(shí)可以提高預(yù)測(cè)準(zhǔn)確度，證實(shí)了文獻(xiàn)[11]中的結(jié)論。

4) SNBCN相對(duì)于LNBCN和CN的AUC的提高幅度最大，SNBAA次之，接著是SNBRA。究其原因，一方面是因?yàn)轭A(yù)測(cè)效果越差的指標(biāo)越容易提高，另一方面是因?yàn)橹苯佑?jì)算共同鄰居的貢獻(xiàn)時(shí)，節(jié)點(diǎn)自身的影響是最大的，不容忽視。且節(jié)點(diǎn)的度越大，越傾向于形成鏈接，符合優(yōu)先連接原則，因此考慮節(jié)點(diǎn)度的影響可以極大地提高準(zhǔn)確度。而SNBAA和SNBRA認(rèn)為，度越大的節(jié)點(diǎn)貢獻(xiàn)越小，這與優(yōu)先連接思想相悖，相當(dāng)于將節(jié)點(diǎn)度對(duì)其自身的影響中和掉了一部分，導(dǎo)致AUC提高的幅度變小。

5) 對(duì)于精確度值，SNBs整體上與LNBs和CNs相差不大，甚至有所下降，可能是因?yàn)樵陬A(yù)測(cè) 的前100條邊中，節(jié)點(diǎn)受其自身度的影響不大。

表 1 CNs、LNBs和SNBs在USAir上的預(yù)測(cè)結(jié)果Table 1 Prediction results of CNs， LNBs and SNBs on USAir

綜上，可以得到如下結(jié)論：

1) SNBs的AUC值較LNBs和CNs明顯提高，說(shuō)明SNB模型傾向于賦予預(yù)測(cè)集中的鏈接更高的分?jǐn)?shù)，即整體上SNBs能夠更好地將測(cè)試集中的邊與不存在的邊區(qū)分開(kāi)。

2) 3種方法的精確度變化不明顯，說(shuō)明三者對(duì)測(cè)試集中邊的排序位置相差不大。

3) SNBs能夠在基本保證前100條邊中預(yù)測(cè)準(zhǔn)確率一定的條件下，將更多地測(cè)試鏈接識(shí)別出來(lái)，證明了其有效性。

3.4.2 預(yù)測(cè)效果隨訓(xùn)練集大小的變化情況

本實(shí)驗(yàn)中，訓(xùn)練集比例從0.6開(kāi)始，步長(zhǎng)為0.1，直到比例達(dá)到0.9，得到的CNs, LNBs,SNBs的AUC和精確度隨訓(xùn)練集大小變化情況如圖3和4所示。

圖 3 CNs、LNBs和SNBs的AUC值隨訓(xùn)練集大小的變化情況Fig. 3 Variation of AUC value of CNs， LNBs and SNBs with training set size

圖 4 CNs、LNBs和SNBs的精確度隨訓(xùn)練集大小的變化情況Fig. 4 Variation of Precision value of CNs， LNBs and SNBs with training set size

圖3(a)中，SNBCN的AUC值始終高于LNBCN和CN，證明了SNB模型的高效性；圖3(b)和(c)的變化趨勢(shì)相似，當(dāng)訓(xùn)練集比例較小時(shí)，SNBRA和SNBAA的AUC值均最低，隨著訓(xùn)練集的增大，SNBs與其他指標(biāo)的差距逐漸減小，并在訓(xùn)練集比例為0.9時(shí)超過(guò)其他指標(biāo)，說(shuō)明SNB模型在訓(xùn)練集比例為0.9時(shí)的總體預(yù)測(cè)準(zhǔn)確度最高。

圖4(a)和圖4(b)具有一致的變化趨勢(shì)，即SNBs的精確度略低于LNBs和CNs指標(biāo)，而圖4(c)中SNBRA的精確度值一直處于或接近最高值，可能是因?yàn)椋汗?jié)點(diǎn)自身影響不能簡(jiǎn)單地用度進(jìn)行量化，將節(jié)點(diǎn)度與資源分配思想結(jié)合可以取得更好的預(yù)測(cè)性能。

結(jié)合圖3與圖4，可以得出以下結(jié)論：

1) 隨著訓(xùn)練集比例增大，幾種指標(biāo)的AUC值均呈增長(zhǎng)趨勢(shì)，而精確度值均呈遞減趨勢(shì)，這可能是由于AUC和精確度本身的側(cè)重點(diǎn)不同造成的。其中，AUC側(cè)重于總體的預(yù)測(cè)準(zhǔn)確率，當(dāng)訓(xùn)練集比較大(已知信息豐富)時(shí)，預(yù)測(cè)缺失邊越容易，AUC值越高；精確度側(cè)重于前 L 條邊的預(yù)測(cè)準(zhǔn)確率，當(dāng)測(cè)試集比例較大時(shí)，前 L 條預(yù)測(cè)邊在測(cè)試集的可能性越大，精確度越高。

2) 當(dāng)SNB模型的AUC值較低時(shí)，精確度值一般最高或接近最高；同理，當(dāng)其精確度值較低時(shí)，AUC值一般最高或接近最高，說(shuō)明SNB模型的AUC和精確度一定有一個(gè)最高值，進(jìn)一步從側(cè)面印證了SNB模型的有效性。

4 總結(jié)與展望

近來(lái)，有文獻(xiàn)指出：社交網(wǎng)絡(luò)中鏈接的產(chǎn)生受內(nèi)部和外部因素的影響。受此思想的啟發(fā)，本文在局部樸素貝葉斯(LNB)的基礎(chǔ)上，結(jié)合節(jié)點(diǎn)度的自身影響，提出了融合樸素貝葉斯(SNB)模型。該模型易于推廣到其他的基于共同鄰居的指標(biāo)形式，如AA和RA具有良好的可擴(kuò)展性。在美國(guó)航空網(wǎng)(USAir)上的實(shí)驗(yàn)結(jié)果表明：與基準(zhǔn)方法相比，提高了鏈路預(yù)測(cè)性能，證實(shí)了該方法的有效性。由此得出結(jié)論：鏈接的產(chǎn)生不僅受到共同鄰居的影響，也受到其自身度的影響，將二者綜合考慮更加合理。

未來(lái)，將嘗試將該思想推廣到智能方法做鏈路預(yù)測(cè)，如支持向量機(jī)、相關(guān)向量機(jī)等。另外，考慮到本文研究的是無(wú)權(quán)無(wú)向網(wǎng)絡(luò)，以后可以先在更多不同領(lǐng)域的網(wǎng)絡(luò)上實(shí)現(xiàn)，然后再著眼于加權(quán)網(wǎng)絡(luò)的研究。