基于K-shell分解與鄰居節(jié)點(diǎn)度去噪的鏈路預(yù)測(cè)方法
2022-12-31 00:00:00張希康李澤滔
計(jì)算機(jī)應(yīng)用研究 2022年11期
摘 要：鏈路預(yù)測(cè)是研究復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)和演化機(jī)制的重要工具，提高鏈路預(yù)測(cè)的精度具有重要價(jià)值。針對(duì)傳統(tǒng)的基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相似性算法預(yù)測(cè)精度偏低的問(wèn)題，從網(wǎng)絡(luò)優(yōu)化去噪的角度進(jìn)行分析，提出了一種基于K-shell分解與鄰居節(jié)點(diǎn)度（KSDNN）去噪的鏈路預(yù)測(cè)方法。該方法首先從全局的角度通過(guò)K-shell分解對(duì)復(fù)雜網(wǎng)絡(luò)中所有節(jié)點(diǎn)進(jìn)行重要性排序，然后從局部的角度結(jié)合節(jié)點(diǎn)鄰居節(jié)點(diǎn)的度對(duì)節(jié)點(diǎn)重要性進(jìn)行綜合評(píng)判，最后對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行優(yōu)化后進(jìn)行鏈路預(yù)測(cè)。通過(guò)在四個(gè)不同的真實(shí)網(wǎng)絡(luò)進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，所提方法預(yù)測(cè)精度優(yōu)于K-shell去噪的方法，且相較于傳統(tǒng)算法預(yù)測(cè)精度平均提升了2%左右。
關(guān)鍵詞：鏈路預(yù)測(cè)；復(fù)雜網(wǎng)絡(luò)；K-shell分解；鄰居節(jié)點(diǎn)度
中圖分類(lèi)號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695（2022）11-010-3270-05
doi： 10.19734/j.issn.1001-3695.2022.04.0146
Link prediction method based on K-shell decomposition and
neighbor node degree denoising
Zhang Xikang， Li Zetao
（School of Electrical Engineering， Guizhou University， Guiyang 550025， China）
Abstract：Link prediction is an important tool to study the structure and evolution mechanism of complex networks， and it is of great value to improve the accuracy of link prediction. To address the problem of low prediction accuracy of traditional network topology similarity-based algorithms， this paper proposed a link prediction method based on K-shell decomposition with neighbor node degree （KSDNN） denoising from the perspective of network optimization denoising. The method firstly ranked the importance of all nodes in a complex network by K-shell decomposition from a global perspective， then made a comprehensive evaluation of node importance from a local perspective by combining the degrees of nodes’ neighbor nodes， and finally performed link prediction after optimizing the network data. Through verification on four different real networks， the experimental results show that the prediction accuracy of the proposed method is better than that of the K-shell denoising method， and the prediction accuracy is improved by about 2% on average compared with the traditional algorithm.
Key words：link prediction; complex networks; K-shell decomposition; neighbor node degree
基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（61963009）；貴州省科技計(jì)劃項(xiàng)目（黔科合支撐［2019］2154號(hào)）
作者簡(jiǎn)介：張希康（1995-），男，四川廣元人，碩士研究生，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)；李澤滔（1960-），男（通信作者），貴州遵義人，教授，博導(dǎo)，博士，主要研究方向?yàn)橹悄茈娋W(wǎng)、計(jì)算機(jī)控制技術(shù)（1599306504@qq.com）.
0 引言
在互聯(lián)網(wǎng)時(shí)代，各種形式的網(wǎng)絡(luò)貫穿著人們的生活，復(fù)雜網(wǎng)絡(luò)的研究成為了新興熱點(diǎn)。鏈路預(yù)測(cè)作為復(fù)雜網(wǎng)絡(luò)研究的一個(gè)重要方向，也就自然而然地被推上了熱潮。鏈路預(yù)測(cè)的本質(zhì)是根據(jù)當(dāng)前所獲取的網(wǎng)絡(luò)結(jié)構(gòu)信息以及節(jié)點(diǎn)屬性等信息去還原網(wǎng)絡(luò)節(jié)點(diǎn)之間丟失的鏈接以及預(yù)測(cè)未來(lái)可能出現(xiàn)的鏈接關(guān)系［1］，這對(duì)于探究網(wǎng)絡(luò)的演變規(guī)律具有重要意義。除此之外，鏈路預(yù)測(cè)在電商網(wǎng)絡(luò)［2］、生物醫(yī)藥網(wǎng)絡(luò)［3］、社交網(wǎng)絡(luò)［4］、犯罪信息網(wǎng)絡(luò)［5］、金融網(wǎng)絡(luò)［6］等領(lǐng)域也有著十分廣泛的應(yīng)用。
現(xiàn)有的鏈路預(yù)測(cè)方法主要分為四大類(lèi)：基于似然分析的方法［7］、基于機(jī)器學(xué)習(xí)的方法［8］、基于節(jié)點(diǎn)屬性的方法［9］以及基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的方法［10］。其中，基于似然分析的方法應(yīng)用性不強(qiáng)，框架相對(duì)復(fù)雜，不適用于規(guī)模較大的復(fù)雜網(wǎng)絡(luò)，但有助于理解網(wǎng)絡(luò)的結(jié)構(gòu)特征。基于機(jī)器學(xué)習(xí)的方法盡管預(yù)測(cè)精度較高，但同樣也存在計(jì)算復(fù)雜度高的問(wèn)題，在面對(duì)復(fù)雜網(wǎng)絡(luò)的鏈路預(yù)測(cè)存在著一定的限制。基于節(jié)點(diǎn)屬性的方法由于其節(jié)點(diǎn)屬性信息較難獲取，且無(wú)法保證所獲取信息的準(zhǔn)確性，所以很少被研究者們使用。基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的方法只需考慮網(wǎng)絡(luò)的部分拓?fù)浣Y(jié)構(gòu)特性，使得鏈路預(yù)測(cè)的實(shí)現(xiàn)更為容易，是目前國(guó)內(nèi)外主流的研究方法。
近些年，在基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的鏈路預(yù)測(cè)方面也取得了一些成果。郁湧等人 ［11］通過(guò)對(duì)聚類(lèi)系數(shù)、節(jié)點(diǎn)中心線(xiàn)和度三個(gè)網(wǎng)絡(luò)拓?fù)渲笜?biāo)進(jìn)行融合，提出了一種能夠有效提高鏈路預(yù)測(cè)精度的算法。Li等人［12］提出基于相對(duì)路徑的方法，該方法除了利用節(jié)點(diǎn)對(duì)之間的路徑外，還利用節(jié)點(diǎn)與鄰居之間路徑的因子信息進(jìn)行鏈路預(yù)測(cè)的相似度計(jì)算，實(shí)驗(yàn)結(jié)果表明，基于相對(duì)路徑的方法可以獲得比傳統(tǒng)方法更高的預(yù)測(cè)精度，并具有較好的性能魯棒性。Song等人［13］提出了一種新的節(jié)點(diǎn)相似度指標(biāo)—異構(gòu)度懲罰（HDP），該指標(biāo)綜合了每對(duì)待預(yù)測(cè)節(jié)點(diǎn)擴(kuò)展鄰域的準(zhǔn)局部結(jié)構(gòu)信息和其共同鄰域的聚類(lèi)系數(shù)，對(duì)于具有不同統(tǒng)計(jì)特性的特定網(wǎng)絡(luò)，通過(guò)調(diào)整懲罰權(quán)值可以達(dá)到較好的鏈路預(yù)測(cè)性能。鄒列等人［14］同時(shí)對(duì)節(jié)點(diǎn)自身和鄰居節(jié)點(diǎn)度考慮，提出了一種Psor相似性指標(biāo)，該指標(biāo)相比于一些典型的預(yù)測(cè)指標(biāo)其預(yù)測(cè)精度最高可提升37.69%。Li等人［15］利用K-shell分解的方法，從網(wǎng)絡(luò)優(yōu)化去噪的角度來(lái)改善鏈路預(yù)測(cè)的精度，通過(guò)移除網(wǎng)絡(luò)中位于一層中的節(jié)點(diǎn)以及位于二層中但未連接到高層殼中的節(jié)點(diǎn)來(lái)提高了鏈路預(yù)測(cè)的精度，但該方法僅從全局性對(duì)節(jié)點(diǎn)重要性進(jìn)行評(píng)判，并未對(duì)節(jié)點(diǎn)重要性從局部進(jìn)行考慮。
本文繼續(xù)從復(fù)雜網(wǎng)絡(luò)去噪的角度出發(fā)，提出了一種基于K-shell分解與鄰居節(jié)點(diǎn)度（K-shell decomposition and neighbor node degree）去噪的鏈路預(yù)測(cè)方法，簡(jiǎn)稱(chēng)KSDNN，并在四個(gè)真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)集上與原始的11種相似性指標(biāo)進(jìn)行對(duì)比，驗(yàn)證了該方法有著更優(yōu)越的準(zhǔn)確性。
1 準(zhǔn)備工作
1.1 鏈路預(yù)測(cè)問(wèn)題描述
以無(wú)向無(wú)權(quán)網(wǎng)絡(luò)G（V，E）為例，鏈路預(yù)測(cè)的過(guò)程如圖1所示。其中，V表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合，E代表節(jié)點(diǎn)間所有連邊的集合。理論上，倘若網(wǎng)絡(luò)中存在N個(gè)節(jié)點(diǎn)，則網(wǎng)絡(luò)中至多有N（N-1）/2條連邊，記為U。而U-E就代表網(wǎng)絡(luò)中遺失的連邊或者未來(lái)可能出現(xiàn)的連邊，鏈路預(yù)測(cè)主要解決的就是缺失信息的還原和預(yù)測(cè)，這是信息科學(xué)中最基本的問(wèn)題。
一個(gè)無(wú)向無(wú)權(quán)網(wǎng)絡(luò)G（V，E）的拓?fù)浣Y(jié)構(gòu)可以轉(zhuǎn)換為邊列表和鄰接矩陣兩種方法表示，如圖2所示。通過(guò)某種鏈路預(yù)測(cè)算法，為未產(chǎn)生連邊的節(jié)點(diǎn)對(duì)（vx，vy）賦予一個(gè)分?jǐn)?shù)值，記為Sxy。Sxy值越大，則表明節(jié)點(diǎn)對(duì)（vx，vy）產(chǎn)生連邊的概率越大。
1.2 典型相似性算法
復(fù)雜網(wǎng)絡(luò)的鏈路預(yù)測(cè)中，相似性算法主要可分為三大類(lèi)，分別為：基于局部信息的相似性算法、基于路徑的相似性算法以及基于隨機(jī)游走的相似性算法。本文分別從每類(lèi)中選取一些典型的相似性算法來(lái)驗(yàn)證所提方法的有效性，如表1所示。各算法中符號(hào)的含義如表2所示。
CN算法僅考慮兩節(jié)點(diǎn)之間共同鄰居的數(shù)量，而Salton、Jaccard、S?rensen和HDI算法是在考慮共同鄰居基礎(chǔ)上又分別從不同角度考慮了兩端節(jié)點(diǎn)度的影響而衍生出來(lái)的。PA算法認(rèn)為兩節(jié)點(diǎn)產(chǎn)生鏈接的概率與兩節(jié)點(diǎn)度的乘積成正比。AA與RA算法均從被預(yù)測(cè)節(jié)點(diǎn)對(duì)的共同鄰居度的角度考慮，核心思想是度越大的共同鄰居貢獻(xiàn)反而越小，其主要差別在于共同鄰居節(jié)點(diǎn)權(quán)重的賦予方式不同。以上所提及指標(biāo)均屬于局部信息相似性指標(biāo)的范疇，LP和Katz算法隸屬于基于路徑的相似性算法，前者僅從局部路徑考慮，優(yōu)勢(shì)在于計(jì)算復(fù)雜度低，但預(yù)測(cè)精度相對(duì)于Katz算法較低；后者從全局路徑考慮，優(yōu)勢(shì)在于預(yù)測(cè)精度相對(duì)于LP算法較高，但計(jì)算復(fù)雜度也隨之增長(zhǎng)。Cos+指標(biāo)為基于隨機(jī)游走的相似性算法，通過(guò)引入馬氏距離，利用對(duì)應(yīng)向量的余弦相似性來(lái)進(jìn)行預(yù)測(cè)，具有較高的預(yù)測(cè)精度。
2 提出的方法
2.1 基于K-shell分解與鄰居節(jié)點(diǎn)度去噪的鏈路預(yù)測(cè)方法
由于各式各樣的因素，網(wǎng)絡(luò)數(shù)據(jù)總是或多或少地存在著一些噪聲信息，倘若不對(duì)網(wǎng)絡(luò)原始數(shù)據(jù)進(jìn)行優(yōu)化去噪而直接進(jìn)行鏈路預(yù)測(cè)，那么將會(huì)對(duì)鏈路預(yù)測(cè)的準(zhǔn)確性造成一定的影響。如若可以通過(guò)某種方法識(shí)別出網(wǎng)絡(luò)中的噪聲信息并刪除，那么將可以在一定程度上提升鏈路預(yù)測(cè)的準(zhǔn)確性。
為此，本文提出了基于KSDNN去噪的鏈路預(yù)測(cè)方法，通過(guò)識(shí)別網(wǎng)絡(luò)中的噪聲信息并刪除，然后再進(jìn)行鏈路預(yù)測(cè)，以此來(lái)達(dá)到提升預(yù)測(cè)精度的目的。
該方法從全局和局部?jī)蓚€(gè)角度進(jìn)行考慮，通過(guò)K-shell分解算法，從節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的位置進(jìn)行全局性考慮。K-shell分解算法的核心思想為遞歸地移除網(wǎng)絡(luò)中度低于或等于k的節(jié)點(diǎn)，分解過(guò)程如圖3所示。
找出網(wǎng)絡(luò)中所有度為1的節(jié)點(diǎn)并將其對(duì)應(yīng)的邊一并刪除。如果網(wǎng)絡(luò)中出現(xiàn)度為1的新節(jié)點(diǎn)，則這些節(jié)點(diǎn)及其連邊也將被刪除，重復(fù)這個(gè)操作，直到網(wǎng)絡(luò)中不存在度為1的節(jié)點(diǎn)，并將這些刪除的節(jié)點(diǎn)記為k=1。同理，k=2，k=3，…是使用相同的步驟獲得。K-shell分解算法能很好地從全局的角度區(qū)分節(jié)點(diǎn)重要性，對(duì)節(jié)點(diǎn)所處網(wǎng)絡(luò)位置進(jìn)行分析，根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的重要程度將其分為不同的k層中，節(jié)點(diǎn)所處層的k值越大節(jié)點(diǎn)重要程度越高。然而，若僅僅只用K-shell分解算法對(duì)節(jié)點(diǎn)重要性進(jìn)行排序則不能區(qū)分同一k層下不同節(jié)點(diǎn)的重要性，從圖3中可以明顯看出，通過(guò)K-shell分解算法對(duì)節(jié)點(diǎn)進(jìn)行重要性排序后，節(jié)點(diǎn)12、13、14、15、16、17均位于第1層中，K-shell分解算法默認(rèn)為處于同一層下的這些節(jié)點(diǎn)重要性是相同的，但實(shí)際上節(jié)點(diǎn)12和15的重要性要明顯高于其他節(jié)點(diǎn)。因此，如果只用K-shell分解算法對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行重要性排序會(huì)存在一些不足。
為此，又從局部性角度考慮節(jié)點(diǎn)重要性，其中經(jīng)典的局部性節(jié)點(diǎn)重要性識(shí)別方法主要包括度中心性、介數(shù)中心性以及接近度中心性三種。由于度中心性反映了節(jié)點(diǎn)與其周?chē)?jié)點(diǎn)建立鏈接的能力大小，度值越大，則表明與該節(jié)點(diǎn)產(chǎn)生鏈接的節(jié)點(diǎn)越多，節(jié)點(diǎn)的重要性越高，能很好代表節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)局部影響力，所以本文選擇節(jié)點(diǎn)的度中心性從局部角度進(jìn)行考慮。為了使度指標(biāo)能統(tǒng)一衡量節(jié)點(diǎn)的重要性，對(duì)其進(jìn)行歸一化后的度指標(biāo)可表示為
其中：CD（vi）表示節(jié)點(diǎn)vi的歸一化度指標(biāo)；ki為節(jié)點(diǎn)vi的度；N為網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)。
文獻(xiàn)［14］中所提出的Psor指數(shù)以及Psor相似性指標(biāo)，既考慮了節(jié)點(diǎn)的度又考慮了節(jié)點(diǎn)鄰居節(jié)點(diǎn)的度，且在復(fù)雜網(wǎng)絡(luò)的鏈路預(yù)測(cè)中取得了不錯(cuò)的預(yù)測(cè)精度。其定義的Psor指數(shù)和Psor相似性指標(biāo)為
其中：SPsorxy 為節(jié)點(diǎn)x與y之間的Psor相似性指標(biāo)；Γ（x）∩Γ（y） 為節(jié)點(diǎn)x與y之間的共同鄰居集合；kx與ky分別表示節(jié)點(diǎn)x與y的度；Psorx與Psory分別表示節(jié)點(diǎn)x與y的Psor指數(shù)，Psor指數(shù)越大，節(jié)點(diǎn)的重要性越大。
由此可以得出，網(wǎng)絡(luò)節(jié)點(diǎn)的重要性與節(jié)點(diǎn)的度和其鄰居節(jié)點(diǎn)的度均有關(guān)系，節(jié)點(diǎn)的度及其鄰居節(jié)點(diǎn)的度越大，節(jié)點(diǎn)的重要性程度越高。由于K-shell分解算法已經(jīng)從側(cè)面上反映了節(jié)點(diǎn)度的大小，顯然節(jié)點(diǎn)位置所處層的k值越大，節(jié)點(diǎn)的度越大。所以本文又通過(guò)引入了節(jié)點(diǎn)鄰居節(jié)點(diǎn)的度來(lái)對(duì)節(jié)點(diǎn)重要性進(jìn)行綜合性評(píng)判。
基于KSDNN去噪的鏈路預(yù)測(cè)方法的核心思想為將節(jié)點(diǎn)鄰居節(jié)點(diǎn)的度與K-shell分解算法結(jié)合起來(lái)對(duì)節(jié)點(diǎn)的重要性進(jìn)行綜合性評(píng)估，并把判定為不重要的節(jié)點(diǎn)當(dāng)做噪聲信息進(jìn)行刪除，再用優(yōu)化后的網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行鏈路預(yù)測(cè)。在對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行優(yōu)化去噪的過(guò)程中，噪聲條件的設(shè)定又變得格外重要，為了避免在刪除節(jié)點(diǎn)及連邊的過(guò)程中誤刪過(guò)多的真實(shí)信息，KSDNN方法只刪除網(wǎng)絡(luò)中k=1且該節(jié)點(diǎn)鄰居節(jié)點(diǎn)度小于或等于2的節(jié)點(diǎn)。例如圖3中的節(jié)點(diǎn)11位于第一層且其鄰居節(jié)點(diǎn)10的度等于2，所以該方法會(huì)將其判定為不重要節(jié)點(diǎn)并刪除該節(jié)點(diǎn)及其連邊，而其余位于一層中的節(jié)點(diǎn)其鄰居節(jié)點(diǎn)度均大于2，故不會(huì)被刪除。基于KSDNN去噪的鏈路預(yù)測(cè)方法其流程如圖4所示，具體實(shí)現(xiàn)方法描述如下：
a）對(duì)給定網(wǎng)絡(luò)G（V，E）的邊列表數(shù)據(jù)集，根據(jù)節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性的不同，利用K-shell分解算法對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)進(jìn)行重要性劃分，分別為每個(gè)節(jié)點(diǎn)賦予不同的k值。
b）計(jì)算所有位于k=1層節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的度，若其節(jié)點(diǎn)鄰居節(jié)點(diǎn)的度小于或等于2，則刪除該節(jié)點(diǎn)。
c）將去噪后的網(wǎng)絡(luò)邊列表轉(zhuǎn)換為網(wǎng)絡(luò)鄰接矩陣的形式，以便于計(jì)算機(jī)的識(shí)別，并根據(jù)設(shè)定的劃分比例，將鄰接矩陣劃分為訓(xùn)練集ET和測(cè)試集EP。
d）根據(jù)訓(xùn)練集ET中的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息，利用原始的典型相似性算法，計(jì)算網(wǎng)絡(luò)中所有未知鏈接集合U-ET的相似性分?jǐn)?shù)矩陣。
e）根據(jù)測(cè)試集EP和相似性分?jǐn)?shù)矩陣，評(píng)估基于KSDNN去噪的鏈路預(yù)測(cè)方法的準(zhǔn)確率。
2.2 復(fù)雜度分析
在所選的11種算法中，由于PA算法相對(duì)簡(jiǎn)單，只考慮了被測(cè)節(jié)點(diǎn)對(duì)的度，假設(shè)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)為N，其時(shí)間復(fù)雜度則為O（N2）。而Salton、Jaccard、Srenson、HDI、AA以及RA算法均是在共同鄰居的基礎(chǔ)上改進(jìn)的，因此它們與CN算法的時(shí)間復(fù)雜度相同，均為O（N3）。又假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)的平均度為k，LP算法僅考慮了局部路徑信息，其時(shí)間復(fù)雜度為O（Nk2）。而Katz算法是從全局路徑信息考慮，時(shí)間復(fù)雜度要高于LP算法，為O（N3）。Cos+算法的時(shí)間復(fù)雜度也為O（N3）。本文所提出的基于KSDNN去噪的鏈路預(yù)測(cè)方法是用典型的鏈路預(yù)測(cè)算法在進(jìn)行鏈路預(yù)測(cè)之前先對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行優(yōu)化去噪，因此并沒(méi)有改變算法的時(shí)間復(fù)雜度，而且由于去除了網(wǎng)絡(luò)中一些噪聲節(jié)點(diǎn)，反而減少了鏈路預(yù)測(cè)的時(shí)間，提高了算法的效率。
3 實(shí)驗(yàn)結(jié)果與分析
3.1 實(shí)驗(yàn)數(shù)據(jù)
本文將選取四個(gè)鏈路預(yù)測(cè)中經(jīng)常使用的不同類(lèi)型數(shù)據(jù)集來(lái)驗(yàn)證本文所提算法的有效性。各網(wǎng)絡(luò)數(shù)據(jù)的信息如下：
a）大學(xué)成員間的郵件交換網(wǎng)絡(luò)（Email）。該網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)代表作者所寫(xiě)的郵件，連邊則代表兩者之間存在過(guò)郵件來(lái)往。
b）美國(guó)政治博客網(wǎng)絡(luò)（Political Blogs，PB）。該網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)代表不同政治家的博客網(wǎng)頁(yè)，連邊則代表兩個(gè)博客網(wǎng)頁(yè)之間存在超鏈接。
c）蛋白質(zhì)相互作用網(wǎng)絡(luò)（Yeast）。該網(wǎng)絡(luò)中的節(jié)點(diǎn)代表不同的生物蛋白質(zhì)，連邊則表示兩種蛋白質(zhì)之間的關(guān)聯(lián)作用。
d）社交友誼網(wǎng)絡(luò)（Facebook）。該網(wǎng)絡(luò)中節(jié)點(diǎn)代表Facebook社交平臺(tái)上的每個(gè)用戶(hù)，連邊則表示兩個(gè)用戶(hù)之間存在著溝通交流。
四種網(wǎng)絡(luò)的基本拓?fù)涮卣魅绫?所示，其中：|V|代表網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)，|E|代表網(wǎng)絡(luò)中的連邊數(shù)，davg代表網(wǎng)絡(luò)中節(jié)點(diǎn)的平均度，C代表網(wǎng)絡(luò)的平均聚類(lèi)系數(shù)，r代表網(wǎng)絡(luò)的同配系數(shù)。從表3中可以看出，盡管選取網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量相差不大，但每種網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)均不同，例如Facebook網(wǎng)絡(luò)的平均度最大，Email網(wǎng)絡(luò)和PB網(wǎng)絡(luò)平均度較小，而Yeast網(wǎng)絡(luò)中平均度最小，表明Facebook網(wǎng)絡(luò)相對(duì)稠密，Email網(wǎng)絡(luò)和PB網(wǎng)絡(luò)相對(duì)均勻，Yeast網(wǎng)絡(luò)相對(duì)稀疏。因此，選取這四種網(wǎng)絡(luò)來(lái)驗(yàn)證所提鏈路預(yù)測(cè)方法具有一定代表性。
3.2 評(píng)價(jià)指標(biāo)
曲線(xiàn)下面積（AUC）、精確度（precision）以及排序分（ranking score）是三種衡量鏈路預(yù)測(cè)算法精確度的主要指標(biāo)。
AUC可概括為從測(cè)試集中隨機(jī)選取一條連邊屬于存在邊的概率高于從不存在邊集合中隨機(jī)選中不存在邊的概率［26］。若在重復(fù)獨(dú)立比較M次的過(guò)程中，有M1次滿(mǎn)足從測(cè)試集中隨機(jī)選取一條連邊屬于存在邊的概率高于從不存在邊集合中選中不存在邊的概率，M2次兩者選中概率相等，則AUC定義為
precision僅僅只關(guān)心最靠前的L條預(yù)測(cè)邊預(yù)測(cè)是否準(zhǔn)確，若有P條預(yù)測(cè)準(zhǔn)確，由于預(yù)測(cè)邊根據(jù)相似性分?jǐn)?shù)降序排列，則靠前的L條邊中，有P條屬于測(cè)試集，precision定義為
ranking score更多傾向于考慮被預(yù)測(cè)邊的排序，若令W為網(wǎng)絡(luò)中未知邊的集合，re為測(cè)試邊的排序排名，則該測(cè)試邊的排序分RSe為
接著遍歷測(cè)試集中所有的邊，可得系統(tǒng)的排序分RS為
其中：e為測(cè)試邊；EP為測(cè)試集。
由于AUC具有從整體上衡量算法的精確度［27］且不受正負(fù)樣本比例影響的優(yōu)越性，故是使用最廣泛的評(píng)價(jià)指標(biāo)。本文也將選取AUC指標(biāo)來(lái)驗(yàn)證所提方法的準(zhǔn)確性，AUC值越大，則表明預(yù)測(cè)精度越高。
3.3 數(shù)據(jù)集劃分
數(shù)據(jù)集的劃分也對(duì)預(yù)測(cè)結(jié)果至關(guān)重要，proportion（劃分比例）的不同，也會(huì)造成預(yù)測(cè)精度不同。為了尋求最佳的proportion，本文選取了CN、HDI、PA、RA以及Katz 五種算法分別在四種不同網(wǎng)絡(luò)中根據(jù)不同proportion（proportion取0.5～0.9）進(jìn)行實(shí)驗(yàn)對(duì)比，結(jié)果如圖5所示。
從圖5的四個(gè)圖中可以看出，PA算法的AUC值受proportion的改變影響較小，不與proportion成正比關(guān)系。在Email網(wǎng)絡(luò)和Yeast網(wǎng)絡(luò)中，當(dāng)proportion=0.8時(shí)，PA算法的AUC值最高；在PB網(wǎng)絡(luò)和Facebook網(wǎng)絡(luò)中，當(dāng)proportion=0.7時(shí)，PA算法的AUC值最高；除了PA算法外，其余各算法的AUC值均正比于proportion，當(dāng)proportion=0.9時(shí)，AUC值達(dá)到最大。故在驗(yàn)證本文所提算法時(shí)，proportion也均取0.9。
3.4 實(shí)驗(yàn)結(jié)果
將原始的典型指標(biāo)、文獻(xiàn)［15］中所提出的K-shell方法去噪后指標(biāo)以及通過(guò)KSDNN方法去噪后的指標(biāo)預(yù)測(cè)精度在四種不同結(jié)構(gòu)的真實(shí)網(wǎng)絡(luò)中進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如圖6所示。
從圖6中可以看出，由于每種網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不盡相同，同樣的算法在不同的網(wǎng)絡(luò)中預(yù)測(cè)精度差異較大。例如在Yeast網(wǎng)絡(luò)中，PA算法與Katz算法預(yù)測(cè)精度值最高，其余算法的預(yù)測(cè)精度都很低，表明除了PA與Katz算法外，其余算法不適用于Yeast網(wǎng)絡(luò)。而在Email、PB和Facebook網(wǎng)絡(luò)中，CN、AA、RA和Cos+等算法預(yù)測(cè)精度又相對(duì)較高，較適用于這三種網(wǎng)絡(luò)。
由于各種相似性算法所利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)性質(zhì)的差異性，刪除網(wǎng)絡(luò)中的節(jié)點(diǎn)對(duì)不同算法的預(yù)測(cè)精度也不盡相同，通過(guò)K-shell與KSDNN方法去噪后，一些少量算法的預(yù)測(cè)精度相較于原始典型的算法反而有些許的降低，例如Yeast網(wǎng)絡(luò)中的Jaccard、S?rensen、HDI算法，F(xiàn)acebook網(wǎng)絡(luò)中的Cos+算法。
總體分析來(lái)看，除了Email網(wǎng)絡(luò)中的PA、RA算法，Yeast網(wǎng)絡(luò)中AA、RA算法通過(guò)KSDNN方法去噪后其AUC值相比K-shell方法去噪后的AUC值有略微的降低外，其余算法KSDNN方法去噪后的AUC值都優(yōu)于K-shell方法去噪后的AUC值。結(jié)果表明本文方法相比于K-shell去噪的方法以及原始典型的預(yù)測(cè)算法都要更勝一籌，主要原因在于若僅利用K-shell方法進(jìn)行去噪容易造成網(wǎng)絡(luò)中過(guò)多真實(shí)的節(jié)點(diǎn)信息被刪除，通過(guò)結(jié)合局部性的角度對(duì)節(jié)點(diǎn)重要性進(jìn)行綜合性評(píng)判，不僅能夠減小網(wǎng)絡(luò)中過(guò)多的真實(shí)節(jié)點(diǎn)信息被刪除，也能達(dá)到去噪的效果，且本文方法相比于原始典型算法其AUC值平均提高了2%左右，最高可提高7%。
4 結(jié)束語(yǔ)
本文在傳統(tǒng)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相似性的鏈路預(yù)測(cè)算法之上，對(duì)網(wǎng)絡(luò)數(shù)據(jù)優(yōu)化去噪的角度進(jìn)行分析，提出了一種基于K-shell分解與鄰居節(jié)點(diǎn)度去噪（KSDNN）的鏈路預(yù)測(cè)算法。為了從全局和局部對(duì)節(jié)點(diǎn)重要性進(jìn)行綜合考慮，本文分別引入了K-shell分解算法以及節(jié)點(diǎn)鄰居節(jié)點(diǎn)的度進(jìn)行評(píng)估，從而識(shí)別出網(wǎng)絡(luò)中可能存在的噪聲信息并刪除，然后再利用典型的相似性算法進(jìn)行預(yù)測(cè)。通過(guò)在四種不同真實(shí)網(wǎng)絡(luò)中選擇11種典型的相似性算法進(jìn)行實(shí)驗(yàn)，對(duì)比得出，本文算法使得復(fù)雜網(wǎng)絡(luò)的鏈路預(yù)測(cè)精度更高。在后續(xù)工作中，將會(huì)嘗試將該方法運(yùn)用于有向有權(quán)網(wǎng)絡(luò)中，并考慮是否可以將K-shell分解算法與其他節(jié)點(diǎn)重要性指標(biāo)進(jìn)行綜合考慮。
參考文獻(xiàn)：
［1］呂琳媛. 復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè) ［J］. 電子科技大學(xué)學(xué)報(bào)，2010，39（5）： 651-661. （Lyu Linyuan. Link prediction on complex networks ［J］. Journal of University of Electronic Science amp; Technology of China，2010，39（5）： 651-661.
［2］Liu Guoguang. An ecommerce recommendation algorithm based on link prediction ［J］. AEJ-Alexandria Engineering Journal，2021 （6）： 905-910.
［3］Abbas K，Abbasi A，Dong S，et al. Application of network link prediction in drug discovery ［J］. BMC bioinformatics，2021，22（1）： 1-21.
［4］Berahmand K，Nasiri E，Rostami M，et al. A modified DeepWalk method for link prediction in attributed social network ［J］. Computing，2021，103（10）： 2227-2249.
［5］Lim M，Abdullah A，Jhanjhi N Z. Performance optimization of criminal network hidden link prediction model with deep reinforcement learning ［J］. Journal of King Saud University-Computer and Information Sciences，2021，33（10）： 1202-1210.
［6］Park J H，Chang W，Song J W. Link prediction in the Granger causali-ty network of the global currency market ［J］. Physica A： Statistical Mechanics and Its Applications，2020，553： 124668.
［7］Clauset A. Hierarchical structure and the prediction of missing links in networks ［J］. Nature，2008，453（7191）： 98-101.
［8］Keikha M M，Rahgozar M，Asadpour M. DeepLink： a novel link prediction framework based on deep learning ［J］. Journal of Information Science，2021，47（5）： 642-657.
［9］Bilinovic＇ А，Sokolovska V. Homophily in social networks ［J］. Zbornik Matice srpske za drustvene nauke，2016 （155-156）： 325-338.
［10］Lyu Linyuan，Zhou Tao. Link prediction in complex networks： a survey ［J］. Physica A： Statistical Mechanics and Its Applications，2011，390（6）： 1150-1170.
［11］郁湧，王瑩港，羅正國(guó)，等. 基于聚類(lèi)系數(shù)和節(jié)點(diǎn)中心性的鏈路預(yù)測(cè)算法 ［J］. 清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2022，62（1）： 98-104. （Yu Yong，Wang Yinggang，Luo Zhengguo，et al. Link prediction algorithm based on clustering coefficient and node centrality ［J］. Journal of Tsinghua University ：Science and Technology，2022，62（1）： 98-104.）
［12］Li Shibao，Huang Junwei，Liu Jianhang，et al. Relative-path-based algorithm for link prediction on complex networks using a basic similarity factor ［J］. Chaos，2020，30（1）： 131-144.
［13］Song Rongrong，Ling Guang，F(xiàn)an Qingju，et al. Link prediction based on heterogeneous degree penalization with extending neighbors and clustering coefficient ［J］. International Journal of Modern Phy-sics C，2021，22（5）： 29-36.
［14］鄒列，張?jiān)孪? 基于復(fù)雜網(wǎng)絡(luò)的 Psor 鏈路預(yù)測(cè)算法 ［J］. 電訊技術(shù)，2021，61（12）： 1579-1585. （Zou Lie，Zhang Yuexia. A Psor link prediction algorithm based on complex network ［J］. Telecommunication Engineering，2021，61（12）： 1579-1585.）
［15］Li Jie，Peng Xiyang，Wang Jian，et al. A method for improving the accuracy of link prediction algorithms ［J］. Complexity，2021，5（6）： 76-87.
［16］Lorrain F，White H C. Structural equivalence of individuals in social networks ［J］. Social Networks，1977，1（1）： 67-98.
［17］Salton G，McGill M J. Introduction to modern information retrieval ［M］. Auckland： McGraw-Hill，1983.
［18］Jaccard P. Etude comparative de la distribution florale dans une portion des Alpes et des Jura ［J］. Bulletin de la Societe Vaudoise des Sciences Naturelles，1901，37（142）： 547-579.
［19］Sorensen T A. A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons ［J］. Biologiske Skrifter，1948，5（4）： 1-34.
［20］Zhou Tao，Lyu Linyuan，Zhang Yicheng. Predicting missing links via local information ［J］. European Physical Journal B，2009，71（4）： 623-630.
［21］Barabasi A L，Albert R. Emergence of scaling in random networks ［J］. Science，1999，286（5439）： 509-512.
［22］Adamic L A，Adar E. Friends and neighbors on the Web ［J］. Social Networks，2003，25（3）： 211-230.
［23］Lyu Linyuan，Jin Cihang，Zhou Tao. Similarity index based on local paths for link prediction of complex networks ［J］. Physical Review E，2009，80（4）： 46-52.
［24］Katz L. A new status index derived from sociometric analysis ［J］. Psychometrika，1953，18（1）： 39-43.
［25］Fouss F，Pirotte A，Renders J M，et al. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation ［J］. IEEE Trans on Knowledge and Data Engineering，2007，19： 355-369.
［26］Fawcett T. An introduction to ROC analysis ［J］. Pattern Recognition Letters，2005，27（8）： 861-874.
［27］Hanley J A ，McNeil B J. The meaning and use of the area under a receiver operating characteristic （ROC） curve ［J］. Radiology，1982，143（1）： 29-36.
