融合聚集系數(shù)的鏈接預(yù)測方法

劉昱陽，李龍杰，單 娜，陳曉云

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

0 引言

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

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

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

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

1 相關(guān)工作

1.1 IMP_CN算法

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

(1)

(2)

(3)

1.2 CN指標

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

Sxy=|Oxy|

(4)

1.3 AA指標

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

(5)

1.4 RA指標

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

(6)

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

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

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

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

(7)

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

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

(8)

其中?表示空集。

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

m:2Φ→[0,1]

(9)

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

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

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

(10)

(11)

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

m1⊕m2=m2⊕m1

(12)

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

(13)

3 本文方法

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

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

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

(14)

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

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

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

(15)

其中：Oxz表示節(jié)點x和z的共同鄰居集合；|Oxz|表示集合Oxz中元素數(shù)量。

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

3.3 IMP_DS方法

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

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

(16)

(17)

(18)

以及

(19)

(20)

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

(21)

(22)

(23)

接下來通過一個例子描述IMP_DS方法的計算過程。

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

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

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

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

4 實驗數(shù)據(jù)集與評價指標

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

本文選取了9個真實網(wǎng)絡(luò)進行實驗及分析，網(wǎng)絡(luò)的簡單介紹如下。

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

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

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

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

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

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

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

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

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

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

4.2 評價指標

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

Etr∪Ets=E

(24)

Etr∩Ets=?

(25)

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

(26)

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

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

(27)

5 實驗結(jié)果及分析

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

5.1 與其他相似性指標對比

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

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

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

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

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

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

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

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

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

5.2 IMP_DS性能提升原因分析

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

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

6 結(jié)語

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