劉昱陽(yáng)，李龍杰，單 娜，陳曉云

(蘭州大學(xué) 信息科學(xué)與工程學(xué)院，蘭州 730000)

0 引言

鏈接預(yù)測(cè)[1]是復(fù)雜網(wǎng)絡(luò)分析中的重要研究方向，得到了越來(lái)越多的關(guān)注。鏈接預(yù)測(cè)根據(jù)網(wǎng)絡(luò)中已知信息預(yù)測(cè)網(wǎng)絡(luò)中丟失的鏈接或者未來(lái)可能出現(xiàn)的鏈接，在網(wǎng)絡(luò)分析中起著非常重要的作用，可以用于指導(dǎo)生物實(shí)驗(yàn)、重建網(wǎng)絡(luò)結(jié)構(gòu)以及模擬網(wǎng)絡(luò)演化等。鏈接預(yù)測(cè)在許多實(shí)際問(wèn)題中都有很高的應(yīng)用價(jià)值，不同領(lǐng)域的學(xué)者都可以利用其作為工具輔助本領(lǐng)域的研究。例如，在生物學(xué)領(lǐng)域，生物學(xué)家可以利用鏈接預(yù)測(cè)篩選潛在的蛋白質(zhì)相互作用關(guān)系[2]和進(jìn)行腦功能網(wǎng)絡(luò)研究[3]，能夠減少實(shí)際實(shí)驗(yàn)的次數(shù)以及降低實(shí)驗(yàn)成本。對(duì)于在線社交網(wǎng)絡(luò)[4]、電子商務(wù)網(wǎng)絡(luò)[5]和航空運(yùn)輸網(wǎng)絡(luò)[6]，都可以利用鏈接預(yù)測(cè)來(lái)增加其商業(yè)價(jià)值。在在線社交網(wǎng)絡(luò)中，鏈接預(yù)測(cè)可以發(fā)現(xiàn)用戶的潛在朋友[7]，并通過(guò)把預(yù)測(cè)結(jié)果推薦給用戶的方式來(lái)增加用戶關(guān)聯(lián)，同時(shí)用于提高用戶的活躍度與忠誠(chéng)度。

截至目前，學(xué)者們提出了大量基于相似性的鏈接預(yù)測(cè)方法，這些方法給節(jié)點(diǎn)對(duì)分配相似性分?jǐn)?shù)，利用所分配的分?jǐn)?shù)估計(jì)兩個(gè)節(jié)點(diǎn)間存在鏈接的可能性，節(jié)點(diǎn)間的相似性分?jǐn)?shù)越高，它們之間存在鏈接的可能性就越大?；诰W(wǎng)絡(luò)結(jié)構(gòu)特征評(píng)估節(jié)點(diǎn)間的相似性是目前的一個(gè)主要研究方向。共同鄰居(Common Neighbors，CN)指標(biāo)[8]是其中最簡(jiǎn)單的一個(gè)，它基于兩個(gè)節(jié)點(diǎn)共同鄰居的數(shù)量進(jìn)行預(yù)測(cè)，共同鄰居數(shù)量越多，這兩個(gè)節(jié)點(diǎn)間存在鏈接的可能性就越高。相關(guān)方法還有考慮對(duì)大度節(jié)點(diǎn)進(jìn)行懲罰的資源分配(Resource Allocation, RA)指標(biāo)[9]以及AA(Adamic-Adar)指標(biāo)[10]等。上述方法基于節(jié)點(diǎn)的共同鄰居信息，而局部路徑(Local Path, LP)指標(biāo)[9]、Katz指標(biāo)[11]等考慮節(jié)點(diǎn)間的路徑信息。除此之外還有基于隨機(jī)游走的相似性指標(biāo)，如平均通勤時(shí)間(Average Commute Time, ACT)指標(biāo)[12]、基于隨機(jī)游走的余弦相似性(Cos+)指標(biāo)[13]、有重啟的隨機(jī)游走(Random Walk with Restart, RWR)指標(biāo)[14]和SimRank指標(biāo)[15]等。以及基于網(wǎng)絡(luò)局部隨機(jī)游走的LRW(Local Random Walk)指標(biāo)[16]和SRW(Superposed Random Walk)指標(biāo)[16]。

節(jié)點(diǎn)的聚集系數(shù)是一種常用的網(wǎng)絡(luò)結(jié)構(gòu)信息，用于度量節(jié)點(diǎn)的鄰居之間鏈接的密度。許多鏈接預(yù)測(cè)模型使用節(jié)點(diǎn)的聚集系數(shù)來(lái)評(píng)估該節(jié)點(diǎn)的兩個(gè)鄰居之間存在鏈接的概率?；诰奂禂?shù)的鏈接預(yù)測(cè)方法(Clustering Coefficient for Link Prediction，CCLP)[17]將兩個(gè)節(jié)點(diǎn)的共同鄰居的聚集系數(shù)之和作為這兩個(gè)節(jié)點(diǎn)的相似度值。局部樸素貝葉斯(Local Naive Bayes, LNB)模型[18]利用貝葉斯分類器理論計(jì)算節(jié)點(diǎn)間存在鏈接的可能性。該模型認(rèn)為不同的鄰居對(duì)相似性的計(jì)算可能有不同的貢獻(xiàn)，并使用鄰居的聚集系數(shù)來(lái)表示其貢獻(xiàn)。中間概率(InterMediary Probability, IMP)模型[19]是一種廣義的概率評(píng)估模型，它可以根據(jù)節(jié)點(diǎn)間的不同特征來(lái)評(píng)估其存在概率的可能性。IMP_CN(InterMediate Probability model based on Common Neighbor)是基于IMP模型衍生的鏈接預(yù)測(cè)算法[19]，該算法將節(jié)點(diǎn)間的共同鄰居作為特征，鄰居的聚集系數(shù)作為中間概率。最近，Wu等[20]定義了非對(duì)稱鏈接聚集系數(shù)(Asymmetric Link Clustering Coefficient, ALCC)，該聚集系數(shù)計(jì)算經(jīng)過(guò)一條鏈接的三角形的概率。與文獻(xiàn)[21]中提出的鏈接聚集系數(shù)不同，ALCC將鏈接的一個(gè)端點(diǎn)定義為要預(yù)測(cè)鏈接的節(jié)點(diǎn)，另一個(gè)端點(diǎn)為鄰居節(jié)點(diǎn)。用ALCC替換了CCLP方法、LNB模型中節(jié)點(diǎn)的聚集系數(shù)，提升了鏈接預(yù)測(cè)的精度[20]。

節(jié)點(diǎn)的聚集系數(shù)與非對(duì)稱鏈接聚集系數(shù)從不同的角度度量了兩個(gè)節(jié)點(diǎn)間存在鏈接的可能性。本文考慮將兩者進(jìn)行結(jié)合以得到一個(gè)綜合的度量指標(biāo)，并使用該指標(biāo)評(píng)估節(jié)點(diǎn)間存在鏈接的可能性。本文方法使用Dempster-Shafer(DS)證據(jù)理論[22]將兩種聚集系數(shù)進(jìn)行融合，并且將融合后的度量指標(biāo)引入到IMP模型[19]中設(shè)計(jì)了一個(gè)新的鏈接預(yù)測(cè)方法。為驗(yàn)證本文所提方法的性能，在多個(gè)網(wǎng)絡(luò)數(shù)據(jù)上進(jìn)行了實(shí)驗(yàn)，結(jié)果表明，與其他方法相比，本文提出的方法取得了較好的預(yù)測(cè)效果。

1 相關(guān)工作

1.1 IMP_CN算法

IMP算法是一種廣義的概率模型，可以利用不同的網(wǎng)絡(luò)特征評(píng)估節(jié)點(diǎn)間存在鏈接的可能性，IMP模型公式如式(1)：

(1)

(2)

(3)

1.2 CN指標(biāo)

CN指標(biāo)認(rèn)為：兩個(gè)不連接的節(jié)點(diǎn)如果有更多的共同鄰居，則它們更傾向于連邊。CN指標(biāo)定義兩個(gè)節(jié)點(diǎn)x和y的相似性為其共同鄰居的數(shù)量，即：

Sxy=|Oxy|

(4)

1.3 AA指標(biāo)

AA(Adamic-Adar)指標(biāo)認(rèn)為度小的共同鄰居的貢獻(xiàn)大于度大的共同鄰居，因此為每個(gè)鄰居節(jié)點(diǎn)賦一個(gè)權(quán)重值。該權(quán)重等于該節(jié)點(diǎn)的度的對(duì)數(shù)的倒數(shù)，其定義為：

(5)

1.4 RA指標(biāo)

RA(Resource Allocation)指標(biāo)受網(wǎng)絡(luò)中資源分配過(guò)程的啟發(fā)。考慮網(wǎng)絡(luò)中不相連的兩個(gè)節(jié)點(diǎn)x和y，從x可以傳遞一些資源到y(tǒng)，在這個(gè)過(guò)程中，共同鄰居就成為資源傳遞的媒介。假設(shè)每個(gè)媒介將得到的資源平均分配給它的鄰居，則y可以接收到的資源數(shù)就定義為節(jié)點(diǎn)x和y的相似度，即：

(6)

2 Dempster-Shafer證據(jù)理論

Dempster-Shafer(DS)證據(jù)理論，以其表示和處理不確定信息的能力而聞名，DS融合規(guī)則可以使命題得到不同來(lái)源信息的綜合支持度。最早應(yīng)用于專家系統(tǒng)中，用于根據(jù)多個(gè)信息源的不確定性信息[23]作出決策。例如，針對(duì)供應(yīng)商選擇問(wèn)題，Liu等[24]提出了一種模糊拓展分析網(wǎng)絡(luò)方法，該方法利用DS證據(jù)理論解決專家判斷中的認(rèn)知不確定問(wèn)題。DS證據(jù)理論還應(yīng)用于處理傳感器信息融合系統(tǒng)中的不確定性，Ye等[25]提出了一種基于灰色關(guān)聯(lián)和DS證據(jù)理論的不確定性融合算法，解決了傳感器之間的不一致性和監(jiān)測(cè)環(huán)境的復(fù)雜性帶來(lái)的不確定性問(wèn)題。Jiang等[26]將Z-number模型與DS證據(jù)理論進(jìn)行結(jié)合，對(duì)傳感器數(shù)據(jù)融合系統(tǒng)中的不確定性進(jìn)行建模和處理，提高了故障檢測(cè)的可靠性。此外，DS證據(jù)理論還用于解決服務(wù)器集群負(fù)載不均衡的問(wèn)題[27]。為了更好地解釋DS證據(jù)理論，本文接下來(lái)介紹一些相關(guān)概念。

定義1 識(shí)別框架(Frame Of Discernment, FOD)。給定一組基本的命題E1,E2,…,Ei,…,En，命題Ei是Φ的基本元素，表示如下：

Φ={E1,E2,…,Ei,…,En}

(7)

要求Φ中的元素是相互排斥的并且是完備的。在DS理論中，Φ被就稱為識(shí)別框架。符號(hào)2Φ表示Φ的冪集：

2Φ={?,{E1},{E2},…,{En},{E1,E2},…,Φ}

(8)

其中?表示空集。

定義2 基本概率分配函數(shù)。在識(shí)別框架Φ上的基本概率分配函數(shù)是一個(gè)從2Φ到[0,1]的映射函數(shù)，用于給各命題分配信任程度，記作m：

m:2Φ→[0,1]

(9)

此函數(shù)滿足如下性質(zhì):

其中m(A)反映對(duì)命題A的信任程度大小。

定義3 Dempster合成規(guī)則。給定兩個(gè)獨(dú)立的基本概率分配函數(shù)m1和m2，Dempster合成規(guī)則根據(jù)m1、m2產(chǎn)生一個(gè)新的基本概率分配函數(shù)，新的基本概率分配函數(shù)表示為m=m1⊕m2，具體公式如下：

(10)

(11)

Dempster合成規(guī)則既滿足結(jié)合律，又滿足交換律：

m1⊕m2=m2⊕m1

(12)

(m1⊕m2)⊕m3=m1⊕(m2⊕m3)

(13)

3 本文方法

在鏈接預(yù)測(cè)中，節(jié)點(diǎn)聚集系數(shù)和非對(duì)稱鏈接聚集系數(shù)分別從不同的角度定義了共同鄰居對(duì)兩個(gè)節(jié)點(diǎn)之間是否存在鏈接的評(píng)估。本文利用DS證據(jù)理論將兩者進(jìn)行融合得到一個(gè)綜合性度量指標(biāo)，利用該指標(biāo)去評(píng)估節(jié)點(diǎn)間存在鏈接的概率。最后將融合后的度量指標(biāo)與IMP模型相結(jié)合，設(shè)計(jì)了一個(gè)新的鏈接預(yù)測(cè)方法，記為IMP_DS。接下來(lái)，首先對(duì)兩種聚集系數(shù)進(jìn)行介紹，然后給出IMP_DS方法的流程，并通過(guò)例子演示了IMP_DS方法的計(jì)算過(guò)程。

3.1 節(jié)點(diǎn)聚集系數(shù)

聚集系數(shù)用于衡量網(wǎng)絡(luò)中節(jié)點(diǎn)的聚集程度，其定義建立在網(wǎng)絡(luò)中的“三角形”結(jié)構(gòu)之上。節(jié)點(diǎn)的聚集系數(shù)定義為該節(jié)點(diǎn)與其鄰居之間組成的三角形的個(gè)數(shù)與所有可能的三角形個(gè)數(shù)之比。給定節(jié)點(diǎn)z，其聚集系數(shù)的計(jì)算如式(12)所示：

(14)

其中：N△表示節(jié)點(diǎn)z與其鄰居之間的三角形個(gè)數(shù)；kz表示節(jié)點(diǎn)z的度，kz(kz-1)/2表示最大可能的三角形個(gè)數(shù)。

3.2 非對(duì)稱性鏈接聚集系數(shù)

非對(duì)稱鏈接聚集系數(shù)[20]的定義原理與節(jié)點(diǎn)的聚集系數(shù)相似，其定義為通過(guò)一條鏈接的三角形個(gè)數(shù)除以可能的最大三角形個(gè)數(shù)。這里，最大三角形個(gè)數(shù)只與節(jié)點(diǎn)對(duì)中的某一點(diǎn)相關(guān)，這個(gè)點(diǎn)為共同鄰居節(jié)點(diǎn)。給定節(jié)點(diǎn)x與y，z是它們的一個(gè)共同鄰居，鏈接(x,z)的非對(duì)稱聚集系數(shù)定義為：

(15)

其中：Oxz表示節(jié)點(diǎn)x和z的共同鄰居集合；|Oxz|表示集合Oxz中元素?cái)?shù)量。

式(13)表明，LCx,z是非對(duì)稱的，只在節(jié)點(diǎn)x與節(jié)點(diǎn)z的度相同時(shí)LCx,z與LCz,x才相等。本文使用的鏈接聚集系數(shù)分別為L(zhǎng)Cx,z與LCy,z。

3.3 IMP_DS方法

給定節(jié)點(diǎn)x與y，z為它們的一個(gè)共同鄰居。Cz、LCx,z和LCy,z從不同的角度度量了x、y之間存在鏈接的概率。本文將三種聚集系數(shù)進(jìn)行融合得到一個(gè)新的度量指標(biāo)，然后將融合后的指標(biāo)引入IMP模型中，設(shè)計(jì)一個(gè)新的鏈接預(yù)測(cè)方法。本文方法包含三步，具體的過(guò)程介紹如下。

1)首先，將鄰居z的兩個(gè)非對(duì)稱鏈接聚集系數(shù)相結(jié)合，得到z的平均鏈接聚集系數(shù)LCz，定義如下:

(16)

(17)

(18)

以及

(19)

(20)

定義mf為融合后的基本概率分配函數(shù)，則：

(21)

(22)

(23)

接下來(lái)通過(guò)一個(gè)例子描述IMP_DS方法的計(jì)算過(guò)程。

例1 利用IMP_DS算法計(jì)算節(jié)點(diǎn)的相似性。在圖1所示的網(wǎng)絡(luò)中，節(jié)點(diǎn)對(duì)(x,y)有4個(gè)共同鄰居，分別是z1,z2,z3,z4。使用IMP_DS算法評(píng)估x、y之間的相似性，首先計(jì)算4個(gè)鄰居的節(jié)點(diǎn)聚集系數(shù)和鏈接聚集系數(shù)，結(jié)果如下：

圖1 描述IMP_DS計(jì)算過(guò)程的示意網(wǎng)絡(luò)Fig. 1 Schematic network used to show computation process of IMP_DS

之后對(duì)每一個(gè)共同鄰居的節(jié)點(diǎn)聚集系數(shù)與鏈接聚集系數(shù)進(jìn)行融合，得到相應(yīng)的融合概率，結(jié)果如下：

將融合后的概率代入IMP_DS的計(jì)算公式中，得到節(jié)點(diǎn)對(duì)(x,y)相似性分?jǐn)?shù)為：

4 實(shí)驗(yàn)數(shù)據(jù)集與評(píng)價(jià)指標(biāo)

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

本文選取了9個(gè)真實(shí)網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)及分析，網(wǎng)絡(luò)的簡(jiǎn)單介紹如下。

1)Florida[28]：弗洛里達(dá)海灣雨季的食物鏈網(wǎng)絡(luò)。

2)Word[29]：小說(shuō)《大衛(wèi)·科波菲爾》中常見(jiàn)形容詞和名詞的鄰接網(wǎng)絡(luò)。

3)Karate[30]：70年代美國(guó)一所大學(xué)空手道俱樂(lè)部34名成員之間的友誼網(wǎng)絡(luò)。

4)Cypwet[31]：賽普拉斯海灣雨季食物鏈網(wǎng)絡(luò)。

5)Jazz[32]：爵士樂(lè)音樂(lè)家之間的協(xié)作網(wǎng)絡(luò)。

6)Celegansneural(CE)[33]：線蟲(chóng)Caenorhabditis elegans的神經(jīng)網(wǎng)絡(luò)。

7)Polblogs(PB)[34]：政治博客網(wǎng)絡(luò)。

8)Yeast[29]：酵母蛋白質(zhì)相互作用網(wǎng)絡(luò)。

9)Lesmis[35]：小說(shuō)《悲慘世界》中人物的同時(shí)出現(xiàn)的網(wǎng)絡(luò)。

表1展示了9個(gè)網(wǎng)絡(luò)的基本拓?fù)浣Y(jié)構(gòu)，其中：|V|表示網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量，|E|表示網(wǎng)絡(luò)中鏈接數(shù)量，C表示網(wǎng)絡(luò)的平均聚集系數(shù)，r表示網(wǎng)絡(luò)的同配系數(shù)，k表示節(jié)點(diǎn)的平均度，d表示平均最短距離，Nd表示網(wǎng)絡(luò)密度。

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

本文采用受試者工作特征(Receiver Operating Characteristic, ROC)曲線下方面積(Area Under the ROC Curve, AUC)[36]與精度值(Precision)[37]兩種指標(biāo)衡量鏈接預(yù)測(cè)算法的性能。實(shí)驗(yàn)中，將網(wǎng)絡(luò)中的鏈接集合隨機(jī)劃分為訓(xùn)練集Etr與測(cè)試集Ets，其滿足：

Etr∪Ets=E

(24)

Etr∩Ets=?

(25)

AUC是一種依靠整體排名結(jié)果的度量，類似于概率。具體定義如下：進(jìn)行n次獨(dú)立比較，每次獨(dú)立比較都從測(cè)試集和不存在的鏈接中分別取一條鏈接，鏈接預(yù)測(cè)算法根據(jù)訓(xùn)練集信息分別對(duì)兩條鏈接進(jìn)行評(píng)分。如果一個(gè)算法有較好的預(yù)測(cè)性能，測(cè)試集中鏈接的對(duì)應(yīng)指標(biāo)分?jǐn)?shù)應(yīng)該比不存在的鏈接的分?jǐn)?shù)要高。因此，假設(shè)在n次獨(dú)立比較中，測(cè)試集鏈接比不存在鏈接擁有更高分?jǐn)?shù)n′次，兩者擁有相同分?jǐn)?shù)n″次，則對(duì)應(yīng)AUC的計(jì)算公式如下：

(26)

AUC值越高，鏈接預(yù)測(cè)算法的預(yù)測(cè)準(zhǔn)確度越高。隨機(jī)預(yù)測(cè)的AUC值約等于0.5，因此AUC大于0.5的程度表明了相應(yīng)算法在多大程度上比隨機(jī)預(yù)測(cè)的方法更精確。

Precision定義為將訓(xùn)練集與網(wǎng)絡(luò)中所有不存在鏈接按照相似性分?jǐn)?shù)進(jìn)行降序排列，計(jì)算前L個(gè)鏈接中屬于訓(xùn)練集的鏈接所占比例。如果排名前L的鏈接中有l(wèi)個(gè)屬于測(cè)試集，則Precision計(jì)算公式為：

(27)

5 實(shí)驗(yàn)結(jié)果及分析

以AUC與Precision為衡量指標(biāo)，在9個(gè)真實(shí)網(wǎng)絡(luò)中測(cè)試IMP_DS算法的預(yù)測(cè)效果，具體結(jié)果分為兩部分：一是在不同網(wǎng)絡(luò)中IMP_DS與其他相似性指標(biāo)的對(duì)比結(jié)果分析；二是IMP_DS性能提升的原因分析。

5.1 與其他相似性指標(biāo)對(duì)比

表2給出了CN、AA、RA、IMP_CN以及IMP_DS 5種算法在各個(gè)網(wǎng)絡(luò)上的AUC與Precision的實(shí)驗(yàn)結(jié)果，表中加粗字體表明效果最好。兩個(gè)表中的結(jié)果均為50次獨(dú)立實(shí)驗(yàn)的平均值，每次實(shí)驗(yàn)中，原始網(wǎng)絡(luò)被隨機(jī)地劃分為一個(gè)訓(xùn)練集和一個(gè)測(cè)試集，其中訓(xùn)練集占90%的鏈接，測(cè)試集占10%的鏈接。表2中的Precision是取L=10時(shí)的實(shí)驗(yàn)結(jié)果。

從表2中可以看出，IMP_DS算法在Florida、Word、Cypwet、CE和PB 5個(gè)網(wǎng)絡(luò)上取得最好的AUC結(jié)果。在Karate上，RA的AUC值最高，IMP_DS第二。在其他3個(gè)網(wǎng)絡(luò)上，IMP_DS的性能與IMP_CN非常接近。結(jié)果表明融合兩種聚集系數(shù)的方法在IMP模型上是可行的，并且比單一的節(jié)點(diǎn)聚集系數(shù)的效果更好。特別地，在Florida和Cypwet兩個(gè)網(wǎng)絡(luò)上，與其他算法相比，IMP_DS的AUC結(jié)果提升非常明顯。從表1中可以看到：Florida和Cypwet兩個(gè)網(wǎng)絡(luò)的密度非常高，是兩個(gè)非常稠密的網(wǎng)絡(luò)，因此，兩個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)聚集系數(shù)和鏈接聚集系數(shù)都非常高，通過(guò)融合節(jié)點(diǎn)聚集系數(shù)和鏈接聚集系數(shù)能夠顯著提高鏈接預(yù)測(cè)的性能。相反地，在Yeast這個(gè)特別稀疏的網(wǎng)絡(luò)上，IMP_DS以及IMP_CN兩個(gè)方法的AUC值均低于CN、AA和RA三個(gè)方法。這是因?yàn)橄∈杈W(wǎng)絡(luò)上的節(jié)點(diǎn)間的共同鄰居數(shù)據(jù)很少，并且節(jié)點(diǎn)的聚集系數(shù)和鏈接聚集系數(shù)的值也變得非常低，降低了IMP模型的性能[19]。

表2中的Precision結(jié)果再次證明IMP_DS方法的預(yù)測(cè)精度高于對(duì)比算法。例如，在Florida網(wǎng)絡(luò)上，IMP_DS方法的預(yù)測(cè)精度相比CN、AA、RA和IMP_CN算法分別提高了130.9%、139.5%、169.4%和106.4%，因此本文認(rèn)為融合共同鄰居的節(jié)點(diǎn)聚集系數(shù)與非對(duì)稱鏈接聚集系數(shù)能夠明顯提高IMP模型的預(yù)測(cè)精度。

接下來(lái)，在9個(gè)網(wǎng)絡(luò)上選取不同比例的訓(xùn)練集進(jìn)行實(shí)驗(yàn)，觀察AUC的結(jié)果與變化趨勢(shì)。本實(shí)驗(yàn)的結(jié)果也是50次獨(dú)立實(shí)驗(yàn)的平均值。圖2描述了從E中選取不同比例訓(xùn)練集Etr(從0.7到0.9)時(shí)各預(yù)測(cè)方法AUC的變化情況。從圖2中可以看出，在不同比例訓(xùn)練集的情況下，IMP_DS在超過(guò)一半的網(wǎng)絡(luò)上都獲得了較高的AUC值。觀察AUC的變化趨勢(shì)發(fā)現(xiàn)，當(dāng)訓(xùn)練集的比例從0.7上升到0.9時(shí)，AUC值呈明顯上升趨勢(shì)。這是因?yàn)?，?xùn)練集Etr的比例越大，為訓(xùn)練提供的信息越多，預(yù)測(cè)越準(zhǔn)確；相反，低比例的Etr會(huì)增加鏈接預(yù)測(cè)的難度[38]。

圖2 不同比例訓(xùn)練集時(shí)的AUC結(jié)果Fig. 2 AUC values under different proportions of training set

圖3描述訓(xùn)練集Etr的比例從0.7增長(zhǎng)到0.9時(shí)Precision的變化趨勢(shì)，L的值同樣設(shè)置為10。

從圖3中可以看出，與AUC相比，Precision隨著訓(xùn)練集比例變化呈現(xiàn)相反的變化趨勢(shì)，即當(dāng)比例從0.7上升到0.9時(shí)，Precision值呈現(xiàn)下降趨勢(shì)。這是因?yàn)橛?xùn)練集Etr的減少會(huì)導(dǎo)致AUC定義中n′與n″變小，從而降低AUC的值[39]，但是，隨著測(cè)試集Ets的提高(訓(xùn)練集Etr減小)，獲得相關(guān)信息的可能性增加，使得發(fā)現(xiàn)缺失鏈接更容易[39]。比較各個(gè)方法的Precision值，整體而言，IMP_DS在不同比例訓(xùn)練集上的性能均優(yōu)于對(duì)比方法。

圖3 不同比例訓(xùn)練集時(shí)的Precision結(jié)果Fig. 3 Precision values under different proportions of training set

圖4顯示了在取不同L值時(shí)每個(gè)方法的Precision值及變化趨勢(shì)。圖4中，訓(xùn)練集與測(cè)試集的比例為9∶1，結(jié)果仍然是50次獨(dú)立實(shí)驗(yàn)的平均值。這里，只給出了在6個(gè)較大網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果。從圖4中可以看出，在這6個(gè)網(wǎng)絡(luò)上，IMP_DS的性能具有明顯的優(yōu)勢(shì)，尤其是在Flodria、Cypwet和PB 3個(gè)網(wǎng)絡(luò)中，其Precision值顯著高于對(duì)比方法。在不同的網(wǎng)絡(luò)上，其他方法的排序隨著L取值改變有較大變化。例如，在PB網(wǎng)絡(luò)上，隨著L的改變各種方法的排序基本不變，但是在Jazz與CE網(wǎng)絡(luò)上，4種對(duì)比方法的排序有很大波動(dòng)。另外，在大多數(shù)網(wǎng)絡(luò)中，隨著L值的增大，Precision呈現(xiàn)逐漸下降的趨勢(shì)。這是因?yàn)長(zhǎng)的增加，使得發(fā)現(xiàn)丟失鏈接的概率降低，從而導(dǎo)致精度值降低[38]。

5.2 IMP_DS性能提升原因分析

最后，通過(guò)實(shí)例分析的方式進(jìn)一步研究IMP_DS性能提升的原因。參考文獻(xiàn)[19]中的分析方法，圖5選取了四個(gè)對(duì)比算法預(yù)測(cè)的前100條鏈接，并將這100條鏈接在不同算法的排名進(jìn)行對(duì)比。本文實(shí)驗(yàn)中，將PB隨機(jī)劃分成一個(gè)訓(xùn)練集和一個(gè)測(cè)試集，訓(xùn)練集和測(cè)試集的比例是9∶1。圖5中，使用半對(duì)數(shù)坐標(biāo)繪制了每一對(duì)算法預(yù)測(cè)的前100條鏈接的相對(duì)排序。以圖5(c)(d)子圖為例，(c)子圖表示AA預(yù)測(cè)的前100條鏈接在IMP_DS結(jié)果中的排序，(d)子圖表示IMP_DS預(yù)測(cè)的前100條鏈接在AA結(jié)果中的排序。觀察圖中的結(jié)果可以發(fā)現(xiàn)，AA預(yù)測(cè)的前100條鏈接中，41條是正確的，59條是錯(cuò)誤的，而IMP_DS將這些錯(cuò)誤結(jié)果中的大部分排在了100～1 000。另一方面，IMP_DS預(yù)測(cè)的前100條鏈接中，52條是正確的，48條是錯(cuò)誤的，而AA將正確預(yù)測(cè)結(jié)果中的20條排在了100以外，因此，IMP_DS能夠取得比AA更高的預(yù)測(cè)精度。其他三個(gè)子圖上的結(jié)果也與此類似。

圖5 各算法在PB網(wǎng)絡(luò)上預(yù)測(cè)的前100條鏈接的對(duì)比Fig. 5 Comparison of top- 100 predicted links of different algorithms on PB network

6 結(jié)語(yǔ)

針對(duì)許多基于網(wǎng)絡(luò)結(jié)構(gòu)信息的鏈接預(yù)測(cè)算法只考慮節(jié)點(diǎn)的聚集系數(shù)，而忽略了預(yù)測(cè)節(jié)點(diǎn)與共同鄰居節(jié)點(diǎn)之間鏈接的聚集系數(shù)對(duì)鏈接預(yù)測(cè)影響的問(wèn)題，本文提出了一種基于Dempster-Shafer證據(jù)理論，融合節(jié)點(diǎn)聚集系數(shù)和非對(duì)稱鏈接聚集系數(shù)的鏈接預(yù)測(cè)算法。首先，針對(duì)每個(gè)共同鄰居節(jié)點(diǎn)計(jì)算出對(duì)應(yīng)的聚集系數(shù)和平均鏈接聚集系數(shù)；然后，將兩種聚集系數(shù)進(jìn)行融合得到一個(gè)綜合性度量指標(biāo)；最后將這個(gè)綜合性度量指標(biāo)應(yīng)用于中間概率模型，得到一個(gè)新的節(jié)點(diǎn)間相似性指標(biāo)。在9個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果表明，IMP_DS方法具有較高的AUC與Precision值，可以用于復(fù)雜網(wǎng)絡(luò)鏈接預(yù)測(cè)。盡管本文設(shè)計(jì)的融合兩種聚集系數(shù)的鏈接預(yù)測(cè)算法取得了優(yōu)秀的預(yù)測(cè)效果，但仍有許多問(wèn)題待解決，例如可以進(jìn)一步研究不同特征的融合以及具體融合過(guò)程對(duì)鏈接預(yù)測(cè)效果的影響。