劉苗苗， 扈慶翠， 郭景峰， 陳 晶

(1.東北石油大學(xué)計算機與信息技術(shù)學(xué)院， 大慶 163318； 2. 燕山大學(xué)信息科學(xué)與工程學(xué)院， 秦皇島 066004；3.黑龍江省石油大數(shù)據(jù)與智能分析重點實驗室， 大慶 163318)

1 引 言

隨著人工智能和機器學(xué)習(xí)技術(shù)的快速發(fā)展，涌現(xiàn)了許多社會媒體網(wǎng)絡(luò)平臺，隨之也產(chǎn)生了大量復(fù)雜多樣的網(wǎng)絡(luò)大數(shù)據(jù)，對這些數(shù)據(jù)的表征和預(yù)測逐漸成為社會網(wǎng)絡(luò)分析領(lǐng)域的研究熱點.在現(xiàn)實網(wǎng)絡(luò)中，實體間通常具有正負兩方面的關(guān)系.例如，社會領(lǐng)域的人與人之間存在朋友和敵人關(guān)系，信息領(lǐng)域的用戶間在觀點上存在支持和反對關(guān)系，生物領(lǐng)域的細胞之間存在促進和抑制關(guān)系.這種同時具有正負關(guān)系的網(wǎng)絡(luò)稱為符號社會網(wǎng)絡(luò)，簡稱符號網(wǎng)絡(luò)[1].它與傳統(tǒng)無符號網(wǎng)絡(luò)的區(qū)別在于節(jié)點間是否存在鏈接的正負符號屬性.符號網(wǎng)絡(luò)是一種包含正負對立關(guān)系的二維網(wǎng)絡(luò)，這種對立關(guān)系包括朋友、支持、喜歡等積極關(guān)系和敵人、反對、厭惡等消極關(guān)系.

符號網(wǎng)絡(luò)是社會網(wǎng)絡(luò)的重要分支，因其更貼近現(xiàn)實世界的特性，從而受到學(xué)術(shù)界的廣泛關(guān)注.有關(guān)符號網(wǎng)絡(luò)的研究主要集中在其結(jié)構(gòu)分析，其中一個研究熱點便是鏈路預(yù)測[2].它通過對觀察到的網(wǎng)絡(luò)結(jié)構(gòu)進行分析來預(yù)測未知的鏈接，包括對未知鏈接建立的可能性預(yù)測、未知鏈接的符號預(yù)測以及對已觀測到的鏈接缺失的符號類型的預(yù)測[3].符號網(wǎng)絡(luò)鏈路預(yù)測在社會與信息領(lǐng)域的推薦系統(tǒng)以及知識圖譜中實體間關(guān)系的學(xué)習(xí)中有著廣泛的應(yīng)用，在生物領(lǐng)域蛋白質(zhì)相互作用關(guān)系的發(fā)現(xiàn)方面更是有著實際的意義和價值，可幫助指導(dǎo)實驗過程，在節(jié)省時間和成本的同時提高預(yù)測準(zhǔn)確率.

目前，針對符號網(wǎng)絡(luò)的鏈路預(yù)測研究主要有基于節(jié)點相似性、基于概率統(tǒng)計的矩陣分解或填充以及基于機器學(xué)習(xí)等方法.第一類方法主要結(jié)合結(jié)構(gòu)平衡理論，利用符號網(wǎng)絡(luò)的局部或全局信息如節(jié)點的度、共同鄰居數(shù)量、路徑特征等設(shè)計相似性指標(biāo)，代表性研究成果有：文獻[4]提出基于結(jié)構(gòu)平衡理論與網(wǎng)絡(luò)局部特征的符號預(yù)測算法.文獻[5]利用路徑上傳輸節(jié)點相似度以及拉普拉斯聚類算法實現(xiàn)了符號網(wǎng)絡(luò)的鏈路預(yù)測及推薦.文獻[6]在基于節(jié)點共同鄰居的符號預(yù)測算法CN-Predict的基礎(chǔ)上，融合符號密度提出改進后的ICN-Predict算法，能夠較好地實現(xiàn)符號預(yù)測，但該方法針對負鏈接的預(yù)測效果欠佳.文獻[7]提取結(jié)構(gòu)平衡環(huán)的局部特征以及頻繁子圖出現(xiàn)的次數(shù)構(gòu)建特征來進行符號預(yù)測，但時間復(fù)雜度較高.文獻[8]結(jié)合局部路徑指標(biāo)以及結(jié)構(gòu)平衡理論對符號網(wǎng)絡(luò)鏈路預(yù)測方法進行了研究.文獻[9]提出一種符合結(jié)構(gòu)平衡理論的高度對稱四邊形結(jié)構(gòu)，基于局部結(jié)構(gòu)的統(tǒng)計特性提取節(jié)點對的相似性、相異性以及反映節(jié)點對正負態(tài)度傾向的構(gòu)造特征，在此基礎(chǔ)上完成了符號預(yù)測.文獻[10]融合結(jié)構(gòu)平衡理論與節(jié)點的局部和路徑結(jié)構(gòu)相似性提出了一種符號網(wǎng)絡(luò)邊值預(yù)測算法PSNBS.文獻[11]以結(jié)構(gòu)平衡理論為基礎(chǔ)，將Katz指標(biāo)與網(wǎng)絡(luò)拓撲相融合，提出一種符號預(yù)測算法.文獻[12]考慮到負鏈接在符號網(wǎng)絡(luò)中的重要性，融合結(jié)構(gòu)平衡理論和地位理論提出基于隱空間映射矩陣的符號網(wǎng)絡(luò)鏈接預(yù)測算法，在Epinions和Slashdot數(shù)據(jù)集上獲得了較好的效果.針對符號網(wǎng)絡(luò)拓撲結(jié)構(gòu)中的非確定性因素，文獻[13]利用集對理論，融合網(wǎng)絡(luò)中的確定和不確定關(guān)系以及局部和全局信息實現(xiàn)了符號預(yù)測.總體而言，基于節(jié)點相似性的鏈路預(yù)測算法簡單快捷，且通常能達到較高的預(yù)測準(zhǔn)確率，但針對稀疏網(wǎng)絡(luò)及負鏈接的預(yù)測效果往往欠佳.第二類算法主要通過將符號網(wǎng)絡(luò)轉(zhuǎn)化為矩陣，利用信任傳播模型、矩陣分解或填充來完成符號預(yù)測，代表性研究成果有：文獻[14]首次提出將符號預(yù)測問題轉(zhuǎn)化為低秩矩陣分解和填充問題，先將n×n矩陣分解為n×k和k×n矩陣的乘積，再通過逐點誤差來測量結(jié)果矩陣和原矩陣間的誤差，最終達到了較好的符號預(yù)測效果.文獻[15]在矩陣分解損失函數(shù)中運用了成對經(jīng)驗誤差并引入了拉格朗日乘子，通過隨機梯度下降算法求解符號預(yù)測結(jié)果.文獻[16]提出帶偏置的低秩矩陣分解模型，將鄰居節(jié)點的出邊和入邊符號作為偏置信息引入模型，提高了符號預(yù)測精度.文獻[17]提出一種基于投影非負矩陣分解的框架，通過嵌入網(wǎng)絡(luò)結(jié)構(gòu)和用戶屬性的無監(jiān)督學(xué)習(xí)實現(xiàn)了負鏈接預(yù)測.針對大型符號網(wǎng)絡(luò)的鏈路預(yù)測，文獻[18]提出基于異步的分布式隨機梯度下降算法的矩陣分解模型，在大大降低參數(shù)空間大小的同時提高了計算效率.總體而言，基于矩陣處理的符號預(yù)測方法計算復(fù)雜度較高，且模型評價難度大，因此限制了此類方法在大型網(wǎng)絡(luò)中的實際應(yīng)用.近幾年，相關(guān)學(xué)者利用深度學(xué)習(xí)機制對基于卷積神經(jīng)網(wǎng)絡(luò)、循環(huán)神經(jīng)網(wǎng)絡(luò)等的鏈接表示與預(yù)測方法也進行了研究[19]，利用節(jié)點間的局部拓撲結(jié)構(gòu)構(gòu)建有序節(jié)點序列，并使用節(jié)點向量表達生成潛在鏈接的矩陣表示[20]，最后基于神經(jīng)網(wǎng)絡(luò)運算提取節(jié)點序列中節(jié)點對的多層隱含關(guān)系，實現(xiàn)鏈路預(yù)測[21].但此類算法大多關(guān)注的是傳統(tǒng)社會網(wǎng)絡(luò)中鏈接建立的可能性研究，針對符號網(wǎng)絡(luò)中的鏈接與符號預(yù)測的研究相對較少.

綜上所述，針對符號網(wǎng)絡(luò)中的鏈接預(yù)測與符號預(yù)測雙重目標(biāo)，如何有效挖掘網(wǎng)絡(luò)圖的局部與全局特征，在保證算法效率的前提下提高預(yù)測的正確性，尤其是負鏈接以及拓撲結(jié)構(gòu)特殊的符號網(wǎng)絡(luò)的預(yù)測，是一個值得思考的問題.基于此，本文在考慮連接兩節(jié)點的路徑(包括路徑長度及數(shù)量)、路徑上的中間節(jié)點(包括一階和二階鄰居節(jié)點的數(shù)量、度數(shù))以及連邊符號等信息的基礎(chǔ)上，綜合引入共同鄰居節(jié)點的聚集系數(shù)以及基于結(jié)構(gòu)平衡環(huán)的符號影響力的概念定義兩節(jié)點的相似性.該方法能更全面地捕獲符號網(wǎng)絡(luò)的拓撲結(jié)構(gòu)特征對于兩節(jié)點間的鏈接建立的可能性以及符號類型的影響程度，既能保證算法執(zhí)行效率，又能提高預(yù)測的準(zhǔn)確性.本文在多個經(jīng)典符號網(wǎng)絡(luò)數(shù)據(jù)集上對所提方法進行了驗證，實驗結(jié)果也表明了該方法對于常規(guī)和稀疏的大型符號網(wǎng)絡(luò)，以及拓撲結(jié)構(gòu)特殊的小型網(wǎng)絡(luò)的鏈接預(yù)測以及符號預(yù)測的有效性和更高的預(yù)測準(zhǔn)確性.

2 預(yù)備知識

根據(jù)節(jié)點間的鏈接是否帶方向，可將符號網(wǎng)絡(luò)分為有向和無向符號網(wǎng)絡(luò)，本文關(guān)注無向符號網(wǎng)絡(luò)中的鏈路預(yù)測研究.一個無向符號網(wǎng)絡(luò)通常被形式化表示為G=(V，E，S)，其中，V={v1，v2，…，vn}表示節(jié)點集，E={e(i，j)|vi，vj∈V，i≠j}表示邊集，S={sign(i，j)|vi，vj∈V，i≠j}表示符號集合，取值如下.

2.1 結(jié)構(gòu)平衡理論

Heider[22]源于社會心理學(xué)提出的用戶間結(jié)構(gòu)關(guān)系的平衡模型為無向符號網(wǎng)絡(luò)的結(jié)構(gòu)分析提供了理論基礎(chǔ)，它最初是針對三角形的平衡性分析開始，如圖1所示.根據(jù)該理論，若無向符號網(wǎng)絡(luò)中一個閉合環(huán)上所有邊的符號之積為正，則該環(huán)為結(jié)構(gòu)平衡環(huán)，否則為非平衡環(huán).眾多研究者在社會媒體網(wǎng)站中的實證研究表明，真實網(wǎng)絡(luò)中平衡的三元環(huán)數(shù)目遠大于不平衡的三元環(huán)數(shù)目，且隨時間推移平衡三元環(huán)所占的比例日益增加[23]，像Epinions和Slashdot這類大型符號網(wǎng)絡(luò)的平衡指數(shù)分別達到了89.6%和86.2%[24].2010年，Leskovec等[4]首次將結(jié)構(gòu)平衡理論應(yīng)用于符號預(yù)測問題.目前，該理論的一些基本規(guī)律已被廣泛應(yīng)用于符號網(wǎng)絡(luò)鏈路預(yù)測算法研究[25].針對符號網(wǎng)絡(luò)的預(yù)測研究，一方面要分析未知鏈接或缺失符號的已有鏈接的符號屬性，即符號預(yù)測.通常依據(jù)結(jié)構(gòu)平衡理論，力圖使兩個目標(biāo)節(jié)點所在的環(huán)能最大限度地增強網(wǎng)絡(luò)的結(jié)構(gòu)平衡性.

圖1 結(jié)構(gòu)平衡理論示意圖Fig.1 Sketch of structural balance theory

2.2 經(jīng)典的相似性指標(biāo)

針對符號網(wǎng)絡(luò)的預(yù)測研究，除了完成符號預(yù)測之外，還要分析兩個尚未相連的節(jié)點間存在或建立鏈接的可能性，即鏈接預(yù)測.通常認為兩節(jié)點間相似性越高，兩者存在或建立鏈接的可能性越大.總體而言，經(jīng)典的相似性指標(biāo)有CN、Jaccard、AA、LP、Katz等，如下式所示.

(1)

(2)

(3)

(4)

β2(A2)xy+β3(A3)xy+…

(5)

2.3 預(yù)測準(zhǔn)確度評價方法

衡量鏈路預(yù)測算法準(zhǔn)確性的基本方法是，給網(wǎng)絡(luò)圖對應(yīng)的全集U中所有沒有連邊的節(jié)點對按其建立鏈接的可能性賦予一個分?jǐn)?shù)值Sxy，然后根據(jù)實際網(wǎng)絡(luò)的演化情況觀察哪些節(jié)點對之間出現(xiàn)了新的連邊，并與預(yù)測結(jié)果進行比較以判斷預(yù)測的準(zhǔn)確性.然而，社會網(wǎng)絡(luò)的動態(tài)性使得實驗中無法預(yù)知或觀察到連邊何時會出現(xiàn)，故而無法將預(yù)測結(jié)果與網(wǎng)絡(luò)真實演化結(jié)果進行比較.因此，許多鏈路預(yù)測研究均以網(wǎng)絡(luò)在某個時刻的瞬時快照為研究對象.針對傳統(tǒng)無符號網(wǎng)絡(luò)的靜態(tài)快照的鏈路預(yù)測方法，常用的預(yù)測準(zhǔn)確度的評價指標(biāo)有AUC和Precision[26].實驗中，為衡量算法預(yù)測結(jié)果的準(zhǔn)確性，需將已知的邊集E劃分為訓(xùn)練集Etr和測試集Ete.通常采用K折交叉驗證法[27]進行劃分，每次取其中一個子集作為Etr，其余K-1個子集形成Ete.大量實驗表明，十折交叉驗證在計算量和性能間達到了最好的折中[28]即，針對每個數(shù)據(jù)集獨立進行10次劃分，保證每次劃分中Etr∪Ete=E且Etr∩Ete=Φ且|Etr|=9|Ete|.

2.3.1 鏈接預(yù)測準(zhǔn)確率評價指標(biāo)AUC′ 針對符號網(wǎng)絡(luò)中的鏈接預(yù)測，本文所提算法計算所得兩節(jié)點間總相似度有正有負，其絕對值代表了兩節(jié)點存在或建立鏈接的概率，其正負代表了被預(yù)測鏈接的符號類型.故而，本文對AUC[26]進行調(diào)整得到新的指標(biāo)AUC′，如式(6)所示.

(6)

2.3.2 符號預(yù)測準(zhǔn)確率評價指標(biāo)Precision′ 針對符號網(wǎng)絡(luò)中的符號預(yù)測，每次隨機從測試集中取一條邊作為待測邊，假定其不存在，之后基于算法計算得到待測邊的符號預(yù)測結(jié)果，并與真實的符號類型進行比較，以此評價符號預(yù)測準(zhǔn)確性，相應(yīng)的指標(biāo)有TP、FP、TN、FN、TPR(又稱Recall)、TNR(又稱specificity)、Precision、Accuracy、F1-score等[29].符號網(wǎng)絡(luò)的符號預(yù)測需評價正負符號預(yù)測準(zhǔn)確性的綜合指數(shù)，相關(guān)研究顯示[12，17，30]，絕大多數(shù)真實符號網(wǎng)絡(luò)中正鏈接數(shù)與負鏈接數(shù)的比值超過4∶1，也即實驗中選取的待測邊是正鏈接的概率遠高于負鏈接.故而，本文實驗中融合上述指標(biāo)進行調(diào)整，為正鏈接的符號預(yù)測結(jié)果賦予權(quán)重1，為負鏈接的符號預(yù)測結(jié)果賦予權(quán)重0.5，得到調(diào)整后的指標(biāo)Precision′，用于綜合評價符號預(yù)測準(zhǔn)確性，其定義如式(7)所示.

(7)

3 融合聚集系數(shù)與符號影響力的鏈路預(yù)測方法

在考慮符號網(wǎng)絡(luò)的局部拓撲信息時，CN、RA、AA指標(biāo)沒有考慮到待測節(jié)點對的共同鄰居節(jié)點的聚集系數(shù)對于兩者的相似性影響.如圖2，對于節(jié)點對而言，圖2(a)和(b)中節(jié)點X與Y的度數(shù)、兩者的共同鄰居數(shù)目以及共同鄰居的度數(shù)都相同，且共同鄰居節(jié)點B的聚集系數(shù)也相同，但共同鄰居節(jié)點A的聚集系數(shù)不同.顯然，圖2(b)中共同鄰居節(jié)點A對于節(jié)點對的相似性貢獻更大.針對該情況，綜合引入共同鄰居聚集系數(shù)CNCC(Common Neighbor Clustering Coefficient)全面衡量兩節(jié)點的共同鄰居的屬性特征對于兩者的相似性貢獻.此外，對真實符號網(wǎng)絡(luò)拓撲特征的相關(guān)研究顯示，符號網(wǎng)絡(luò)中正負鏈接的分布不均衡，且負鏈接具有更重要的作用.因此，在進行符號預(yù)測時，連接兩節(jié)點的路徑上正鏈接數(shù)目也遠超過負鏈接數(shù)目，也即由于正負鏈接數(shù)目比例的不同，正負符號在結(jié)構(gòu)平衡環(huán)中對于目標(biāo)節(jié)點對的符號影響也不同.為此，引入符號影響力SI(Sign Influence)的概念，對多步長路徑上的符號類型賦予不同的權(quán)重，以更精確地衡量多條路徑對于兩節(jié)點間所建鏈接的符號類型的影響程度.

(a) (b)

基于以上思考，我們提出CNCC_SI算法.在考慮基于局部路徑信息的三元環(huán)對節(jié)點的相似性影響時，引入共同鄰居聚集系數(shù)，綜合考慮兩節(jié)點的度、共同鄰居數(shù)目、共同鄰居的度及聚集系數(shù)的貢獻；在考慮基于全局路徑信息的平衡環(huán)對節(jié)點的相似性影響時，引入符號影響力，綜合考慮連接兩節(jié)點的路徑上中間傳輸節(jié)點的度數(shù)以及過渡鏈接的符號類型的貢獻；考慮到高階步長的路徑信息計算復(fù)雜度較高，根據(jù)文獻[31]和文獻[32]的研究結(jié)果，本文研究中利用了連接兩節(jié)點的步長為2和3的路徑信息分別定義了節(jié)點對的二階相似性和三階相似性，以達到預(yù)測準(zhǔn)確性和計算效率上較好的均衡.

3.1 相關(guān)定義

為描述方便，對變量及符號表示如表1.

表1 CNCC_SI算法相關(guān)變量定義及符號說明

定義1共同鄰居的聚集系數(shù).

(8)

為提高預(yù)測準(zhǔn)確率，CNCC_SI算法綜合考慮兩節(jié)點的度數(shù)、一階共同鄰居的度數(shù)和聚集系數(shù)、連邊符號等局部結(jié)構(gòu)特征對于兩者的相似性影響.設(shè)G=，?vx，vy∈V且sign(x，y)=0，基于結(jié)構(gòu)平衡理論，定義節(jié)點對基于一階共同鄰居節(jié)點的相似性得分，記作SCN1，如式(9)所示.

定義2兩節(jié)點基于一階共同鄰居的相似性得分.

(9)

(10)

式(10)中，l=vxe(vx，vp)vpe(vp，vq)vy為連接vx與vy的長度為3的路徑；vp和vq為路徑l上的兩個中間節(jié)點，即vp∈N1(x)∩N2(y)，vq∈N1(y)∩N2(x)；α代表路徑l上正鏈接的權(quán)重，設(shè)為1；β代表路徑l上負鏈接的權(quán)重，設(shè)為0.5.

定義3路徑l基于平衡環(huán)的符號影響力.

基于上述定義，利用連接兩節(jié)點的步長為3的路徑信息定義兩節(jié)點基于二階共同鄰居的相似性得分，記作SCN2，如式(11)所示.

定義4兩節(jié)點基于二階共同鄰居的相似性得分.

(11)

將不相連的兩節(jié)點間的總相似度定義為兩節(jié)點基于一階共同鄰居和二階共同鄰居的相似性得分之和，記作SCN(x，y)，如式(12)所示.|SCN(x，y)|代表節(jié)點vx與vy建立鏈接的可能性大小，鏈接的符號類型與SCN(x，y)的符號類型相同.

定義5節(jié)點對總相似性得分.

SCN1(x,y)+SCN2(x,y)

(12)

3.2 算法實現(xiàn)

Algorithm： CNCC_SI

Input：G=(V，E，S)

Output： SCN(x，y) and sign(x，y)

Begin

1) Read Dataset File

2) For eachvx，vy∈Vdo

3) IFe(x，y)=0 ore(x，y)=1∧sign(x，y)=0

4) {Find all paths where |l|=2， Calculate SCN1(x，y)

5) Find all paths where |l|=3， Calculate SCN2(x，y)

6) Calculate SCN(x，y)}

7) If {SCN(x，y)>0 then sign(x，y)=+1

8) Else sign(x，y)=-1}

9) Output sign(x，y)

10) Sort |SCN(x，y)| and get Topk

End

4 實驗與分析

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

采用符號網(wǎng)絡(luò)研究中常用的3個經(jīng)典大規(guī)模真實數(shù)據(jù)集Epinions、Slashdot和Wikipedia，以及3個小型數(shù)據(jù)集進行實驗，基本信息見表2.所選3個小型數(shù)據(jù)集拓撲結(jié)構(gòu)(正負鏈接數(shù)的比例、節(jié)點的度分布特征等)都較為特殊，其中CRA和FEC是仿真數(shù)據(jù)集，Gahuku Gama Subtribes(記作GGS)是真實的符號網(wǎng)絡(luò)數(shù)據(jù)集.

表2 數(shù)據(jù)集基本特征

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

針對符號網(wǎng)絡(luò)中的符號預(yù)測，文獻[6]中所述CN-Predict和改進后的ICN-Predict是經(jīng)典的符號預(yù)測算法.針對符號網(wǎng)絡(luò)中的邊值預(yù)測(包括鏈接預(yù)測與符號預(yù)測)，PSNBS算法[10]是較為經(jīng)典的算法.為衡量本文所提算法對符號網(wǎng)絡(luò)鏈路預(yù)測的準(zhǔn)確性，采用十折交叉法劃分實驗數(shù)據(jù)集，并以前文所述AUC’、Precision’等為評價指標(biāo)，與上述3個經(jīng)典算法分別進行了鏈接預(yù)測與符號預(yù)測準(zhǔn)確性的實驗對比.

4.2.1 基于AUC′的鏈接預(yù)測準(zhǔn)確率實驗結(jié)果 以AUC′為評價標(biāo)準(zhǔn)，將所提算法與PSNBS算法進行了鏈接預(yù)測準(zhǔn)確性的對比分析，結(jié)果如圖3所示，圖中顯示的是10次獨立實驗的平均值.且針對前5個數(shù)據(jù)集，圖中顯示的PSNBS實驗結(jié)果為該算法中步長影響因子λ分別取0.6、0.9、0.8、0.9和0.8時所得到的算法的最高預(yù)測準(zhǔn)確率.

圖3 基于AUC′指標(biāo)的鏈接預(yù)測實驗結(jié)果Fig.3 Link prediction results based on AUC′

從圖3可清晰看出，本文所提算法在3個大型經(jīng)典符號網(wǎng)絡(luò)以及小型仿真網(wǎng)絡(luò)CRA中均得到了較好的預(yù)測效果，鏈接預(yù)測準(zhǔn)確率均高于PSNBS算法.尤其針對正負鏈接數(shù)目分布不均衡的小型網(wǎng)絡(luò)CRA(接近14∶1)，所提算法鏈接預(yù)測準(zhǔn)確率較PSNBS有較大幅度提升.

對于GGS網(wǎng)絡(luò)，算法預(yù)測準(zhǔn)確率相比前四個數(shù)據(jù)集相對較低.該網(wǎng)絡(luò)描述了新幾內(nèi)亞高地16個子部落(節(jié)點)之間真實的政治聯(lián)盟和對立關(guān)系，其拓撲結(jié)構(gòu)較為特殊，如圖4所示.16個子部落根據(jù)同盟與敵對關(guān)系形成了3個小的社區(qū)(團體)，同一社區(qū)內(nèi)節(jié)點間都為正向的同盟關(guān)系，不同社區(qū)的節(jié)點間均為負向的對立關(guān)系，16個節(jié)點的度數(shù)以及聚集系數(shù)的分布情況分別如圖5和圖6所示，58條邊中正負鏈接比例為1∶1.針對正負鏈接數(shù)量完全相同的小型數(shù)據(jù)集，CNCC_SI算法鏈接預(yù)測準(zhǔn)確率仍可達到71%，具有較強的健壯性.

圖4 GGS網(wǎng)絡(luò)拓撲結(jié)構(gòu)示意圖Fig.4 Topology of GGS network

圖5 GGS網(wǎng)絡(luò)節(jié)點度數(shù)分布示意圖Fig.5 Degree distribution of GGS network

圖6 GGS網(wǎng)絡(luò)節(jié)點聚集系數(shù)分布示意圖Fig.6 Clustering coefficient distribution of GGS

圖7 FEC網(wǎng)絡(luò)拓撲結(jié)構(gòu)示意圖Fig.7 Topology of FEC network

圖8 FEC網(wǎng)絡(luò)節(jié)點度數(shù)分布示意圖Fig.8 Degree distribution of FEC network

4.2.2 基于Precision′的符號預(yù)測準(zhǔn)確率實驗結(jié)果 以Recall、Precison、F1-score、Accuracy等為評價指標(biāo)，對CNCC_SI算法的符號預(yù)測準(zhǔn)確性進行了驗證，結(jié)果見表3所示.從表3可以看出，所提算法無論對于具有常規(guī)拓撲結(jié)構(gòu)分布的大型真實符號網(wǎng)絡(luò)，還是拓撲結(jié)構(gòu)特殊的小型仿真及真實數(shù)據(jù)集，均達到了較好的符號預(yù)測性能，且針對負鏈接的預(yù)測準(zhǔn)確率較高，具有良好的穩(wěn)健性.

表3 CNCC_SI算法符號預(yù)測準(zhǔn)確性實驗結(jié)果

與此同時，以Precision′為評價標(biāo)準(zhǔn)，將所提算法與PSNBS算法進行了符號預(yù)測準(zhǔn)確性的對比實驗，結(jié)果如圖9所示，圖中顯示的依然是10次獨立實驗的平均值.從圖中可以看出，CNCC_SI算法在6個數(shù)據(jù)集上的符號預(yù)測準(zhǔn)確性均高于PSNBS算法，總體獲得了較好的符號預(yù)測性能.尤其針對3個拓撲結(jié)構(gòu)特殊的小型符號網(wǎng)絡(luò)，所提算法符號預(yù)測準(zhǔn)確性均有較大幅度提升，進一步顯示了CNCC_SI算法融合共同鄰居聚集系數(shù)和符號影響力進行符號預(yù)測的正確性和有效性.

圖9 基于Precision′的符號預(yù)測準(zhǔn)確性實驗結(jié)果Fig.9 Sign prediction results based on Precision′

4.2.3 可調(diào)步長參數(shù)敏感性分析 為達到預(yù)測準(zhǔn)確性與計算復(fù)雜度上較好的均衡，本文算法將兩節(jié)點基于一階共同鄰居的二步相似性得分和基于二階共同鄰居的三步相似性得分之和作為兩節(jié)點的總相似度.然而，相關(guān)研究也已表明，相對于低階路徑而言，高階路徑對節(jié)點的相似性貢獻相對較低，且針對不同拓撲結(jié)構(gòu)的數(shù)據(jù)集，網(wǎng)絡(luò)的平均最短路徑也不盡相同.為此，許多基于路徑結(jié)構(gòu)信息的相似性計算方法為不同步長的路徑賦予了可調(diào)步長參數(shù)，以區(qū)分高階路徑與低階路徑的相似性貢獻程度.本文實驗中，為連接兩節(jié)點的步長為2和3的路徑分別賦予了可調(diào)步長參數(shù)ε(0.5≤ε≤1)和1-ε，并進行了預(yù)測準(zhǔn)確率的分析，將式(12)中兩節(jié)點的總相似性得分修改為式(13)所示，記作SCN(x,y)ε，修改后的算法記作CNCC_SIε.

定義6融合步長影響因子的相似性得分.

SCN(x,y)ε=ε×SCN1(x,y)+

(1-ε)×SCN2(x,y)

(13)

基于式(13)，在相同的條件下進行了實驗，可調(diào)步長參數(shù)ε分別取0.5、0.6、0.7、0.8、0.9和1，所提算法基于AUC′和Precision′評價指標(biāo)的實驗結(jié)果分別如圖10和圖11所示.

圖10 CNCC_SIε算法基于AUC′的鏈接預(yù)測準(zhǔn)確率Fig.10 Link prediction results of CNCC_SIε based on AUC′

圖11 CNCC_SIε算法基于Precision′的符號預(yù)測準(zhǔn)確率Fig.11 Sign prediction results of CNCC_SIεbased on Precision′

從圖10和圖11可知，對于同一個網(wǎng)絡(luò)，所提算法鏈接預(yù)測和符號預(yù)測準(zhǔn)確率隨ε的變化趨勢是一致的.針對Epinions、Slashdot、Wikipedia、CRA和GGS網(wǎng)絡(luò)，鏈接預(yù)測準(zhǔn)確率和符號預(yù)測準(zhǔn)確率都是在ε分別取0.6、0.9、0.8、0.9和0.8時達到了最高值，又一次驗證了所提算法的正確性.

4.2.4 與其他算法預(yù)測準(zhǔn)確率對比

(1) 基于AUC的符號預(yù)測準(zhǔn)確率對比.為進一步驗證本文所提算法的正確性和有效性，以文獻[6]中的AUC為符號網(wǎng)絡(luò)鏈路預(yù)測準(zhǔn)確性的評價指標(biāo)，將CN-Predict、ICN-Predict、PSNBS(λ)、CNCC_SI、CNCC_SIε算法進行了預(yù)測結(jié)果的對比，見圖12.在此說明，文獻[6]中AUC評價指標(biāo)定義見式(14)所示，其中n代表被預(yù)測的鏈接對數(shù)，取值為10 000；n′代表符號預(yù)測結(jié)果中正鏈接預(yù)測正確的數(shù)量，權(quán)重為1；n″代表符號預(yù)測結(jié)果中負鏈接預(yù)測正確的數(shù)量，權(quán)重為0.5.

圖12 基于AUC[6]指標(biāo)的符號網(wǎng)絡(luò)鏈路預(yù)測準(zhǔn)確率對比Fig.12 Link prediction results comparison based on AUC[6]

(14)

實驗結(jié)果顯示，針對6個符號網(wǎng)絡(luò)數(shù)據(jù)集，基于可調(diào)步長參數(shù)敏感性分析的CNCC_SIε算法預(yù)測準(zhǔn)確率均高于其他算法，表明基于共同鄰居聚類系數(shù)和符號影響力的相似性計算方法能有效解決其他算法(基于共同鄰居的度、節(jié)點符號密度等)對某些拓撲結(jié)構(gòu)特殊的網(wǎng)絡(luò)存在的預(yù)測準(zhǔn)確率較低的問題，具有更好的穩(wěn)健性.

(2) 基于Accuracy的符號預(yù)測準(zhǔn)確率對比.同樣地，我們以Accuracy[29]作為符號預(yù)測準(zhǔn)確率的評價指標(biāo)，在3個大型數(shù)據(jù)集上進行了實驗，將所提算法與已有的經(jīng)典的符號預(yù)測算法進行了對比.例如，文獻[33]所提基于譜分析的不平衡度量的符號預(yù)測方法MOI、文獻[34]所提符號網(wǎng)絡(luò)中基于高階環(huán)監(jiān)督學(xué)習(xí)的鏈路預(yù)測算法HOC、文獻[35]所提將聚類之間的相對相似性定義應(yīng)用于協(xié)同過濾算法的符號預(yù)測方法CF，文獻[36]所提基于譜分析聚類的矩陣分解方法MF，以及文獻[37]所述基于封閉三角結(jié)構(gòu)的符號預(yù)測算法CTMS.以上7個算法在3個大型數(shù)據(jù)集上的實驗結(jié)果如圖13所示.

圖13 基于Accuracy[29]的符號網(wǎng)絡(luò)鏈路預(yù)測準(zhǔn)確率對比Fig.13 Link prediction results comparison based on Accuracy[29]

從圖13可知，MOI算法雖度量了符號網(wǎng)絡(luò)中長度小于等于10的環(huán)的不平衡程度，但其符號預(yù)測準(zhǔn)確率依然低于其他方法.CF算法較低的符號預(yù)測準(zhǔn)確率也說明，進行符號預(yù)測時除考慮網(wǎng)絡(luò)的結(jié)構(gòu)平衡性以外，節(jié)點的局部和全局結(jié)構(gòu)特征對符號預(yù)測結(jié)果的影響更大.HOC算法不僅學(xué)習(xí)了三元環(huán)的結(jié)構(gòu)特征，同時還融入了四元環(huán)和五元環(huán)的結(jié)構(gòu)特征，但符號預(yù)測效果總體上依然差于本文所提僅使用三元環(huán)和四元環(huán)的結(jié)構(gòu)特征的CNCC_SI算法.上述實驗結(jié)果再次顯示，影響符號網(wǎng)絡(luò)中連邊符號的主要因素為邊的兩個端點的屬性特征，其次是連邊所處的局部結(jié)構(gòu)特征和全局結(jié)構(gòu)特征.此外，本文所提算法雖然在Epinions和Slashdot兩個數(shù)據(jù)集上Accuracy指標(biāo)(分別為93.2%和84.3%)略低于文獻[9]所述SPR模型(分別為94.7%和93.8%)，但在Wikipedia數(shù)據(jù)集上預(yù)測正確率(92.9%)明顯優(yōu)于SPR算法(86.6%).且Accuracy指標(biāo)并沒有區(qū)分預(yù)測正確的樣本是正例還是負例，因此針對拓撲結(jié)構(gòu)特殊的數(shù)據(jù)集，相關(guān)算法預(yù)測效果欠佳.而本文所提算法能同時實現(xiàn)鏈接預(yù)測與符號預(yù)測雙重目標(biāo)，且關(guān)注了符號網(wǎng)絡(luò)中正負鏈接的比例問題，針對各種拓撲結(jié)構(gòu)的符號網(wǎng)絡(luò)，總體而言均具有較好的預(yù)測性能.

4.3 算法復(fù)雜度分析

CNCC_SI算法使用鄰接表儲存圖邊關(guān)系，針對無向符號網(wǎng)絡(luò)圖G=(V，E，S)，節(jié)點數(shù)和邊數(shù)分別為n和m，算法空間復(fù)雜度是O(m+n).算法在計算網(wǎng)絡(luò)圖中任意兩節(jié)點基于一階共同鄰居的二步相似性得分時，計算復(fù)雜度為O(m2n)；算法在計算任意兩節(jié)點基于二階共同鄰居的三步相似性得分時，時間復(fù)雜度為O(mn2).因而，算法總的時間復(fù)雜度為O(m2n).與其它幾種算法相比，所提算法計算復(fù)雜度略微提高.例如，文獻[9]所述SPR模型需遍歷網(wǎng)絡(luò)中的所有邊，獲取任意節(jié)點對相應(yīng)的鄰居節(jié)點并計算節(jié)點對的相似性-相異性，進行符號預(yù)測，算法的計算復(fù)雜度為O(m2)，其中，m為網(wǎng)絡(luò)中的邊數(shù)，為網(wǎng)絡(luò)中節(jié)點的平均度數(shù).針對大規(guī)模符號網(wǎng)絡(luò)，本文所提算法計算復(fù)雜度雖略微增加，但在達到較高預(yù)測準(zhǔn)確率的前提下，仍可保證時間上的可行性和有效性.

5 結(jié) 論

提出CNCC_SI算法，結(jié)合共同鄰居節(jié)點聚類系數(shù)和符號影響力分別定義了兩節(jié)點基于一階共同鄰居的二步相似性和基于二階共同鄰居的三步相似性，并通過可調(diào)步長影響因子的敏感性分析對算法做進一步改進，在多個數(shù)據(jù)集上的實驗結(jié)果驗證了所提算法對于符號網(wǎng)絡(luò)鏈接預(yù)測和符號預(yù)測的正確性、較高的預(yù)測準(zhǔn)確率和良好的穩(wěn)健性.然而，針對具有復(fù)雜結(jié)構(gòu)的符號網(wǎng)絡(luò)(例如含時網(wǎng)絡(luò)、多層網(wǎng)絡(luò)、超網(wǎng)絡(luò)等)中的鏈路預(yù)測，仍存在較多挑戰(zhàn).針對超大規(guī)模符號網(wǎng)絡(luò)的動態(tài)性、網(wǎng)絡(luò)中節(jié)點及其鏈接關(guān)系的不確定性等，如何有效利用多維的豐富信息進行快速、準(zhǔn)確的鏈路預(yù)測，設(shè)計局域化或并行化算法等，都將是下一步的研究內(nèi)容.