符號(hào)網(wǎng)絡(luò)中融合聚集系數(shù)與符號(hào)影響力的鏈路預(yù)測(cè)算法

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

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

1 引 言

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

(3)

(4)

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

(5)

2.3 預(yù)測(cè)準(zhǔn)確度評(píng)價(jià)方法

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

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

(6)

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

(7)

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

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

(a) (b)

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

3.1 相關(guān)定義

為描述方便，對(duì)變量及符號(hào)表示如表1.

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

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

(8)

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

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

(9)

(10)

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

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

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

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

(11)

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

定義5節(jié)點(diǎn)對(duì)總相似性得分.

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

(12)

3.2 算法實(shí)現(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 實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

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

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

圖4 GGS網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)示意圖Fig.4 Topology of GGS network

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

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

圖7 FEC網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)示意圖Fig.7 Topology of FEC network

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

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

表3 CNCC_SI算法符號(hào)預(yù)測(cè)準(zhǔn)確性實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

(13)

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

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

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

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

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

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

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

(14)

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

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

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

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

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

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

5 結(jié) 論

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