潘永昊，于洪濤，劉樹新

?

基于神經(jīng)網(wǎng)絡(luò)的鏈路預(yù)測算法

潘永昊，于洪濤，劉樹新

（國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002）

針對當(dāng)前基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相似性的鏈路預(yù)測算法普遍存在精確度較低且適應(yīng)性不強的問題，研究發(fā)現(xiàn)融合算法能夠有效改善這些問題。提出了一種基于神經(jīng)網(wǎng)絡(luò)的融合鏈路預(yù)測算法，主要通過神經(jīng)網(wǎng)絡(luò)對不同鏈路預(yù)測相似性指標(biāo)進(jìn)行融合。該算法使用神經(jīng)網(wǎng)絡(luò)對不同相似性指標(biāo)的數(shù)值特征進(jìn)行學(xué)習(xí)，同時采用標(biāo)準(zhǔn)粒子群算法對神經(jīng)網(wǎng)絡(luò)進(jìn)行了優(yōu)化，并通過優(yōu)化學(xué)習(xí)后的神經(jīng)網(wǎng)絡(luò)模型計算出融合指標(biāo)。多個真實網(wǎng)絡(luò)數(shù)據(jù)集上實驗表明，該算法的預(yù)測精度明顯高于融合之前的各項指標(biāo)，并且優(yōu)于現(xiàn)有融合方法的精度。

復(fù)雜網(wǎng)絡(luò)；鏈路預(yù)測；神經(jīng)網(wǎng)絡(luò)；BP算法

1 引言

鏈路預(yù)測是復(fù)雜網(wǎng)絡(luò)研究的一個重要部分，是指通過網(wǎng)絡(luò)中已知的節(jié)點以及結(jié)構(gòu)信息，預(yù)測網(wǎng)絡(luò)中尚未產(chǎn)生連接的2個節(jié)點之間產(chǎn)生連接的可能性[1]。這種預(yù)測包括對網(wǎng)絡(luò)中已有但未被觀測到連接的預(yù)測，以及網(wǎng)絡(luò)中未來產(chǎn)生連接的預(yù)測。

鏈路預(yù)測的概念一經(jīng)提出，就獲得了眾多領(lǐng)域的廣泛關(guān)注，在很多領(lǐng)域得到了實際應(yīng)用，如指導(dǎo)生物蛋白質(zhì)網(wǎng)絡(luò)構(gòu)建[2]、分析社會網(wǎng)絡(luò)結(jié)構(gòu)[3]、解決推薦系統(tǒng)中數(shù)據(jù)稀疏問題[4]等。與此同時，鏈路預(yù)測還具有重要的理論研究意義，如網(wǎng)絡(luò)結(jié)構(gòu)與演化的研究[5-6]等。經(jīng)過了多年的研究和探索，鏈路預(yù)測的算法逐步形成基于相似性的方法和基于似然估計的方法[1]。在鏈路預(yù)測的研究過程中，所研究的網(wǎng)絡(luò)模型，也從最初無權(quán)無向網(wǎng)絡(luò)，擴展到了含權(quán)網(wǎng)絡(luò)[7]、有向網(wǎng)絡(luò)[8]、異質(zhì)網(wǎng)絡(luò)[9]，從靜態(tài)模型發(fā)展到了時序模型[10]。但不論模型如何復(fù)雜，靜態(tài)還是時序，都是以無權(quán)無向網(wǎng)絡(luò)為出發(fā)點，其算法也是在無權(quán)無向網(wǎng)絡(luò)算法思想的基礎(chǔ)上不斷改進(jìn)。在無權(quán)無向網(wǎng)絡(luò)的算法中，也存在一系列矛盾：1) 基于似然估計的方法最大的問題是計算復(fù)雜度高，不適合在規(guī)模較大的網(wǎng)絡(luò)中應(yīng)用；2) 基于相似性的方法具有運算復(fù)雜度低的特點，但其運算效果會受到網(wǎng)絡(luò)結(jié)構(gòu)的影響，在不同結(jié)構(gòu)特點的網(wǎng)絡(luò)中，運算效果不夠穩(wěn)定，不具有頑健性。

針對以上問題，文獻(xiàn)[1]中提出了基于不同的相似性算法進(jìn)行融合的方法，用以提高鏈路預(yù)測算法的穩(wěn)定性和頑健性，同時這種融合方法可以兼顧基于相似性的鏈路預(yù)測方法運算復(fù)雜度低的優(yōu)點。本文借鑒這種融合方法[1]的思想，提出一種基于神經(jīng)網(wǎng)絡(luò)的鏈路預(yù)測算法（NNLP，neural network-based link prediction algorithm），對鏈路預(yù)測相似性指標(biāo)融合問題進(jìn)行研究。主要貢獻(xiàn)如下：1) 使用不同的鏈路預(yù)測相似性指標(biāo)，通過訓(xùn)練神經(jīng)網(wǎng)絡(luò)，實現(xiàn)對不同相似性指標(biāo)的非線性計算，得出融合指標(biāo)；2) 在真實的數(shù)據(jù)集中進(jìn)行測試，并與基準(zhǔn)方法進(jìn)行比較，在不同的真實網(wǎng)絡(luò)數(shù)據(jù)集上都得到了理想的效果，證明本文方法能夠有效提高鏈路預(yù)測的準(zhǔn)確性和頑健性。

2 相關(guān)工作

文獻(xiàn)[1]中介紹了幾種基于相似性的鏈路預(yù)測方法，包括基于局部相似性的方法，如common neighbors（CN）[11]、adamic-adar（AA）[12]、resource allocation index（RA）[13]、preferential attachment Index（PA）[14]，extended resource allocation index[15]，以及基于全局路徑相似性的方法，最常用的是Katz指標(biāo)[16]。Liu等[17]在研究中通過增加節(jié)點對之間包含的局部拓?fù)湫畔?，提出了基于?jié)點間拓?fù)浼訖?quán)的相似性鏈路預(yù)測方法。文獻(xiàn)[18-19]通過實驗對比了基于相似性的鏈路預(yù)測指標(biāo)性能，在不同的實際網(wǎng)絡(luò)中，不同的結(jié)構(gòu)相似性指標(biāo)表現(xiàn)各有優(yōu)劣，性能差異較大，頑健性較差。文獻(xiàn)[20]研究發(fā)現(xiàn)一些算法輸出的結(jié)果中部分正確結(jié)果具有互補性。同時在文獻(xiàn)[1]在展望中提出可以通過合適的方法，對不同的相似性指標(biāo)進(jìn)行融合，使融合以后的指標(biāo)能夠適應(yīng)不同的實際網(wǎng)絡(luò)，表現(xiàn)出更高的精確度和更好的頑健性。

在融合算法方面，研究者開展過一些相關(guān)研究，但是總體來說相對較少。文獻(xiàn)[18]中采用3種不同的OWA（ordered weighted averaging）算子對9種基于局部信息的結(jié)構(gòu)相似性指標(biāo)進(jìn)行了融合。文獻(xiàn)[20]非常巧妙地把鏈路預(yù)測問題定義為了二分類問題，并提出一種基于Adaboost的鏈路預(yù)測算法，借用 Boosting方法通過錯誤反饋提升弱學(xué)習(xí)算法得到強學(xué)習(xí)算法的思想，并利用算法互補性原則選取若干鏈路預(yù)測算法作為弱分類器，基于AdaBoost算法提出并實現(xiàn)了一個新的算法。文獻(xiàn)[21]則提出一種基于choquet模糊積分的鏈路預(yù)測算法，引入數(shù)學(xué)中模糊測度和模糊積分的概念，在考慮不同指標(biāo)的重要性和指標(biāo)交互作用的基礎(chǔ)上，對指標(biāo)進(jìn)行融合。通過已有的相關(guān)研究可以證實，融合結(jié)構(gòu)相似性指標(biāo)的方法的確能夠提高鏈路預(yù)測的效果，使融合后的算法能夠克服各個單一指標(biāo)只適用于與其結(jié)構(gòu)特性接近網(wǎng)絡(luò)的問題。

3 算法描述

3.1 訓(xùn)練集說明

3.2 使用粒子群算法確定神經(jīng)網(wǎng)絡(luò)的初始參數(shù)

使用多種相似性指標(biāo)對神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，各個相似性指標(biāo)之間具有很強的相關(guān)性，直接用于訓(xùn)練神經(jīng)網(wǎng)絡(luò)很容易過擬合，因此，首先采用標(biāo)準(zhǔn)粒子群（PSO，particle swarm optimization）算法優(yōu)化神經(jīng)網(wǎng)絡(luò)的初始閾值和權(quán)值。

3.3 訓(xùn)練神經(jīng)網(wǎng)

通過BP迭代學(xué)習(xí)算法，對神經(jīng)網(wǎng)絡(luò)中的所有參數(shù)，即連接權(quán)值和閾值進(jìn)行更新估計，對于任意參數(shù)的更新估計表達(dá)式為

由Sigmoid函數(shù)的性質(zhì)得到

由式(3)和式(4)得到

由類似原理可以計算出

其中

最終確定神經(jīng)網(wǎng)絡(luò)的參數(shù)，即連接權(quán)值和閾值。

3.4 計算融合指標(biāo)

按照此方法，計算出網(wǎng)絡(luò)中未連邊節(jié)點對的連邊相似性融合指標(biāo)的數(shù)值，并按照這個數(shù)值，從大到小進(jìn)行排列，排在最前面的節(jié)點對之間存在或未來產(chǎn)生連邊的概率最大。整個計算過程如算法1所示。

算法1

輸出 NNLP算法計算的融合指標(biāo)

5) 使用步驟4)中訓(xùn)練的神經(jīng)網(wǎng)絡(luò)計算融合指標(biāo)。

6) 返回計算得出的融合指標(biāo)。

4 實驗與分析

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

為了驗證所提鏈路預(yù)測算法的有效性，本文在6個真實網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行鏈路預(yù)測對比實驗，分別如下。

1) 政治家博客網(wǎng)絡(luò)（PB），原數(shù)據(jù)是有向網(wǎng)絡(luò)，節(jié)點為博客網(wǎng)頁，邊表示網(wǎng)頁之間的超鏈接。

2) 科學(xué)家合作網(wǎng)絡(luò)（NS），網(wǎng)絡(luò)中的節(jié)點是在網(wǎng)絡(luò)科學(xué)領(lǐng)域發(fā)表過論文的科學(xué)家，連邊表示科學(xué)家的合作關(guān)系。

3) 爵士音樂家合作網(wǎng)（Jazz），網(wǎng)絡(luò)中的節(jié)點為爵士音樂家，連邊表示音樂家的合作關(guān)系。

4) 線蟲的神經(jīng)網(wǎng)絡(luò)（CE），節(jié)點表示線蟲的神經(jīng)元，邊表示神經(jīng)元突觸。

5) 美國航空網(wǎng)絡(luò)（USAir），網(wǎng)絡(luò)中的每個節(jié)點對應(yīng)一個機場，連邊表示2個機場之間有直飛的航線。

6) 蛋白質(zhì)相互作用網(wǎng)絡(luò)（Yeast），網(wǎng)絡(luò)中的每個節(jié)點表示一種蛋白質(zhì)，邊表示蛋白質(zhì)間的相互作用關(guān)系。

以上6個網(wǎng)絡(luò)的基本結(jié)構(gòu)參數(shù)如表1所示。其中，||表示網(wǎng)絡(luò)中節(jié)點的個數(shù)，||表示邊的數(shù)量，<>表示網(wǎng)絡(luò)的平均度，<>表示網(wǎng)絡(luò)平均距離，表示網(wǎng)絡(luò)簇系數(shù)，表示結(jié)合系數(shù)，表示度的分布熵。

4.2 度量指標(biāo)

4.3 神經(jīng)網(wǎng)絡(luò)的參數(shù)優(yōu)化與訓(xùn)練

選擇要融合的相似性指標(biāo)是一個基礎(chǔ)，決定了本算法的結(jié)果精確性。從這點出發(fā)，應(yīng)該考慮結(jié)果精確度高、重疊少的指標(biāo)。為了能進(jìn)一步用此算法分析挖掘網(wǎng)絡(luò)結(jié)構(gòu)和指標(biāo)之間、指標(biāo)和指標(biāo)的關(guān)系，取CN、PA、AA、Katz 4種含義較為明確的基準(zhǔn)指標(biāo)進(jìn)行融合。使用神經(jīng)網(wǎng)絡(luò)對指標(biāo)進(jìn)行融合，實質(zhì)上就是把不同指標(biāo)進(jìn)行非線性疊加，使其發(fā)揮各自的優(yōu)勢，使融合后的算法具有更加廣泛的適用性。

神經(jīng)網(wǎng)絡(luò)的優(yōu)點在于它的算法具有學(xué)習(xí)能力，能夠在訓(xùn)練過程中通過每一輪迭代后的輸出誤差優(yōu)化神經(jīng)網(wǎng)絡(luò)中的參數(shù)，使神經(jīng)網(wǎng)絡(luò)對各個指標(biāo)的融合效果達(dá)到最佳。但在實驗中注意到，把不同的相似性指標(biāo)作為節(jié)點之間有無連邊的分類屬性，本身就具有很大的相關(guān)性，這就使在訓(xùn)練神經(jīng)網(wǎng)絡(luò)時很容易出現(xiàn)過擬合。在實驗中，對同一個網(wǎng)絡(luò)進(jìn)行多次計算，得出的計算結(jié)果時好時壞，偏差較大，計算結(jié)果很不穩(wěn)定。本文使用粒子群算法對神經(jīng)網(wǎng)絡(luò)初始參數(shù)進(jìn)行優(yōu)化，防止過擬合現(xiàn)象出現(xiàn)。通過對神經(jīng)網(wǎng)絡(luò)的初始參數(shù)進(jìn)行優(yōu)化后，計算結(jié)果具有很好的收斂性，使算法在多次計算的結(jié)果能夠穩(wěn)定一致。

表1 靜態(tài)網(wǎng)絡(luò)數(shù)據(jù)集拓?fù)涮卣鲄?shù)

網(wǎng)絡(luò)|V||E|CrH NS146127423.755.820.8780.4611.85 PB12221671727.362.510.360?0.2212.970 Jazz198274227.72.240.6330.021.4 CE45320258.942.660.655?0.2254.49 USAir332212812.812.740.749?0.2083.36 Yeast2 37010 9049.25.160.3780.4693.35

實驗中發(fā)現(xiàn)，數(shù)量過大的訓(xùn)練集并不能夠有效提高實驗算法的預(yù)測效果，反而會降低算法的時間復(fù)雜度，并且引起過擬合。通過大量實驗總結(jié)認(rèn)為，在確定訓(xùn)練集的時候，選擇從連邊集合中隨機抽取10%的連邊數(shù)目，再從未連邊的節(jié)點對集合中隨機抽取同樣數(shù)量的節(jié)點對，組成訓(xùn)練集，既能夠達(dá)到良好的預(yù)測精確度，又能降低算法的時間復(fù)雜度，提高運算效率。

4.4 算法有效性驗證

本文使用NNLP算法對CN、AA、PA、Katz 這4種相似性指標(biāo)進(jìn)行融合實驗，計算6種真實網(wǎng)絡(luò)數(shù)據(jù)集中未連接節(jié)點對的連邊可能性值。本節(jié)使用AUC值精確衡量各個算法的預(yù)測精度。在每種數(shù)據(jù)集上分別單獨計算10次，每次計算前重新劃分訓(xùn)練集和測試集，隨機從訓(xùn)練集中抽取節(jié)點對組成神經(jīng)網(wǎng)絡(luò)的訓(xùn)練集，取10次計算的平均值作為未連邊節(jié)點對的數(shù)值，可以得到各個算法在6種不同數(shù)據(jù)集中的AUC值，如表2所示，每個數(shù)據(jù)集中最優(yōu)值用粗體標(biāo)出，Katz指標(biāo)的參數(shù)固定為0.01。

如表2所示，本文中提出的NNLP算法在6種真實網(wǎng)絡(luò)數(shù)據(jù)集中的表現(xiàn)都優(yōu)于其他指標(biāo)。這6種真實網(wǎng)絡(luò)來自不同的領(lǐng)域，具有不同的網(wǎng)絡(luò)拓?fù)涮卣?，因此說明NNLP算法在不同種類的網(wǎng)絡(luò)中可以有比較好的表現(xiàn)，NNLP算法可以有效提高結(jié)構(gòu)相似性指標(biāo)的頑健性。

表3中數(shù)據(jù)與表2中結(jié)果一致，在精確度指標(biāo)中，NNLP算法依然表現(xiàn)最佳。

表2 NNLP算法和各結(jié)構(gòu)相似性指標(biāo)在數(shù)據(jù)集中的AUC值

表3 NNLP算法和各結(jié)構(gòu)相似性指標(biāo)在數(shù)據(jù)集中的precision值

通過分析NNLP算法和4種結(jié)構(gòu)相似性指標(biāo)可以發(fā)現(xiàn)，4種指標(biāo)是基于不同的連邊機理提出的，因此，它們在不同的網(wǎng)絡(luò)中表現(xiàn)不同。例如，PA指標(biāo)在Jazz網(wǎng)絡(luò)中表現(xiàn)優(yōu)秀，而在NS網(wǎng)絡(luò)中變現(xiàn)非常一般；Katz指標(biāo)雖然考慮了全局路徑信息，但在所有網(wǎng)絡(luò)中的表現(xiàn)也不是最好，它在USAir網(wǎng)絡(luò)中的表現(xiàn)與AA指標(biāo)有一定差距；而NNLP算法合理融合了4種指標(biāo)，因此在所有網(wǎng)絡(luò)中都有比較好的表現(xiàn)。值得注意的是，NNLP算法提供的是一種融合指標(biāo)框架，它也可以用于融合其他的相似性指標(biāo)以獲得更好的表現(xiàn)，本章不再選取其他指標(biāo)進(jìn)行比較。

融合各種結(jié)構(gòu)相似性指標(biāo)的研究仍處于起步階段，相關(guān)文獻(xiàn)還比較少；本文選擇與He等[18]提出的一種基于OWA算子的鏈路預(yù)測算法進(jìn)行對比，稱為LPEOWA算法，該算法采用MEM（maximum entropy method）、MVM（minimum variance method）和CSM（chi-square method）3種OWA算子分別給9種基于局部信息的結(jié)構(gòu)相似性指標(biāo)賦予融合權(quán)重。在WSDP98、ChesLower、C96和B97這4個真實社會網(wǎng)絡(luò)上的實驗表明，該算法能在一定程度上提高結(jié)構(gòu)相似性指標(biāo)的預(yù)測精度和頑健性；其中，與MVM算子和CSM算子相比，基于MEM算子的LPEOWA算法在大部分?jǐn)?shù)據(jù)集中可以取得更高的預(yù)測精度?；谏鲜龇治?，本章采用MEM算子對CN、AA、PA和Katz這4種結(jié)構(gòu)相似性指標(biāo)進(jìn)行融合，并在6種真實網(wǎng)絡(luò)數(shù)據(jù)集上與NNLP算法進(jìn)行對比。

如表4所示，在6個真實網(wǎng)絡(luò)數(shù)據(jù)集中，LPEOWA算法和NNLP算法的預(yù)測精度都優(yōu)于單個結(jié)構(gòu)相似性指標(biāo)，而NNLP算法的預(yù)測精度又都高于LPEOWA算法。在許多數(shù)據(jù)集中，LPEOWA算法的預(yù)測精度與表現(xiàn)最優(yōu)的單個指標(biāo)接近，說明LPEOWA算法對預(yù)測精度的提升能力有限。在Jazz網(wǎng)絡(luò)和PB網(wǎng)絡(luò)中，NNLP算法和LPEOWA算法的表現(xiàn)接近，但在NS、USAir、CE和Yeast網(wǎng)絡(luò)中，NNLP算法明顯優(yōu)于LPEOWA算法，這是因為OWA算子在融合各結(jié)構(gòu)相似性指標(biāo)時，只考慮到了各指標(biāo)分?jǐn)?shù)值在大小順序上的重要性，并沒有考慮到各指標(biāo)之間存在的交互作用。

4.5 融合局部相似性指標(biāo)后與全局指標(biāo)的比較

在本文選取的4種結(jié)構(gòu)相似性指標(biāo)中，CN、PA、AA屬于局部結(jié)構(gòu)相似性指標(biāo)，Katz指標(biāo)屬于全局結(jié)構(gòu)相似性指標(biāo)。前3種指標(biāo)時間復(fù)雜度較低，但預(yù)測精度一般沒有全局指標(biāo)高，Katz指標(biāo)的精度一般較高，但時間復(fù)雜度也較高。如表4所示，Katz指標(biāo)在NS、PB、Yeast等大多數(shù)網(wǎng)絡(luò)中的表現(xiàn)要優(yōu)于其他3種只考慮了局部信息的結(jié)構(gòu)相似性指標(biāo)，甚至在很多網(wǎng)絡(luò)中的表現(xiàn)與NNLP算法接近。從表4中也可以看出，在許多數(shù)據(jù)集中，Katz指標(biāo)的模糊密度大于其他3種局部結(jié)構(gòu)相似性指標(biāo)，說明考慮了全局信息的Katz指標(biāo)在融合中發(fā)揮了重要作用?；谏鲜龇治觯疚闹胁捎蒙窠?jīng)網(wǎng)絡(luò)來融合局部相似性指標(biāo)，比較其與Katz指標(biāo)的優(yōu)劣。將融合了3種局部結(jié)構(gòu)相似性指標(biāo)的算法稱為NNLP3算法，表5列出了Katz指標(biāo)、NNLP3算法和NNLP算法的AUC值。

表4 NNLP算法、LPEOWA算法和各指標(biāo)在數(shù)據(jù)集中的AUC值

算法AUC值 NSPBUsAirCEJazzYeast CN0.969 10.919 10.950 70.829 70.952 50.909 8 PA0.737 60.911 60.918 30.752 80.766 50.866 4 AA0.969 60.922 40.956 70.845 80.946 40.911 2 Katz0.980 80.930 40.950 90.855 60.938 70.970 6 LPEOWA0.981 90.941 70.966 70.867 90.960 80.972 9 NNLP0.999 80.945 30.980 70.902 40.975 30.981 4

從表5可以看出，NNLP算法在除Jazz網(wǎng)絡(luò)外的其他5個真實網(wǎng)絡(luò)數(shù)據(jù)集中的表現(xiàn)優(yōu)于Katz指標(biāo)和NNLP3算法，在表6中，NNLP算法在6個真實網(wǎng)絡(luò)數(shù)據(jù)集中表現(xiàn)均優(yōu)于Katz指標(biāo)和NNLP3算法，在大多數(shù)網(wǎng)絡(luò)中，NNLP3算法也優(yōu)于考慮了全局信息的Katz指標(biāo)。但在PB和Yeast網(wǎng)絡(luò)中，Katz指標(biāo)要優(yōu)于NNLP3算法，這是因為CN、PA、AA指標(biāo)在PB和Yeast網(wǎng)絡(luò)中的表現(xiàn)明顯低于Katz指標(biāo)，使神經(jīng)網(wǎng)絡(luò)在對3種局部結(jié)構(gòu)相似性指標(biāo)進(jìn)行融合后預(yù)測精度有所提升，但提升效果受到這3種指標(biāo)預(yù)測精度的限制。在NS指標(biāo)中，CN、PA、AA指標(biāo)也與Katz指標(biāo)有較大的差距，但融合后的預(yù)測效果卻好于Katz指標(biāo)，說明CN、PA、AA指標(biāo)在NS網(wǎng)絡(luò)的預(yù)測計算中，相互之間具有更加良好的互補性，而在PB和Yeast網(wǎng)絡(luò)中互補性不夠明顯。在Jazz網(wǎng)絡(luò)中，NNLP3算法的結(jié)果要優(yōu)于NNLP算法，說明融合相似性指標(biāo)的方法，并不是選擇的指標(biāo)越多，效果越好。

表5 Katz指標(biāo)、NNLP3算法和NNLP算法在數(shù)據(jù)集中的AUC值

算法AUC值 NSPBUSAirCEJazzYeast Katz0.980 00.932 90.947 20.859 70.942 80.974 1 NNLP30.988 00.929 80.978 50.870 70.977 80.919 0 NNLP0.999 80.945 30.980 70.902 40.975 30.981 2

算法precision值 NSPBUSAirCEJazzYeast Katz0.4780.1770.3810.1050.4460.256 NNLP30.5110.1380.3890.1090.5310.143 NNLP0.5160.1850.4130.1340.5430.266

5 結(jié)束語

本文提出的NNLP算法通過神經(jīng)網(wǎng)絡(luò)對不同鏈路預(yù)測指標(biāo)進(jìn)行了融合，主要利用指標(biāo)在預(yù)測結(jié)果上的互補性，提高了鏈路預(yù)測的精度，同時兼顧了算法的時間復(fù)雜度。NNLP算法在計算中針對不同的網(wǎng)絡(luò)數(shù)據(jù)訓(xùn)練神經(jīng)網(wǎng)絡(luò)參數(shù)，然后計算融合指標(biāo)，針對不同的網(wǎng)絡(luò)具有較強的適應(yīng)性。通過本文的算法推導(dǎo)以及實驗，驗證了融合算法能夠提升鏈路預(yù)測的精度，同時也發(fā)現(xiàn)，融合指標(biāo)并不是越多越好。下一步研究主要關(guān)注2方面問題：1) 融合方法中如何確定融合指標(biāo)的種類和數(shù)量；2) 通過探討各個算法之間的互補性，進(jìn)一步分析網(wǎng)絡(luò)特性，并探索新的算法。

[1] Lü L, ZHOU T. Link prediction in complex networks: a survey[J]. Physica a: Statistical Mechanics and its Applications, 2011, 390(6): 1150-1170.

[2] CANNISTRACI C V, ALANISLOBATO G, RAVASI T. From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks[J]. Scientific Reports, 2015 ,3 (4): 1613-1613.

[3] KOSSINETS G. Effects of missing data in social network[J]. Social Networks, 2006 , 28 (3): 247-268.

[4] ESSLIMAMI I, BRUN A, BOYER A. Densifying a behavioral recommender system by social networks link prediction methods[J].Social Network Analysis and Mining, 2011,1(3): 159-172.

[5] 劉樹新, 季新生, 劉彩霞, 等. 一種信息傳播促進(jìn)網(wǎng)絡(luò)增長的網(wǎng)絡(luò)演化模型[J]. 物理學(xué)報, 2014, 63(15).LIU S X, JI X S, LIU C X, et al. A complex network evolution model for network growth promoted by information transmission[J]. Acta Physica Sinica, 2014, 63(15).

[6] 劉樹新, 季新生, 劉彩霞, 等. 局部拓?fù)湫畔Ⅰ詈洗龠M(jìn)網(wǎng)絡(luò)演化[J]. 電子與信息學(xué)報, 2016, 38 (9): 2180-2187.LIU S X, JI X S, LIU C X, et al. Information coupling of local topology promoting the network evolution [J]. Journal of Electronics & Information Technology, 2016, 38(9): 2180-2187.

[7] ZHOU C, MOTTER A E, KURTHS J. Universality in the synchronization of weighted random networks[J]. Physical Review Letters, 2006, 96 (3): 034101.

[8] FIRTUNATO S. Community detection in graph[J].Physics Reports, 2010, 486 (3): 75-174.

[9] 黃立威, 李德毅, 馬于濤, 等. 一種基于元路徑的異質(zhì)信息網(wǎng)絡(luò)鏈路預(yù)測模型[J].計算機學(xué)報, 2014, 37 (4): 848-858.HUANG L W, LI D Y, MA Y T, et al. A meta path-based link prediction model for heterogeneous information networks[J]. Chinese Journal of Computers 2014 ,37 (4): 848-858.

[10] 王守輝, 于洪濤, 黃瑞陽, 等. 基于模體演化的時序鏈路預(yù)測方法[J]. 自動化學(xué)報, 2016, 42 (5): 735-745.WANG S H, YU H T, HUANG R Y, et al. A temporal link prediction method based on motifevolution[J]. Acta Automatica Sinica, 2016 ,42 (5): 735-745.

[11] MITZENMACHER M. A brief history of generative models for power law and lognormal distributions[J]. Internet Mathematics, 2004, 1 (2): 226-251.

[12] ADAMIC L A, Adar E. Friends and neighbors on the Web[J].Social Networks, 2003, 25 (3): 211-230.

[13] OU Q, JIN Y D, ZHOU T, et al. Power-law strength-degree correlation from resource-allocation dynamics on weighted networks[J]. Physical Review E, 2007, 75 (2).

[14] BARABáSI A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286 (5439): 509-512.

[15] LIU S, JI X, LIU C, et al. Extended resource allocation index for link prediction of complex network[J]. Physica a Statistical Mechanics & its Applications, 2017, 479 : 174-183.

[16] KATZ L. A new status index derived from sociometric index[J]. Psychometrika, 1953, 18 (1): 39-43.

[17] LIU S, JI X, LIU C, et al. Similarity indices based on link weight assignment for link prediction of unweighted complex networks[J]. International Journal of Modern Physics B, 2017, 31 (2): 412-1054.

[18] HE Y, LIU J N K, HU Y, et al. OWA operator based link prediction ensemble for social network[J]. Expert Systems with Applications, 2015, 42 (1): 21-50.

[19] GAO F, MUSIAL K, COOPER C, et al. Link prediction methods and their accuracy for different social networks and network metrics[J]. Scientific Programming, 2014, 501: 172879.

[20] 吳祖峰, 梁棋, 劉嶠, 等. 基于AdaBoost的鏈路預(yù)測優(yōu)化算法[J]. 通信學(xué)報, 2014, 35 (3): 116-123.WU Z F, LIANG Q, LIU Q, et al. Modified link prediction algorithm based on AdaBoost [J]. Journal on Communications, 2014 , 35(3): 116-123.

[21] YU H T, WANG S H, MA Q Q. Link prediction algorithm based on the Choquet fuzzy integral[J]. Journal on Communications, 2016, 20 (4): 809-824.

[22] 呂琳媛, 周濤. 鏈路預(yù)測[M]. 北京: 高等教育出版社, 2013: 46-47.LYU L Y, ZHOU T. Link prediction[M]. Beijing: High Education Press, 2013.

[23] BRITS R, ENGELBRECHT A P, et al. A niching particle swarm optimizer[C]//The 4th Asia-Pacific conference on simulated evolution and learning, Singapore, 2002, 692-696.

[24] HECHT-NIELSEN R. Theory of the backpropagation neural network[C]//International Joint Conference on Neural Networks, 1989, 1(1): 593-605.

Neural network-based link prediction algorithm

PAN Yonghao, YU Hongtao, LIU Shuxin

National Digital Switching System Engineering and Technological R&D Center, Zhengzhou 450002, China

To improve the difference existed in the link prediction accuracy and adaptability of different topology structure similarity based methods, a neural network-based link prediction algorithm, which fused similarity indices by neural network was proposed. The algorithm uses neural network to study the numerical characteristics of different similarity indices, and uses particle swarm optimization to optimize the neural network, and calculates the fusion index by the optimized neural network model. The experiment on the real network data set shows that the prediction accuracy of the algorithm is obviously higher than that before the fusion, and the accuracy is better than the existing methods.

complex network, link prediction, neural network, back propagation algorithm

TN94; TP3; TP391

A

10.11959/j.issn.2096-109x.2018049

潘永昊（1992-），男，甘肅金昌人，國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心碩士生，主要研究方向為復(fù)雜網(wǎng)絡(luò)、鏈路預(yù)測。

于洪濤（1970-），男，遼寧丹東人，博士，國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心研究員，主要研究方向為網(wǎng)絡(luò)大數(shù)據(jù)分析與處理。

劉樹新（1987-），男，山東濰坊人，博士，國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心助理研究員，主要研究方向為復(fù)雜網(wǎng)絡(luò)、網(wǎng)絡(luò)信息挖掘。

2018-05-07；

2018-06-01

潘永昊，panyonghao2016@163.com

國家自然科學(xué)基金創(chuàng)新研究群體基金資助項目（No.61521003），國家自然科學(xué)基金資助項目（No.61601513）

The Innovative Research Groups of the National Natural Science Foundation of China (No.61521003), The National Natural Science Foundation of China (No.61601513)