傅馨玉，顧益軍

中國(guó)人民公安大學(xué) 信息網(wǎng)絡(luò)安全學(xué)院，北京 102600

鏈路預(yù)測(cè)是研究復(fù)雜網(wǎng)絡(luò)[1]的核心內(nèi)容之一，在生物研究[2]、電子商務(wù)[3]、合作推薦[4]、社會(huì)安全[5]等眾多領(lǐng)域得到廣泛的實(shí)際應(yīng)用。在復(fù)雜網(wǎng)絡(luò)中，將個(gè)體稱(chēng)為節(jié)點(diǎn)，節(jié)點(diǎn)間的關(guān)系稱(chēng)為連接。鏈路預(yù)測(cè)，即根據(jù)網(wǎng)絡(luò)中的已知節(jié)點(diǎn)以及節(jié)點(diǎn)間的連接情況等信息，預(yù)測(cè)該網(wǎng)絡(luò)中任意兩個(gè)未連接節(jié)點(diǎn)之間可能會(huì)產(chǎn)生新連接的概率[6]。近年來(lái)，隨著機(jī)器學(xué)習(xí)、深度學(xué)習(xí)的不斷發(fā)展，一些有監(jiān)督式鏈路預(yù)測(cè)方法[7]成為研究熱點(diǎn)，通過(guò)定義損失函數(shù)訓(xùn)練模型或者利用先驗(yàn)知識(shí)來(lái)進(jìn)行鏈路預(yù)測(cè)，學(xué)習(xí)訓(xùn)練的過(guò)程通常需要大量的時(shí)間成本?，F(xiàn)實(shí)世界中網(wǎng)絡(luò)數(shù)據(jù)集多為“小世界”[8]模型下的加權(quán)復(fù)雜網(wǎng)絡(luò)，對(duì)于一些小規(guī)模、需要快速預(yù)測(cè)的網(wǎng)絡(luò)，往往不需要采用有監(jiān)督式鏈路預(yù)測(cè)方法，消耗大量的訓(xùn)練時(shí)間，并且小規(guī)模數(shù)據(jù)集下訓(xùn)練的效果較差。反而一些無(wú)監(jiān)督式鏈路預(yù)測(cè)方法，在保證預(yù)測(cè)精確度的同時(shí)，可以高效快速輸出預(yù)測(cè)結(jié)果，更適用于解決此類(lèi)加權(quán)網(wǎng)絡(luò)鏈路預(yù)測(cè)問(wèn)題。無(wú)監(jiān)督式鏈路預(yù)測(cè)方法可以分為基于似然分析的預(yù)測(cè)方法[9]和基于相似性[10]的預(yù)測(cè)方法。基于似然分析的預(yù)測(cè)方法需要不斷更新樣本，時(shí)間復(fù)雜度較高，不具備普遍適用性。常用的基于相似性的預(yù)測(cè)方法，計(jì)算信息容易獲取，算法復(fù)雜度低，并根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)信息量的多少，可以劃分為基于局部網(wǎng)絡(luò)結(jié)構(gòu)和基于全局網(wǎng)絡(luò)結(jié)構(gòu)的預(yù)測(cè)指標(biāo)。在真實(shí)加權(quán)網(wǎng)絡(luò)數(shù)據(jù)集中，存儲(chǔ)、計(jì)算權(quán)重信息和路徑信息會(huì)增加算法的時(shí)間復(fù)雜度，因此在一些小規(guī)模、需要及時(shí)解決的事件預(yù)測(cè)問(wèn)題上，基于局部網(wǎng)絡(luò)結(jié)構(gòu)的無(wú)監(jiān)督預(yù)測(cè)方法更為適用。

然而，這類(lèi)方法通常僅考慮節(jié)點(diǎn)度[11]、共同鄰居[12]、邊權(quán)值[13]、路徑[14]等信息，忽略了節(jié)點(diǎn)自身重要性對(duì)新連接產(chǎn)生的影響。“中心性”常用來(lái)刻畫(huà)網(wǎng)絡(luò)中節(jié)點(diǎn)的重要程度，應(yīng)用到無(wú)權(quán)網(wǎng)絡(luò)的相關(guān)研究上[15-16]。在真實(shí)加權(quán)網(wǎng)絡(luò)上，受到親近關(guān)系、傳播阻塞等現(xiàn)實(shí)因素影響，會(huì)出現(xiàn)低中心性節(jié)點(diǎn)同樣具有高重要性的情況，對(duì)鏈路預(yù)測(cè)結(jié)果產(chǎn)生一定影響。

針對(duì)上述問(wèn)題，將無(wú)權(quán)網(wǎng)絡(luò)上節(jié)點(diǎn)重要性的研究更多地延展到加權(quán)網(wǎng)絡(luò)上，分析節(jié)點(diǎn)重要性影響連接產(chǎn)生的方式以及不同中心性下的影響差異，并應(yīng)用到加權(quán)網(wǎng)絡(luò)鏈路預(yù)測(cè)方法中。本文的主要貢獻(xiàn)包括：（1）證明了在現(xiàn)實(shí)加權(quán)網(wǎng)絡(luò)中，中心性小的節(jié)點(diǎn)反而越重要，產(chǎn)生新連接的可能性越大，節(jié)點(diǎn)重要性在鏈路預(yù)測(cè)問(wèn)題研究中起到重要作用；（2）提出一種融合節(jié)點(diǎn)重要性的無(wú)監(jiān)督鏈路預(yù)測(cè)算法FNI（unsupervised link prediction algorithm fusing node importance），相比同類(lèi)基于局部網(wǎng)絡(luò)結(jié)構(gòu)的無(wú)監(jiān)督預(yù)測(cè)方法提高了精確度；（3）對(duì)比圖嵌入等有監(jiān)督式鏈路預(yù)測(cè)方法，無(wú)監(jiān)督的FNI算法能夠更加準(zhǔn)確地解決現(xiàn)實(shí)里小規(guī)模加權(quán)數(shù)據(jù)集上的快速預(yù)測(cè)問(wèn)題。

1 加權(quán)網(wǎng)絡(luò)鏈路預(yù)測(cè)相關(guān)研究

當(dāng)前加權(quán)網(wǎng)絡(luò)鏈路預(yù)測(cè)相關(guān)研究方法相比無(wú)權(quán)網(wǎng)絡(luò)較少，可以分為有監(jiān)督式和無(wú)監(jiān)督式鏈路預(yù)測(cè)方法。

1.1 有監(jiān)督式鏈路預(yù)測(cè)方法

機(jī)器學(xué)習(xí)、深度學(xué)習(xí)領(lǐng)域不斷提出各種有監(jiān)督式方法用于解決鏈路預(yù)測(cè)問(wèn)題，最為常用的就是圖嵌入方法，主要包括基于矩陣分解、隨機(jī)游走和深度學(xué)習(xí)的圖嵌入方法。Ou 等人[17]針對(duì)有向圖中的非對(duì)稱(chēng)傳遞性，將嵌入分為源嵌入和目標(biāo)嵌入，提出基于矩陣分解的HOPE（high-order proximity preserved embedding）算法；Grover等人[18]通過(guò)調(diào)整深度優(yōu)先搜索和廣度優(yōu)先搜索策略的參數(shù)，用Skip-Gram模型對(duì)生成的游走序列進(jìn)行嵌入，提出基于隨機(jī)游走的Node2vec 方法；Wang 等人[19]提出基于深度學(xué)習(xí)的SDNE（structural deep network embedding）方法，保持一階和二階相似性，利用高度的非線性函數(shù)和優(yōu)化目標(biāo)函數(shù)生成嵌入向量。這些方法通過(guò)大量的迭代輪數(shù)，最小化各自定義的損失函數(shù)，得到最佳的嵌入向量表示，計(jì)算節(jié)點(diǎn)向量間的相似性輸出預(yù)測(cè)結(jié)果。然而，監(jiān)督訓(xùn)練過(guò)程往往需要大量的時(shí)間，且存在訓(xùn)練結(jié)果較差的可能，在小規(guī)模加權(quán)網(wǎng)絡(luò)上并不具備訓(xùn)練的必要性，時(shí)間成本投入和預(yù)測(cè)結(jié)果收益不成正比。

1.2 無(wú)監(jiān)督式鏈路預(yù)測(cè)方法

基于似然分析的預(yù)測(cè)方法通常適用于規(guī)模龐大的網(wǎng)絡(luò)，在加權(quán)網(wǎng)絡(luò)上邊的存在性可以用泊松的似然程度來(lái)表示。具有代表性的是泊松隨機(jī)分塊模型、度修正的泊松隨機(jī)分塊模型以及非負(fù)矩陣因子分解模型。這類(lèi)算法的時(shí)間復(fù)雜度較高，且不適用于小規(guī)模網(wǎng)絡(luò)的連邊預(yù)測(cè)。

基于局部網(wǎng)絡(luò)結(jié)構(gòu)的預(yù)測(cè)方法主要可以分為基于局部信息、路徑信息以及局部與路徑相結(jié)合的三類(lèi)指標(biāo)。在基于局部信息的預(yù)測(cè)指標(biāo)中，Lv等人[20]將經(jīng)典相似性指標(biāo)拓展到加權(quán)網(wǎng)絡(luò)上，提出了WCN（weighted common neighbors）、WAA（weighted Adamic-Adar）、WRA（weighted resource allocation）三種經(jīng)典指標(biāo)。在共同鄰居的基礎(chǔ)上考慮兩端節(jié)點(diǎn)度的影響，WCN 指標(biāo)從不同角度衍生出WSalton、WS?rensen、WHPI（weighted hub promoted index）、WHDI（weighted hub depressed index）、WLHN-I 五種加權(quán)指標(biāo)。這一類(lèi)指標(biāo)很好地結(jié)合了節(jié)點(diǎn)強(qiáng)度和權(quán)重值，計(jì)算復(fù)雜度低，但計(jì)算方式僅限于存在共同鄰居的兩階路徑下，高階相似性并沒(méi)有得到充分計(jì)算。

基于路徑的預(yù)測(cè)指標(biāo)可以寫(xiě)成統(tǒng)一的形式：

其中，Sxy表示節(jié)點(diǎn)相似性，α表示可調(diào)參數(shù)，A為含權(quán)鄰接矩陣。區(qū)別在于路徑的步長(zhǎng)限制不同，最為常用的是加權(quán)局部路徑指標(biāo)WLP（weighted local path），其將路徑步長(zhǎng)限制在三步之內(nèi)。這一類(lèi)指標(biāo)從路徑的角度出發(fā)，全面考慮多路徑、高階路徑對(duì)節(jié)點(diǎn)相似性的貢獻(xiàn)，反而忽略了節(jié)點(diǎn)自身屬性在鏈路預(yù)測(cè)問(wèn)題中的重要作用。

綜合上述兩類(lèi)指標(biāo)各自的優(yōu)缺點(diǎn)，學(xué)者們不斷提出局部與路徑信息相結(jié)合的指標(biāo)。Zhao 等人[21]通過(guò)路徑權(quán)重的乘積衡量該路徑對(duì)節(jié)點(diǎn)間相似性的貢獻(xiàn)程度，定義可信路徑加權(quán)指標(biāo)rWCN（reliable-route WCN）、rWAA（reliable-route WAA）和rWRA（reliable-route WRA）。Bai等人[22]提出了節(jié)點(diǎn)與路徑相結(jié)合的半局部預(yù)測(cè)指標(biāo)WRALP（weighted resource allocation along local path）。劉苗苗等人[23]定義邊權(quán)強(qiáng)度、路徑相似性貢獻(xiàn)，并限制路徑長(zhǎng)度來(lái)計(jì)算相似性得分，提出了基于多路徑節(jié)點(diǎn)相似性的預(yù)測(cè)指標(biāo)STNMP（similarity based on transmission nodes of multi-path）。白楊等人[24]提出了將可靠路徑與WRALP相結(jié)合的預(yù)測(cè)指標(biāo)PWRALP（product-WRALP）。雖然這一類(lèi)預(yù)測(cè)指標(biāo)，相比前兩類(lèi)指標(biāo)具有更高的預(yù)測(cè)精確度，但僅憑相似程度來(lái)判斷節(jié)點(diǎn)間建立新連接的可能性，忽略了節(jié)點(diǎn)重要性作為節(jié)點(diǎn)的重要屬性之一，同樣會(huì)影響新連接產(chǎn)生的可能性。

2 FNI算法

2.1 節(jié)點(diǎn)重要性對(duì)連接產(chǎn)生的影響

真實(shí)網(wǎng)絡(luò)中，新連接的產(chǎn)生具有一定的隨機(jī)性，并非任意產(chǎn)生。鏈路預(yù)測(cè)是在遵循概率分布的基礎(chǔ)上，區(qū)分不同連接產(chǎn)生的可能性，從而給出預(yù)測(cè)結(jié)果。節(jié)點(diǎn)重要性則會(huì)在一定程度上影響到這種可能性，原因在于一些親密關(guān)系強(qiáng)、傳播信息快的重要節(jié)點(diǎn)，往往更容易與其他節(jié)點(diǎn)建立通話接觸、信息傳遞、合作互利等不同現(xiàn)實(shí)意義上的關(guān)系，增強(qiáng)了該節(jié)點(diǎn)產(chǎn)生新連接的可能性，促使網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生變化。尤其是在當(dāng)尚未連接的節(jié)點(diǎn)對(duì)間根據(jù)相似性計(jì)算的連接可能性相同時(shí)，重要性高的節(jié)點(diǎn)更有可能產(chǎn)生新連接。根據(jù)節(jié)點(diǎn)的度數(shù)大小、對(duì)網(wǎng)絡(luò)連通性的貢獻(xiàn)作用、在網(wǎng)絡(luò)結(jié)構(gòu)中的位置以及鄰居節(jié)點(diǎn)的重要程度等定義的中心性，均可以用來(lái)評(píng)估該節(jié)點(diǎn)的重要性。在一些傳播網(wǎng)絡(luò)中普遍認(rèn)為，一個(gè)新加入的節(jié)點(diǎn)更容易選擇網(wǎng)絡(luò)中已有的大度節(jié)點(diǎn)建立單向行為的新連接，例如微博新用戶在注冊(cè)后會(huì)單方面關(guān)注明星博主。然而在現(xiàn)實(shí)網(wǎng)絡(luò)中，更多的是在已有網(wǎng)絡(luò)結(jié)構(gòu)信息下，解決現(xiàn)存節(jié)點(diǎn)間產(chǎn)生新連接的預(yù)測(cè)問(wèn)題，這種連接主要表示合作、溝通等雙向行為，會(huì)受到親密關(guān)系、傳播阻塞等因素的影響。因此，一些中心性高的節(jié)點(diǎn)由于連接關(guān)系較為固定，不易產(chǎn)生新連接，反而是中心性低的節(jié)點(diǎn)間更容易拓展新的雙向行為關(guān)系，在判斷新連接產(chǎn)生時(shí)其節(jié)點(diǎn)重要性更高。

例如圖1所示，A、B節(jié)點(diǎn)和A、C節(jié)點(diǎn)在相似性指標(biāo)計(jì)算下的連接可能性相同，然而在現(xiàn)實(shí)情境下，節(jié)點(diǎn)重要性會(huì)從不同角度改變兩個(gè)節(jié)點(diǎn)對(duì)間產(chǎn)生新連接的可能性。圖1（a）表示微博關(guān)注關(guān)系網(wǎng)絡(luò)時(shí)，C節(jié)點(diǎn)的度中心性小于B節(jié)點(diǎn)，由于A更容易去關(guān)注朋友的親密朋友C，而不是朋友所關(guān)注的流量明星B，因此C節(jié)點(diǎn)對(duì)于A節(jié)點(diǎn)而言更重要，產(chǎn)生新連接可能性更大。圖1（b）表示科學(xué)合作網(wǎng)絡(luò)時(shí)，核心成員B的合作關(guān)系較為固定，產(chǎn)生新連接的可能性較小，反而是C節(jié)點(diǎn)的介數(shù)中心性更低，對(duì)同為外層成員的A而言，是建立新合作的重要伙伴，使得網(wǎng)絡(luò)進(jìn)一步擴(kuò)大其連通范圍。圖1（c）表示機(jī)場(chǎng)航班網(wǎng)絡(luò)時(shí)，B節(jié)點(diǎn)屬于中轉(zhuǎn)樞紐，當(dāng)負(fù)載量達(dá)到一定程度時(shí)，與小機(jī)場(chǎng)A開(kāi)通新航班的可能性不高，而C節(jié)點(diǎn)接近中心性較低，即使處于網(wǎng)絡(luò)邊緣，在新航線的備選名單中地位也格外重要。圖1（d）表示涉密信息傳播網(wǎng)絡(luò)時(shí)，實(shí)心節(jié)點(diǎn)表示影響力較大的信息傳播點(diǎn)，當(dāng)A節(jié)點(diǎn)傳播私密信息時(shí)，更可能會(huì)選擇特征向量中心性小的C節(jié)點(diǎn)，認(rèn)可其在信息傳遞過(guò)程中的重要性。

圖1 4個(gè)簡(jiǎn)單加權(quán)網(wǎng)絡(luò)示例圖Fig.1 4 simple weighted network sample diagrams

綜上所述，新連接的產(chǎn)生沒(méi)有遵循可限定概率分布，利用結(jié)構(gòu)相似性計(jì)算新連接可能性這一方式并不嚴(yán)謹(jǐn)，節(jié)點(diǎn)重要性正是通過(guò)改變這種可能性來(lái)影響連接的產(chǎn)生，且中心性小的節(jié)點(diǎn)可能更為重要。因此，F(xiàn)NI 算法從結(jié)構(gòu)相似性和節(jié)點(diǎn)重要性兩個(gè)角度出發(fā)，更加準(zhǔn)確地計(jì)算新連接產(chǎn)生的可能性，按照可能性從高到低排序作為預(yù)測(cè)結(jié)果。

2.2 不同中心性對(duì)連接產(chǎn)生的影響差異

節(jié)點(diǎn)重要性可以影響連接產(chǎn)生的可能性，但是從不同角度衡量節(jié)點(diǎn)重要性時(shí)，影響程度也會(huì)有差異。以常用的度中心性（degree centrality，DC）、介數(shù)中心性（betweenness centrality，BC）、接近中心性（closeness centrality，CC）、特征向量中心性（eigenvector centrality，EC）為代表，在10 個(gè)經(jīng)過(guò)無(wú)向加權(quán)處理后的數(shù)據(jù)集上，綜合分析不同中心性對(duì)連接產(chǎn)生的影響差異。分別計(jì)算平均節(jié)點(diǎn)中心性值cˉ和平均連接中心性值-cl，二者的差值Δc可以量化表示出中心性對(duì)連接的影響程度，Δc ＞0 則說(shuō)明中心性對(duì)新連接的產(chǎn)生具有一定影響，具體計(jì)算方式為：

其中，kx表示節(jié)點(diǎn)度，E為邊集合，| |E為連邊數(shù)，V為節(jié)點(diǎn)集合，| |V為節(jié)點(diǎn)數(shù)。Δc越大說(shuō)明該中心性對(duì)連接產(chǎn)生的影響越大，Δc值較小即表示對(duì)連接產(chǎn)生的影響不夠明顯。表1 展示了各數(shù)據(jù)集在不同中心性下的Δc值，括號(hào)內(nèi)序號(hào)表示同一數(shù)據(jù)集上Δc值由大到小的排序。

表1 各數(shù)據(jù)集上不同中心性的Δc 值Table 1 Δc values of different centrality on datasets

分析表1 可知，由于網(wǎng)絡(luò)數(shù)據(jù)集的拓?fù)浣Y(jié)構(gòu)差異，不同中心性對(duì)連接產(chǎn)生的影響差異較大。具體表現(xiàn)為DC在70%的數(shù)據(jù)集上Δc值同比最高，對(duì)連接產(chǎn)生的影響最為明顯。根據(jù)度中心性的大小來(lái)衡量節(jié)點(diǎn)重要性，可以有效區(qū)分各連接產(chǎn)生的可能性，對(duì)鏈路預(yù)測(cè)結(jié)果產(chǎn)生影響。根據(jù)表中排序順序可知，CC 和EC 相比DC 而言總體表現(xiàn)相對(duì)較差，BC對(duì)連接產(chǎn)生的影響最小，在相似性得分相同的情況下，難以區(qū)分連接產(chǎn)生的可能性。因此，F(xiàn)NI 算法選取度中心性值來(lái)衡量節(jié)點(diǎn)重要性，最大程度地區(qū)分不同節(jié)點(diǎn)對(duì)間連接產(chǎn)生的可能性，充分發(fā)揮節(jié)點(diǎn)重要性對(duì)鏈路預(yù)測(cè)結(jié)果的影響作用。

2.3 FNI算法描述

通過(guò)分析節(jié)點(diǎn)重要性對(duì)連接產(chǎn)生的影響，總結(jié)出在加權(quán)網(wǎng)絡(luò)中重要性越高的節(jié)點(diǎn)與其他節(jié)點(diǎn)建立新連接的可能性越大；通過(guò)分析不同中心性對(duì)連接產(chǎn)生的影響差異，總結(jié)出度中心性對(duì)連接產(chǎn)生的影響最大，因此提出一種融合節(jié)點(diǎn)重要性的無(wú)監(jiān)督鏈路預(yù)測(cè)算法FNI。首先，通過(guò)計(jì)算邊權(quán)強(qiáng)度simxy和路徑貢獻(xiàn)Sxy_path來(lái)計(jì)算節(jié)點(diǎn)對(duì)的相似性得分Sxy，并且計(jì)算節(jié)點(diǎn)對(duì)的中心性得分Cxy以衡量節(jié)點(diǎn)重要性。

其次，由于相似性得分與中心性得分的數(shù)量級(jí)存在差異，如果直接用原始數(shù)值進(jìn)行分析，就會(huì)突出數(shù)值較高的一方得分在綜合分析中的作用，相對(duì)削弱數(shù)值水平較低得分的作用。為了保證結(jié)果的可靠性，結(jié)合MinMaxScaler 函數(shù)對(duì)Sxy和Cxy進(jìn)行歸一化處理，映射到[0，1]區(qū)間，分別表示為New_Sxy和New_Cxy。

最后，由于相似性得分和中心性得分均是從衡量建立新連接可能性的角度出發(fā)，通過(guò)調(diào)節(jié)系數(shù)的方式將二者相加，實(shí)現(xiàn)雙方共同作用的最大效益，使算法達(dá)到預(yù)測(cè)效果的最優(yōu)化。對(duì)相似性得分分配系數(shù)α，對(duì)中心性得分分配系數(shù)β，計(jì)算節(jié)點(diǎn)對(duì)建立新連接的可能性Pxy。若系數(shù)β為負(fù)值，則表明該數(shù)據(jù)集上中心性小的節(jié)點(diǎn)更為重要，增加新連接產(chǎn)生的可能性，而中心性高的節(jié)點(diǎn)反而會(huì)抑制新連接的產(chǎn)生；若系數(shù)β為正值，則表明該數(shù)據(jù)集上節(jié)點(diǎn)的中心性越高，其重要性越高。如算法1所示。

算法1 FNI算法

節(jié)點(diǎn)數(shù)量為n的網(wǎng)絡(luò)數(shù)據(jù)集中，總節(jié)點(diǎn)對(duì)數(shù)量為n(n-1)/2 個(gè)。現(xiàn)有的基于局部結(jié)構(gòu)信息的無(wú)監(jiān)督預(yù)測(cè)方法均需要計(jì)算每對(duì)節(jié)點(diǎn)之間的相似度，時(shí)間復(fù)雜度為O(n2)。FNI算法首先計(jì)算每個(gè)節(jié)點(diǎn)對(duì)的相似性得分和中心性得分，時(shí)間復(fù)雜度為O(n2)；隨后利用歸一化函數(shù)在自定義參數(shù)下，計(jì)算節(jié)點(diǎn)間的連接可能性，時(shí)間復(fù)雜度仍為O(n2)。因此FNI算法的總時(shí)間復(fù)雜度為O(n2)，在保證算法運(yùn)行效率的同時(shí)，綜合節(jié)點(diǎn)重要性和結(jié)構(gòu)相似性對(duì)連接產(chǎn)生可能性的影響，在解決小規(guī)模加權(quán)網(wǎng)絡(luò)數(shù)據(jù)集的快速預(yù)測(cè)問(wèn)題上，相比同類(lèi)方法考慮更為全面。

3 實(shí)驗(yàn)驗(yàn)證與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)選取5個(gè)不同領(lǐng)域的典型真實(shí)數(shù)據(jù)集，均為小規(guī)模加權(quán)網(wǎng)絡(luò)。將每一個(gè)數(shù)據(jù)集對(duì)應(yīng)到各自需要做出快速預(yù)測(cè)結(jié)果的真實(shí)情景中，解決實(shí)際問(wèn)題。美國(guó)航空公司網(wǎng)絡(luò)US Air（US）：受天氣等突發(fā)情況影響需要臨時(shí)增設(shè)新航班；神經(jīng)網(wǎng)絡(luò)C Elegans（CE）：生物實(shí)驗(yàn)需要不斷預(yù)測(cè)下一突觸的產(chǎn)生；科學(xué)家合作網(wǎng)絡(luò)Net Science（NS）：科學(xué)家快速鎖定下一次學(xué)術(shù)合作中的預(yù)選對(duì)象；爆炸案恐怖分子聯(lián)系網(wǎng)絡(luò)Train Bombing（TB）：第一時(shí)間掌握恐怖分子間的聯(lián)系傾向以便采取行動(dòng)；小說(shuō)人物關(guān)系網(wǎng)絡(luò)Lesmis（LE）：即時(shí)預(yù)測(cè)小說(shuō)人物間關(guān)系走向。將實(shí)驗(yàn)數(shù)據(jù)集預(yù)處理后按照csv 格式存儲(chǔ)，借助可視化網(wǎng)絡(luò)分析工具Gephi，呈現(xiàn)出相應(yīng)數(shù)據(jù)集的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，每個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)信息如表2所示。

表2 各數(shù)據(jù)集的拓?fù)浣Y(jié)構(gòu)Table 2 Datasets topology

采用隨機(jī)抽樣的方式對(duì)每個(gè)數(shù)據(jù)集進(jìn)行100 次隨機(jī)劃分，抽取其中90%為訓(xùn)練集，10%為測(cè)試集，計(jì)算AUC值來(lái)表示預(yù)測(cè)結(jié)果的精確度。實(shí)驗(yàn)共分為以下三部分：（1）驗(yàn)證不同中心性對(duì)連接產(chǎn)生的影響差異，確保FNI 算法以度中心性衡量節(jié)點(diǎn)重要性的合理性；（2）橫向?qū)Ρ绕渌诰植烤W(wǎng)絡(luò)結(jié)構(gòu)的無(wú)監(jiān)督預(yù)測(cè)方法，驗(yàn)證FNI 算法提高預(yù)測(cè)結(jié)果精確度的有效性；（3）縱向?qū)Ρ热N基于圖嵌入的有監(jiān)督式鏈路預(yù)測(cè)方法，針對(duì)小規(guī)模加權(quán)網(wǎng)絡(luò)快速預(yù)測(cè)問(wèn)題，分析FNI算法的必要性。

3.2 驗(yàn)證不同中心性的影響差異

不同中心性從多角度衡量節(jié)點(diǎn)重要性，對(duì)連接產(chǎn)生的影響差異很大，勢(shì)必也會(huì)體現(xiàn)在對(duì)鏈路預(yù)測(cè)結(jié)果精確度的影響上。參考FNI算法的核心思想：Pxy=αNew_Sxy+βNew_Cxy，實(shí)驗(yàn)利用WCN、WAA、WRA 以及WLP 四種經(jīng)典相似性指標(biāo)計(jì)算Sxy，利用DC、BC、CC、EC四種中心性指標(biāo)計(jì)算Cxy，并按照WCN 對(duì)應(yīng)的新指標(biāo)分別WCN_DC、WCN_BC、WCN_CC、WCN_EC 的方式，以此類(lèi)推進(jìn)行命名。

在實(shí)驗(yàn)過(guò)程中，為快速找到相應(yīng)α、β值，結(jié)合梯度下降更新參數(shù)，得到最終的預(yù)測(cè)AUC 值。本次實(shí)驗(yàn)的重點(diǎn)在于證實(shí)相比其他中心性指標(biāo)，度中心性度量節(jié)點(diǎn)重要性時(shí)，對(duì)鏈路預(yù)測(cè)結(jié)果具有最大程度上的積極影響。表3 總結(jié)了每一種新指標(biāo)在不同數(shù)據(jù)集上的預(yù)測(cè)精確度，括號(hào)內(nèi)數(shù)字代表同一數(shù)據(jù)集、不同中心性下，新指標(biāo)AUC 值的排名情況，下劃線標(biāo)注代表預(yù)測(cè)效果不如原指標(biāo)。

表3 不同中心性對(duì)預(yù)測(cè)結(jié)果AUC值的影響Table 3 Influence of different centrality on AUC values of predicted results

分析表3 可知，DC 在5 個(gè)數(shù)據(jù)集上均表現(xiàn)良好，能夠提高原有指標(biāo)1%～2%的預(yù)測(cè)精確度，在其相應(yīng)20 組實(shí)驗(yàn)中，達(dá)到同比最高精確度12次，對(duì)連接產(chǎn)生的影響最大，新指標(biāo)的預(yù)測(cè)結(jié)果更為精準(zhǔn)；BC 在應(yīng)用到WLP指標(biāo)上時(shí)，使兩個(gè)數(shù)據(jù)集下的精確度與原指標(biāo)持平，除此之外其他新指標(biāo)的精確度均明顯下降；CC在其20組實(shí)驗(yàn)數(shù)據(jù)中，有3 組實(shí)驗(yàn)的精確度略低于原有指標(biāo)，并在2 組實(shí)驗(yàn)上實(shí)現(xiàn)了預(yù)測(cè)結(jié)果最優(yōu)化，總體表現(xiàn)相比DC 較差；EC 在TB 和LE 數(shù)據(jù)集上表現(xiàn)較為優(yōu)異，在其20 組實(shí)驗(yàn)中，6 次實(shí)現(xiàn)最優(yōu)預(yù)測(cè)結(jié)果，但在7 組實(shí)驗(yàn)中，大幅降低了原有指標(biāo)精確度，不具有相對(duì)穩(wěn)定性和普適性。

綜上所述，節(jié)點(diǎn)重要性對(duì)連接產(chǎn)生具有一定的影響，其度量方式對(duì)預(yù)測(cè)結(jié)果的作用差異較大，實(shí)驗(yàn)結(jié)果基本符合上文理論分析。即DC相比其他三種度量方式整體對(duì)連接產(chǎn)生的影響最大，能夠體現(xiàn)在鏈路預(yù)測(cè)的結(jié)果中，以度中心性度量節(jié)點(diǎn)重要性，并以此計(jì)算新連接產(chǎn)生的可能性，能夠穩(wěn)定有效地提高預(yù)測(cè)精確度。CC和EC 的影響效果波動(dòng)較大，適用性弱于DC，無(wú)法解決不同結(jié)構(gòu)類(lèi)型數(shù)據(jù)集的鏈路預(yù)測(cè)問(wèn)題，而B(niǎo)C 完全不適用。因此，在四種經(jīng)典相似性指標(biāo)上的大量實(shí)驗(yàn)，結(jié)果足以證明度中心性對(duì)新連接產(chǎn)生的影響最大，對(duì)鏈路預(yù)測(cè)結(jié)果準(zhǔn)確性的提高效果最為明顯，確保了FNI算法以度中心性大小衡量節(jié)點(diǎn)重要性，具有理論正確性和實(shí)踐可行性。

3.3 FNI算法預(yù)測(cè)結(jié)果

針對(duì)小規(guī)模加權(quán)網(wǎng)絡(luò)的快速預(yù)測(cè)問(wèn)題，將FNI算法與同類(lèi)基于局部網(wǎng)絡(luò)結(jié)構(gòu)的無(wú)監(jiān)督預(yù)測(cè)方法進(jìn)行橫向?qū)Ρ葘?shí)驗(yàn)，預(yù)測(cè)精確度結(jié)果如表4所示。

表4 FNI算法橫向?qū)Ρ葘?shí)驗(yàn)AUC值Table 4 AUC values of transverse contrast experiment of FNI algorithm

分析表4 可知，4 個(gè)數(shù)據(jù)集上FNI 算法預(yù)測(cè)精確度AUC 值，明顯高于同類(lèi)其他11 種基于局部網(wǎng)絡(luò)結(jié)構(gòu)的無(wú)監(jiān)督預(yù)測(cè)方法。只有在Lesmis（LE）數(shù)據(jù)集上由于數(shù)據(jù)集特性，局部信息相比路徑信息更有效，F(xiàn)NI 算法的精確度與rWRA指標(biāo)近乎持平，但仍明顯高于其他預(yù)測(cè)指標(biāo)。分析其具體原因，F(xiàn)NI算法首先合理考慮了節(jié)點(diǎn)重要性對(duì)連接產(chǎn)生的影響；其次，利用度中心性來(lái)計(jì)算中心性得分，更加精準(zhǔn)地計(jì)算了不同節(jié)點(diǎn)對(duì)間產(chǎn)生新連接的可能性；最后，通過(guò)自定義系數(shù)最優(yōu)化結(jié)構(gòu)相似性和節(jié)點(diǎn)重要性對(duì)預(yù)測(cè)結(jié)果的影響程度。因此，實(shí)驗(yàn)結(jié)果證實(shí)了在小規(guī)模加權(quán)網(wǎng)絡(luò)數(shù)據(jù)集上，F(xiàn)NI算法相比現(xiàn)有其他同類(lèi)方法整體提高了預(yù)測(cè)結(jié)果AUC 值，可以達(dá)到最佳預(yù)測(cè)效果。

在證實(shí)FNI算法預(yù)測(cè)結(jié)果的有效性后，進(jìn)一步分析FNI 算法中的參數(shù)選取。在計(jì)算產(chǎn)生新連接可能性Pxy=αNew_Sxy+βNew_Cxy這一步驟里，參數(shù)α和參數(shù)β均為自定義參數(shù)。實(shí)驗(yàn)中為快速找到相應(yīng)α和β值，選取α初始值為1，β初始值為-1，采用梯度下降思想來(lái)更新參數(shù)取值，將預(yù)測(cè)精確度與期望精確度差值定義為損失函數(shù)并使其最小化。圖2 表示隨著參數(shù)的迭代更新，各數(shù)據(jù)集上的損失Loss值不斷下降，AUC值保持上升趨勢(shì)，逐步趨于穩(wěn)定，最終得到所需參數(shù)α、β。

圖2 各數(shù)據(jù)集上Loss值和AUC值變化情況Fig.2 Loss value and AUC value changes on datasets

表5展示出FNI 算法在不同數(shù)據(jù)集上的相應(yīng)參數(shù)α、β值。β在5個(gè)數(shù)據(jù)集上最終取值全部為負(fù)值，驗(yàn)證了中心性小的節(jié)點(diǎn)，在其局部網(wǎng)絡(luò)結(jié)構(gòu)中地位更加重要，與其他節(jié)點(diǎn)產(chǎn)生新連接的可能性更高。對(duì)應(yīng)到5個(gè)數(shù)據(jù)的具體情境中可以理解為，航空網(wǎng)絡(luò)里中心性大的中轉(zhuǎn)樞紐可能行程較滿，班次較少的小機(jī)場(chǎng)間更容易新建航班；神經(jīng)網(wǎng)絡(luò)里一些高中心性的神經(jīng)元接受傳遞信息通常具有重復(fù)性，一些傳遞作用較少的神經(jīng)元更容易傳遞出新信息；科學(xué)家合作網(wǎng)絡(luò)里兩個(gè)團(tuán)隊(duì)的權(quán)威人物間的合作概率要小于其各自同自己團(tuán)隊(duì)伙伴合作的概率；恐怖分子聯(lián)系網(wǎng)絡(luò)里主謀的聯(lián)系關(guān)系較為隱秘固定，遠(yuǎn)離核心的幫兇間更容易彼此聯(lián)系；小說(shuō)人物關(guān)系網(wǎng)絡(luò)里主要角色關(guān)系已經(jīng)充分介紹，小人物間會(huì)發(fā)生更多關(guān)系碰撞的故事。

表5 FNI算法的參數(shù)取值Table 5 Parameter values of FNI algorithm

綜合5個(gè)數(shù)據(jù)集上的取值表現(xiàn)，α穩(wěn)定在區(qū)間（1.0，1.5]，β穩(wěn)定在區(qū)間(-0.4,0)，說(shuō)明在小規(guī)模加權(quán)網(wǎng)絡(luò)上，結(jié)構(gòu)相似性同比節(jié)點(diǎn)重要性對(duì)產(chǎn)生連接可能性的影響程度更大，但節(jié)點(diǎn)重要性的影響程度同樣不可忽略。

FNI算法預(yù)測(cè)結(jié)果的對(duì)比實(shí)驗(yàn)，證實(shí)了本文的兩個(gè)貢獻(xiàn)：一是中心性小的節(jié)點(diǎn)反而更重要，節(jié)點(diǎn)重要性在鏈路預(yù)測(cè)問(wèn)題中具有重要研究意義；二是本文提出的FNI 算法相比同類(lèi)基于局部網(wǎng)絡(luò)結(jié)構(gòu)的無(wú)監(jiān)督式鏈路預(yù)測(cè)方法，預(yù)測(cè)結(jié)果AUC值整體更高。

3.4 FNI算法的必要性評(píng)估

近年來(lái)，一些基于機(jī)器學(xué)習(xí)和深度學(xué)習(xí)的圖嵌入方法在鏈路預(yù)測(cè)問(wèn)題研究中較為常用?？v向?qū)Ρ葻o(wú)監(jiān)督式FNI 算法與三種不同類(lèi)型的有監(jiān)督式圖嵌入方法的整體性能，確保FNI 算法在當(dāng)前加權(quán)網(wǎng)絡(luò)鏈路預(yù)測(cè)的相關(guān)研究中具有必要性和特定優(yōu)越性，實(shí)驗(yàn)結(jié)果如表6所示。

表6 FNI算法縱向?qū)Ρ葘?shí)驗(yàn)AUC值Table 6 AUC values of longitudinal contrast experiment of FNI algorithm

由表6 可知，F(xiàn)NI 算法在US 數(shù)據(jù)集上相較于Node2vec 方法AUC 值提升最多，約提升27 個(gè)百分點(diǎn)；在NS數(shù)據(jù)集上相較于HOPE方法AUC值提升最少，約提升3 個(gè)百分點(diǎn)。因此，綜合FNI 算法在5 個(gè)數(shù)據(jù)集上的表現(xiàn)，其AUC 值總體比有監(jiān)督式的圖嵌入方法高3～27個(gè)百分點(diǎn)。分析其具體原因：首先，在規(guī)模較小的數(shù)據(jù)集上監(jiān)督訓(xùn)練的效果往往較差，稀疏網(wǎng)絡(luò)所對(duì)應(yīng)的可用特征有限，學(xué)習(xí)生成的網(wǎng)絡(luò)表示存在較大偏差。其次，在短路徑網(wǎng)絡(luò)中，存在連接和不存在連接的嵌入向量不易區(qū)分其距離分布[25]，嵌入模型的訓(xùn)練效果并不理想。實(shí)驗(yàn)數(shù)據(jù)集除NS外，均為平均距離小于3的“小世界”網(wǎng)絡(luò)，實(shí)驗(yàn)結(jié)果也表明NS數(shù)據(jù)集上圖嵌入方法整體的精確度更接近于FNI算法。

針對(duì)小規(guī)模加權(quán)網(wǎng)絡(luò)的快速預(yù)測(cè)，有監(jiān)督式圖嵌入方法存在一定的弊端，不僅需要額外的監(jiān)督訓(xùn)練時(shí)間，最為主要的是其預(yù)測(cè)精確度普遍較低。FNI 算法的整體性能明顯優(yōu)于有監(jiān)督式的圖嵌入方法，故FNI算法的提出和運(yùn)用具備解決實(shí)際問(wèn)題的必要性。

4 結(jié)束語(yǔ)

節(jié)點(diǎn)重要性對(duì)連接產(chǎn)生的影響并未在現(xiàn)有基于局部網(wǎng)絡(luò)結(jié)構(gòu)的無(wú)監(jiān)督預(yù)測(cè)方法中得到體現(xiàn)，并且在真實(shí)網(wǎng)絡(luò)里中心性越小節(jié)點(diǎn)往往更加重要。本文從結(jié)構(gòu)相似性和節(jié)點(diǎn)重要性兩個(gè)角度計(jì)算連接可能性，提出一種融合節(jié)點(diǎn)重要性的無(wú)監(jiān)督鏈路預(yù)測(cè)算法FNI。大量實(shí)驗(yàn)結(jié)果證明，在解決小規(guī)模加權(quán)網(wǎng)絡(luò)的快速預(yù)測(cè)問(wèn)題上，F(xiàn)NI 算法在同類(lèi)預(yù)測(cè)方法中的預(yù)測(cè)精確度更高，且相比有監(jiān)督式的鏈路預(yù)測(cè)方法更具研究必要性。

本文所提算法在后續(xù)研究過(guò)程中，仍有需要不斷優(yōu)化的方面：一是該算法雖然很好地利用中心性度量節(jié)點(diǎn)重要性，但是針對(duì)加權(quán)網(wǎng)絡(luò)節(jié)點(diǎn)重要性的研究仍需不斷探索；二是該算法在尋找路徑信息時(shí)較為復(fù)雜，后續(xù)會(huì)結(jié)合降維方法，降低算法的時(shí)間復(fù)雜度，實(shí)現(xiàn)算法性能的進(jìn)一步優(yōu)化。