李英樂，何贊園，王 凱，許明艷

（中國人民解放軍戰(zhàn)略支援部隊信息工程大學(xué)信息技術(shù)研究所，鄭州 450002）

0 概述

鏈路預(yù)測是網(wǎng)絡(luò)科學(xué)的一個重要研究方向，其目的是通過分析網(wǎng)絡(luò)當(dāng)前的拓?fù)浣Y(jié)構(gòu)和屬性信息，來預(yù)測網(wǎng)絡(luò)中不存在鏈接的節(jié)點之間出現(xiàn)鏈接的可能性［1］，對研究復(fù)雜網(wǎng)絡(luò)的演進(jìn)機(jī)制具有十分重要的意義［2］，在生物網(wǎng)絡(luò)［3］和社交網(wǎng)絡(luò)［4］等現(xiàn)實網(wǎng)絡(luò)實踐中也具有很好的應(yīng)用價值。

近年來，越來越多的學(xué)者對鏈路預(yù)測的方法進(jìn)行了深入研究，并在多個方面都取得了一系列成果，特別是在基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的鏈路預(yù)測方法上的進(jìn)展較大。基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的鏈路預(yù)測方法根據(jù)節(jié)點之間的鏈接關(guān)系計算節(jié)點之間的相似性，得到節(jié)點之間出現(xiàn)鏈接的可能性。節(jié)點相似性指標(biāo)大體上包括全局相似性指標(biāo)和局部相似性指標(biāo)兩大類。局部相似性指標(biāo)主要根據(jù)節(jié)點的共同鄰居來計算相似性，包括CN指標(biāo)［5］、Salton指標(biāo)［6］、AA指標(biāo)［7］和RA指標(biāo)［8］等。全局性指標(biāo)是從整個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)著眼計算節(jié)點相似性，主要有基于隨機(jī)游走的Cos+指標(biāo)［9］、ACT 指標(biāo)［10］、RWR 指標(biāo)［11］和基于路徑的LP 指標(biāo)［12］、LHZ-II 指標(biāo)［13］、Katz 指標(biāo)［14］。局部性指標(biāo)僅考慮鄰居節(jié)點，其計算復(fù)雜度和精度較低；全局性相似指標(biāo)考慮整個網(wǎng)絡(luò)結(jié)構(gòu)，預(yù)測精度較高，但計算復(fù)雜度也較高，難以用于大規(guī)模網(wǎng)絡(luò)中。需要注意的是，由于RA 指標(biāo)在局部相似性指標(biāo)中取得相當(dāng)高的預(yù)測精度，因此受到了廣泛的關(guān)注。但RA 指標(biāo)僅從簡單的資源傳輸過程描述出發(fā)對其進(jìn)行量化，忽略了傳輸節(jié)點周圍拓?fù)湫畔Y源傳輸節(jié)點傳輸概率的影響［15-16］。在現(xiàn)實網(wǎng)絡(luò)中，傳輸節(jié)點周圍拓?fù)涞木奂潭扰c資源傳輸?shù)男Ч哂邢嚓P(guān)性［17-18］，傳輸節(jié)點越聚集，資源的傳輸效果越好。

針對上述問題，本文提出一種基于資源傳輸節(jié)點拓?fù)渚o密性的鏈路預(yù)測方法。研究資源傳輸過程中多跳節(jié)點資源的傳輸情況，確定重要傳輸節(jié)點，對傳輸節(jié)點聚類系數(shù)進(jìn)行分析，基于聚類系數(shù)改進(jìn)拓?fù)渚o密性量化方法，并利用傳輸節(jié)點緊密性對共同鄰居傳輸資源進(jìn)行參數(shù)調(diào)整，進(jìn)而重新刻畫節(jié)點間相似性，給出資源傳輸節(jié)點拓?fù)渚o密性指標(biāo)。此外，在Precision 衡量標(biāo)準(zhǔn)下，利用多個實際網(wǎng)絡(luò)對所提指標(biāo)進(jìn)行有效性分析，以驗證該方法的預(yù)測效果。

1 相關(guān)工作

當(dāng)前基于相似性的鏈路預(yù)測方法有很多，研究人員基于不同原理提出多種預(yù)測指標(biāo)，本節(jié)對幾種知名預(yù)測指標(biāo)及網(wǎng)絡(luò)資源傳輸相關(guān)指標(biāo)簡要介紹如下：

1）CN 指標(biāo)［5］。LORRAIN 等人直接利用共同鄰居的數(shù)目衡量節(jié)點x和y的相似度，該方法復(fù)雜度低，在集聚性較高的網(wǎng)絡(luò)中表現(xiàn)較好，但在稀疏網(wǎng)絡(luò)中表現(xiàn)較差。Γ（x）為節(jié)點鄰居的集合，表示為：

2）AA 指標(biāo)［7］。根據(jù)節(jié)點對共同鄰居的重要程度不同，ADAMIC 等人利用高度懲罰機(jī)制對共同鄰居加權(quán)，權(quán)值為節(jié)點度對數(shù)的倒數(shù)，表示為：

3）CAR 指標(biāo)［17］。在CN 的基礎(chǔ)上考慮了共同鄰居之間存在鏈接的情形，該方法在集聚性較高的網(wǎng)絡(luò)中表現(xiàn)較好，CAR 指標(biāo)可表示為：

4）LP 指標(biāo)［12］。呂林媛等人在共同鄰居（即2 階路徑）基礎(chǔ)上，綜合考慮了3 階路徑對節(jié)點相似性的影響，LP 指標(biāo)可表示為：

其中，S為相似度矩陣，A是鄰接矩陣，(An)xy表示節(jié)點x和y之間長度為n的路徑數(shù)目，α為調(diào)節(jié)參數(shù)。該方法是預(yù)測效果與計算復(fù)雜度的合理折中，效果好于CN 指標(biāo)。

5）Katz 指標(biāo)［14］。KATZ 等人從網(wǎng)絡(luò)全局角度充分考慮節(jié)點間所有的路徑數(shù)目量化節(jié)點間的相似度，具有很好的預(yù)測精度，但復(fù)雜度較高，表示為：

6）ACT 指標(biāo)［10］。KLEIN 等人將一個隨機(jī)游走的粒子從一個節(jié)點x游走至另一個節(jié)點y所需要走的平均步數(shù)，作為兩節(jié)點產(chǎn)生連接的可能性，提出平均通勤時間指標(biāo)，表示為：

7）Cos+指標(biāo)［9］。FOUSS 等人在基于隨機(jī)游走的基礎(chǔ)上，提出余弦相似性指標(biāo)，在矩陣L+計算2 個向量之間的相似性：

8）RA 指標(biāo)［8］。周濤等人基于資源傳輸原理，認(rèn)為共同鄰居傳遞資源的多少和其路徑上共同鄰居的節(jié)點度成反比，RA 指標(biāo)具體表示為：

9）ERA 指標(biāo)［19］。劉樹新等人在RA 指標(biāo)的基礎(chǔ)上，詳細(xì)分析節(jié)點間多跳的局部路徑傳輸?shù)馁Y源，提出了擴(kuò)展的資源分配ERA 指標(biāo)，具體表示為：

其中，參數(shù)σ表示多跳路徑資源對相似性的貢獻(xiàn)，當(dāng)σ=0 時，該指標(biāo)退化為RA 指標(biāo)。

10）EP 指標(biāo)［20］。王凱等人考慮資源傳輸路徑有效程度對傳輸性能的影響，分析了潛在的資源傳輸路徑有效性并對雙向資源傳輸量進(jìn)行刻畫，EP 指標(biāo)具體表示為：

其中，Wz表示節(jié)點z所有連邊的路徑有效量化值之和，wlij表示節(jié)點i、j之間的有效資源傳輸量。

11）QN 指標(biāo)［21］。王凱等人在研究路徑傳輸有效性基礎(chǔ)上，分析傳輸路徑的資源承載能力，提出資源承載度及相應(yīng)的預(yù)測方案，具體表示為：

其中，Qλ（i，j）表示節(jié)點i、j之間量化的資源承載能力。

綜上可見，資源傳輸原理是節(jié)點相似性刻畫的重要參考，其不僅應(yīng)從傳輸過程分析，而且在傳輸路徑、局域拓?fù)涞确矫嬗懈啻芯恐帯?/p>

2 資源傳輸節(jié)點拓?fù)渚o密性鏈路預(yù)測方法

2.1 資源傳輸節(jié)點拓?fù)渚o密性分析與量化

研究發(fā)現(xiàn)，網(wǎng)絡(luò)演進(jìn)時連邊的變化會影響到網(wǎng)絡(luò)中的信息的傳播［23］，同時網(wǎng)絡(luò)中信息的傳播也會影響到連邊的變化［24］，此兩者具有相關(guān)性［25］。任意2 個未連接點之間的資源傳輸需要經(jīng)過多跳節(jié)點進(jìn)行，共同鄰居節(jié)點作為最短跳的資源傳播節(jié)點，是資源傳輸過程的核心。圖1 所示為不同類型資源傳輸節(jié)點在資源傳輸過程中的作用（圖中僅以節(jié)點x傳輸一定的資源至節(jié)點y的過程為例）。

圖1 不同類型資源傳輸節(jié)點在資源傳輸中的作用Fig.1 Effect of different types of resource transmission nodes in resource transmission

從圖1 可以看出，在多跳路徑傳輸中，隨著路徑上節(jié)點數(shù)目的增加，資源傳輸過程趨于復(fù)雜，資源量的傳輸“衰落”現(xiàn)象也越來越明顯，導(dǎo)致節(jié)點x到節(jié)點y的資源傳輸量也會以一定的比例逐步減少。而僅經(jīng)過兩跳傳輸?shù)墓餐従庸?jié)點z，其傳輸資源的效率和確定性明顯高于其他傳輸節(jié)點。因此，在資源傳輸過程中，共同鄰居是資源傳輸?shù)暮诵墓?jié)點，發(fā)揮著關(guān)鍵作用。在資源傳輸?shù)暮罄m(xù)分析中，將重點針對核心資源傳輸節(jié)點共同鄰居。

資源傳輸指標(biāo)（RA）是直接利用核心傳輸節(jié)點共同鄰居進(jìn)行資源傳輸過程分析，然后對任意2 個未連接節(jié)點進(jìn)行相似性刻畫。該方法效果較好，但現(xiàn)實網(wǎng)絡(luò)中核心傳輸節(jié)點共同鄰居周圍拓?fù)浣Y(jié)構(gòu)較為復(fù)雜，僅利用節(jié)點度對其進(jìn)行資源傳輸量的刻畫難以更加有效地量化傳輸過程。共同鄰居節(jié)點周圍拓?fù)浣Y(jié)構(gòu)的緊密性會對資源傳輸有著較大影響，如圖2 所示。對于節(jié)點x和節(jié)點y的共同鄰居節(jié)點zn，其周圍存在鄰居節(jié)點｛v1，v2，v3，v4，v5｝和許多連邊構(gòu)成了相對稠密的局部結(jié)構(gòu)，這對于資源傳播具有很大的促進(jìn)作用。為量化局部結(jié)構(gòu)對節(jié)點間資源傳輸?shù)淖饔?，需要分析刻畫傳輸?jié)點周圍拓?fù)浣Y(jié)構(gòu)的資源傳播緊密性。

圖2 資源傳輸節(jié)點周圍拓?fù)浣Y(jié)構(gòu)示意圖Fig.2 Schematic diagram of topology around resource transmission nodes

網(wǎng)絡(luò)節(jié)點的聚類系數(shù)是刻畫網(wǎng)絡(luò)局部拓?fù)浣Y(jié)構(gòu)緊密性的重要參數(shù)［26］。對于網(wǎng)絡(luò)中任意一個節(jié)點i，有ki個鄰居節(jié)點。若所有鄰居節(jié)點間兩兩互聯(lián)，則所有連邊數(shù)目表示為ki（ki-1）/2，此時網(wǎng)絡(luò)鄰居節(jié)點的緊密性最大。在正常情形下，節(jié)點i的聚類系數(shù)可以表示為：

其中，Ei表示節(jié)點i的所有鄰居節(jié)點間實際存在連邊的數(shù)目。節(jié)點聚類系數(shù)會隨著鄰居節(jié)點連邊數(shù)目不斷增加，如圖3 所示。圖3（a）中鄰居節(jié)點之間無任何連接，此時節(jié)點i的拓?fù)浼坌宰畹?，Ci=0；圖3（b）中鄰居節(jié)點之間存在一條連接，此時聚類系數(shù)Ci=2×1/（4×3）=1/6；圖3（c）中鄰居節(jié)點之間的連接大幅度增加，此時拓?fù)溟g關(guān)系更加緊密，聚類系數(shù)為Ci=2×3/（4×3）=1/2；圖3（d）中所有鄰居節(jié)點都存在連接，局部拓?fù)浼坌赃_(dá)到最大，此時聚類系數(shù)為Ci=1?？梢钥闯?，網(wǎng)絡(luò)節(jié)點聚類系數(shù)一定程度上表征了獨立節(jié)點周圍拓?fù)渚o密性。然而，不同于獨立節(jié)點僅考慮局部拓?fù)浣Y(jié)構(gòu)，對于一對未連接節(jié)點的核心資源傳輸節(jié)點，其資源傳輸緊密性的刻畫需要考慮資源傳輸節(jié)點周圍拓?fù)浣Y(jié)構(gòu)對資源傳輸過程的影響，而且直接使用聚類系數(shù)難以表征不同鄰居節(jié)點對傳輸資源緊密性的作用。

圖3 獨立節(jié)點不同拓?fù)浣Y(jié)構(gòu)下的緊密性分析Fig.3 Tightness analysis of independent nodes under different topology

為分析在不同拓?fù)浣Y(jié)構(gòu)下資源傳輸節(jié)點周圍局部拓?fù)鋵?jié)點間資源傳輸?shù)挠绊?，進(jìn)而刻畫資源傳輸節(jié)點拓?fù)浣Y(jié)構(gòu)的緊密性，本文引入多個局部拓?fù)浣Y(jié)構(gòu)進(jìn)行對比分析，如圖4 中的4 個網(wǎng)絡(luò)結(jié)構(gòu)中均存在一對未連接的節(jié)點x和y，以及待分析的資源傳輸節(jié)點zi。下文將對比分析zi周圍不同拓?fù)浣Y(jié)構(gòu)對于節(jié)點x和y資源傳輸過程的影響，即對資源傳輸節(jié)點緊密性的影響。對于圖4（a）和圖4（b），傳輸節(jié)點zi具有相同數(shù)目的鄰居節(jié)點，但后者鄰居節(jié)點之間連邊數(shù)目明顯高于前者，因此從節(jié)點x和y資源傳輸?shù)慕嵌?，后者傳輸?jié)點zi的資源傳輸緊密性明顯高于前者；對于圖4（b）和圖4（c），傳輸節(jié)點zi既具有相同數(shù)目的鄰居節(jié)點，也具有相同數(shù)目的鄰居連邊，不同的是前者是｛v1，v3｝和｛v2，v3｝，而后者是｛v1，x｝和｛v1，z1｝。雖然從聚類系數(shù)角度，圖4（b）和圖4（c）的集聚性相同，但是很明顯后者zi的鄰居節(jié)點v1的連邊為資源傳輸提供了更大的可能（對比來看，后者鄰居節(jié)點v1為節(jié)點x和y提供了更少跳數(shù)的稠密拓?fù)鋫鬏斀Y(jié)構(gòu)），因此，從節(jié)點x和y資源傳輸?shù)慕嵌?，圖4（c）傳輸節(jié)點zi的資源傳輸緊密性高于圖4（b）；對于圖4（c）和圖4（d），傳輸節(jié)點zi具有相同數(shù)目的鄰居節(jié)點，但后者具有更多鄰居連邊和有效鄰居節(jié)點v4。因此，從節(jié)點x和y資源傳輸?shù)慕嵌?，圖4（d）傳輸節(jié)點zi的資源傳輸緊密性高于圖4（c）。

圖4 不同資源傳輸節(jié)點周圍拓?fù)浣Y(jié)構(gòu)Fig.4 Topology around different resource transmission nodes

通過上述分析可以看出，傳輸節(jié)點的鄰居在資源傳輸緊密性的刻畫上發(fā)揮著不同的作用。對于資源傳輸始發(fā)、終結(jié)節(jié)點x和y，若傳輸節(jié)點zi的鄰居與其存在連接，則其對于資源傳輸?shù)呢暙I(xiàn)較大，如圖5中的v1、v2、v3。與之相反，若傳輸節(jié)點zi的鄰居與始發(fā)、終結(jié)節(jié)點并無連接，其對于資源傳輸?shù)呢暙I(xiàn)非常小，考慮到路徑上資源的“衰落”，可以忽略其對于節(jié)點資源傳輸緊密性的影響，如圖5 中的v4、v5。因此，為從資源傳輸?shù)慕嵌雀玫乜坍媯鬏敼?jié)點的緊密性，對傳輸節(jié)點的鄰居中對緊密性貢獻(xiàn)較大的鄰居進(jìn)行定義。

圖5 資源傳輸節(jié)點周圍拓?fù)浣Y(jié)構(gòu)示意圖Fig.5 Schematic diagram of topology around resource transmission nodes

定義1（資源傳輸節(jié)點的緊密鄰居） 網(wǎng)絡(luò)中任意一對未連接的資源傳輸始發(fā)、終結(jié)節(jié)點x和y，共同鄰居節(jié)點z是其核心傳輸節(jié)點。對于傳輸節(jié)點z的所有鄰居節(jié)點，其緊密鄰居包含始發(fā)、終結(jié)節(jié)點x和y，主要囊括與其存在直接連邊的鄰居節(jié)點。傳輸節(jié)點z的緊密鄰居集合可表示為：

其中，Γ（z）為傳輸節(jié)點z的所有鄰居節(jié)點集合，Γ'（x）、Γ'（y）為包括自身節(jié)點x、y及其所有鄰居節(jié)點的集合。圖6 所示為資源傳輸節(jié)點的緊密鄰居，對于資源傳輸始發(fā)、終結(jié)節(jié)點x和y，其資源傳輸節(jié)點z的緊密鄰居為：

圖6 資源傳輸節(jié)點的緊密鄰居示意圖Fig.6 Schematic diagram of tight neighbors of resource transmission nodes

對于同樣的網(wǎng)絡(luò)結(jié)構(gòu)，若其資源傳輸?shù)氖及l(fā)、終結(jié)節(jié)點發(fā)生了變化，其緊密鄰居也會發(fā)生變化。若圖6 中資源傳輸始發(fā)、終結(jié)節(jié)點是v4和v5，其資源傳輸節(jié)點z的緊密鄰居為：

在對資源傳輸節(jié)點z的緊密鄰居進(jìn)行定義后，便可以對其緊密性進(jìn)行量化，本文基于聚類系數(shù)，從緊密鄰居的角度定義傳輸節(jié)點的緊密性。

定義2（資源傳輸節(jié)點拓?fù)渚o密性） 網(wǎng)絡(luò)中任意一對未連接的資源傳輸始發(fā)、終結(jié)節(jié)點x和y，共同鄰居節(jié)點z是其核心傳輸節(jié)點。對于傳輸節(jié)點z，其資源傳輸拓?fù)渚o密性量化為緊密鄰居間實際連邊數(shù)目占比緊密鄰居最大連邊數(shù)目，即：

具體表示為：

2.2 資源傳輸節(jié)點拓?fù)渚o密性指標(biāo)

對資源傳輸節(jié)點拓?fù)渚o密性進(jìn)行量化后，便可以基于拓?fù)渚o密性分析節(jié)點之間的相似性，進(jìn)而預(yù)測任意節(jié)點之間存在的可能性。在一般情況下，與資源分配指標(biāo)RA 相似，可以直接利用傳輸節(jié)點拓?fù)渚o密性對資源傳播進(jìn)行加成：

式（18）直接利用存在相似度量化上的問題，若資源傳輸節(jié)點z的緊密鄰居之間并無連接，其相似度則量化為0。該量化方法會一定程度上忽視共同鄰居節(jié)點本身的資源傳輸能力。因此，在刻畫資源傳輸節(jié)點拓?fù)渚o密性指標(biāo)時，需要同時考慮兩個方面：一方面考慮關(guān)鍵資源傳輸節(jié)點本身的資源傳輸能力；另一方面需要考慮該資源傳輸節(jié)點拓?fù)渚o密性對資源傳輸能力的影響。如圖7 所示，若資源從節(jié)點x傳輸指定資源到端節(jié)點y，則該傳輸過程的資源量與共同鄰居節(jié)點本身資源傳輸和其拓?fù)渚o密性對資源傳輸影響相關(guān)。

圖7 資源傳輸節(jié)點拓?fù)渚o密性指標(biāo)示意圖Fig.7 Schematic diagram of tightness index of resource transmission node topology

定義3（資源傳輸節(jié)點拓?fù)渚o密性指標(biāo)） 對于一個無向網(wǎng)絡(luò)G（V，E），其中網(wǎng)絡(luò)中任意存在兩個節(jié)點x和y，從網(wǎng)絡(luò)中關(guān)鍵資源傳輸節(jié)點的局部拓?fù)涑霭l(fā)，即共同鄰居節(jié)點拓?fù)渚o密性的角度，節(jié)點x和y之間的相似性可量化為所有共同鄰居節(jié)點本身傳遞資源量與其拓?fù)渚o密性加成資源量之和，具體表示為：

其中，β為調(diào)節(jié)參數(shù)，用于調(diào)整不同網(wǎng)絡(luò)中資源傳輸節(jié)點拓?fù)渚o密性對資源傳輸量的影響程度，1/kz表示共同鄰居節(jié)點本身傳遞資源量，而表示拓?fù)渚o密性加成資源量。當(dāng)β=0 時，資源傳輸節(jié)點拓?fù)渚o密性指標(biāo)（TT 指標(biāo)）與資源分配指標(biāo)RA 相同。而對于圖7 所示的拓?fù)浣Y(jié)構(gòu)中

3 網(wǎng)絡(luò)數(shù)據(jù)集

為了驗證基于傳輸節(jié)點拓?fù)渚o密性的鏈路預(yù)測方法的有效性，本文選取了多個不同類型的實際網(wǎng)絡(luò)進(jìn)行實驗，對具體網(wǎng)絡(luò)數(shù)據(jù)分別介紹如下：

1）爵士音樂家合作網(wǎng)絡(luò)Jazz［27］：一種表示爵士音樂家之間的合作關(guān)系的網(wǎng)絡(luò)，其中音樂家用網(wǎng)絡(luò)節(jié)點表示，音樂家之間的合作關(guān)系用網(wǎng)絡(luò)中的連邊表示。

2）食物鏈網(wǎng)絡(luò)FWEW［28］：一種生活在Everglades Graminoids 濕季的69 種生物組成的網(wǎng)絡(luò)，不同生物用網(wǎng)絡(luò)節(jié)點表示，生物之間的捕食關(guān)系用網(wǎng)絡(luò)的邊表示。

3）美國航空線路網(wǎng)絡(luò)USAir［29］：網(wǎng)絡(luò)的節(jié)點代表不同的機(jī)場，網(wǎng)絡(luò)中的連邊代表機(jī)場之間有直達(dá)航線。

4）線蟲神經(jīng)網(wǎng)絡(luò)CE［30］：線蟲神經(jīng)元用網(wǎng)絡(luò)節(jié)點表示，線蟲的神經(jīng)元突觸或其之間的連接用網(wǎng)絡(luò)的連邊表示。

5）郵箱通信網(wǎng)絡(luò)Email（EM）［31］：一種規(guī)模為中型的工廠工人之間的郵箱通信網(wǎng)絡(luò)，工人的郵箱地址用網(wǎng)絡(luò)節(jié)點表示，不同工人之間的郵件往來用網(wǎng)絡(luò)連邊表示。

6）線蟲新陳代謝網(wǎng)絡(luò)Metabolic［32］：秀麗隱桿線蟲的新陳代謝網(wǎng)絡(luò)，節(jié)點表示代謝物，而連邊表示它們之間的相互作用關(guān)系。

7）Infectious（Infect）［33］：2009 年，在柏林科學(xué)美術(shù)館的表演“Infectious：Stay away”中人們面對面行為的網(wǎng)絡(luò)，參與的人員用網(wǎng)絡(luò)節(jié)點表示，人與人之間的溝通用連邊表示。

8）mac-animal［34］：一種62 個成年雌性日本獼猴的支配行為有向網(wǎng)絡(luò)，節(jié)點表示獼猴，網(wǎng)絡(luò)連邊表示左側(cè)節(jié)點對右側(cè)節(jié)點的支配行為。

上述網(wǎng)絡(luò)數(shù)據(jù)集的具體網(wǎng)絡(luò)統(tǒng)計特征參數(shù)如表1 所示。表1 主要包含網(wǎng)絡(luò)節(jié)點數(shù)目（|V|）、網(wǎng)絡(luò)中邊的數(shù)目（|E|）、網(wǎng)絡(luò)平均聚類系數(shù)（C）、網(wǎng)絡(luò)平均節(jié)點度和網(wǎng)絡(luò)平均最短路徑。在后續(xù)網(wǎng)絡(luò)數(shù)據(jù)實驗中，本文設(shè)置訓(xùn)練集合ET中連邊數(shù)目占比為0.9，測試集EP的連邊占比為0.1，此次每個數(shù)據(jù)測試點的結(jié)果均為20 次實驗的平均值。

表1 實驗數(shù)據(jù)集統(tǒng)計信息Table 1 Statistical information of experimental datasets

4 實驗結(jié)果與分析

為驗證資源傳輸節(jié)點拓?fù)渚o密性指標(biāo)的有效性，本文在多個不同類型網(wǎng)絡(luò)中進(jìn)行實驗驗證。在實驗研究中，由于該指標(biāo)主要針對Precision 指標(biāo)，因此重點對Precision 結(jié)果進(jìn)行實驗。具體地，首先實驗分析了不同網(wǎng)絡(luò)中調(diào)節(jié)參數(shù)對TT 的Precision 結(jié)果的影響，然后與現(xiàn)有指標(biāo)進(jìn)行對比，分析TT 的實驗效果和有效性，并給出現(xiàn)實網(wǎng)絡(luò)應(yīng)用時的合理使用建議值。

4.1 Precision 結(jié)果的參數(shù)影響分析

資源傳輸節(jié)點拓?fù)渚o密性指標(biāo)的具體相似性刻畫，利用了參數(shù)β調(diào)節(jié)不同網(wǎng)絡(luò)中資源傳輸節(jié)點拓?fù)渚o密性的影響程度。圖8 顯示了不同網(wǎng)絡(luò)中參數(shù)β對資源傳輸節(jié)點拓?fù)渚o密性指標(biāo)預(yù)測結(jié)果的影響。

圖8 TT 指標(biāo)Precision 結(jié)果隨參數(shù)變化示意圖Fig.8 Schematic diagram of TT index Precision results with parameters changes

可以看出，不同網(wǎng)絡(luò)中參數(shù)β對TT 指標(biāo)的影響較大，在Jazz 和Metabolic 網(wǎng)絡(luò)中隨著β值的增大，在β=0 處迅速增長，說明傳輸節(jié)點拓?fù)渚o密性影響非常明顯。當(dāng)Precision 值達(dá)到較高值后，隨參數(shù)持續(xù)穩(wěn)定，說明此時傳輸節(jié)點拓?fù)渚o密性強(qiáng)度的增大對節(jié)點間相似性的貢獻(xiàn)不再明顯增大；在FWEW 和macanimal 網(wǎng)絡(luò)中，參數(shù)β對TT 指標(biāo)的影響較為復(fù)雜，隨著β值的增大，Precision 值逐漸下降到極點后逐步上升，說明較低的拓?fù)渚o密性強(qiáng)度對于相似性刻畫促進(jìn)作用逐漸下降，而到達(dá)較大強(qiáng)度后會逐漸增強(qiáng)其影響力；USAir 和CE 網(wǎng)絡(luò)相似，在參數(shù)β較小時其Precision 值上升至最大值，然后隨著參數(shù)β的增大呈現(xiàn)輕微下降趨勢；與其他網(wǎng)絡(luò)不同，在Email 網(wǎng)絡(luò)中，在參數(shù)β接近0 時Precision 值呈現(xiàn)急劇上升趨勢，表明較低的傳輸節(jié)點拓?fù)渚o密性強(qiáng)度便可以產(chǎn)生較好的效果。同樣，當(dāng)達(dá)到最高點后，隨著參數(shù)β的增大，呈現(xiàn)快速下降趨勢，也說明了此時傳輸節(jié)點拓?fù)渚o密性強(qiáng)度對其影響正在逐漸降低；在Infectious 網(wǎng)絡(luò)中，當(dāng)參數(shù)β較小時Precision 呈現(xiàn)持續(xù)上升態(tài)勢，到達(dá)最大值頂點后逐步下降，而后又呈現(xiàn)上升，說明傳輸節(jié)點拓?fù)渚o密性強(qiáng)度在不同階段對其影響各異?？傊诙鄶?shù)網(wǎng)絡(luò)中，當(dāng)參數(shù)β較小時，傳輸節(jié)點拓?fù)渚o密性強(qiáng)度對Precision 結(jié)果促進(jìn)作用較強(qiáng)，部分網(wǎng)絡(luò)中提升幅度較大且相對穩(wěn)定，說明傳輸節(jié)點拓?fù)渚o密性對相似度刻畫具有一定的有效性。

4.2 Precision 結(jié)果對比分析

為進(jìn)一步研究分析資源傳輸節(jié)點拓?fù)渚o密性指標(biāo)的有效性和特點，本文選取了8 個相似性指標(biāo)進(jìn)行對比分析。對比指標(biāo)方法主要包括局部相似性和全局相似性指標(biāo)，其中局部相似性指標(biāo)包括共同鄰居指標(biāo)CN、資源分配指標(biāo)RA、AA 指標(biāo)和考慮共同鄰居相互關(guān)系的CAR 指標(biāo)，全局相似性指標(biāo)包括全路徑指標(biāo)Katz、平均通勤時間ACT 和余弦相似性指標(biāo)Cos+，還包括介于局部和全局之間的局部路徑指標(biāo)LP。

表2 為多個不同類型網(wǎng)絡(luò)中TT 指標(biāo)與現(xiàn)有指標(biāo)的Precision 結(jié)果對比情況。其中，（a）可調(diào)參數(shù)α=0.001，（b）可調(diào)參數(shù)α=0.01。

表2 Precision 結(jié)果對比分析Table 2 Comparative analysis of Precision results

從表2 可以看出，相比其他的相似性指標(biāo)，總體上TT 指標(biāo)具有較高的預(yù)測精度，8 個網(wǎng)絡(luò)中有7 個網(wǎng)絡(luò)TT 指標(biāo)的Precision 值最高（見粗體數(shù)字），只有在FWEW 網(wǎng)絡(luò)中排名第三，這在一定程度上說明了資源節(jié)點拓?fù)渚o密性對節(jié)點間相似性刻畫的有效性。作為最簡單的共同鄰居指標(biāo)CN，由于僅考慮了共同鄰居的數(shù)目，其Precision 預(yù)測結(jié)果具有一定的效果，但相比其他相似性方法，大多數(shù)網(wǎng)絡(luò)中CN 的預(yù)測結(jié)果略低（除在Email、Metabolic 和Infectious 網(wǎng)絡(luò)中，CN 的Precision 高于CAR、LP、Katz）。資源分配指標(biāo)RA 通過利用資源分配過程計算節(jié)點間傳輸?shù)馁Y源量進(jìn)行量化節(jié)點間相似性，其復(fù)雜度較低但效果明顯好于一般局部相似性指標(biāo)，尤其是在FWEW、USAir、CE、Metabolic、Infectious 和macanimal 等網(wǎng)絡(luò)中，部分甚至高于全局相似性指標(biāo)LP或Katz。與RA 指標(biāo)類似，AA 指標(biāo)利用共同鄰居的節(jié)點度對共同鄰居進(jìn)行加權(quán)，其效果在多數(shù)網(wǎng)絡(luò)中好于共同鄰居指標(biāo)，部分網(wǎng)絡(luò)如Jazz、USAir、CE、Email、Metabolic 和Infectious 中其結(jié)果好于全局指標(biāo)。CAR 指標(biāo)考慮了共同鄰居之間存在的部分連接對相似性的影響，其效果明顯好于共同鄰居指標(biāo)，但在多數(shù)網(wǎng)絡(luò)中比RA 和AA 效果略差。LP 和Katz 是基于長路徑的相似性指標(biāo)，在多數(shù)網(wǎng)絡(luò)中效果較好且相對穩(wěn)定，尤其是在FWEW、CE、Email 和macanimal 網(wǎng)絡(luò)中效果最好。平均通勤時間ACT 指標(biāo)是基于隨機(jī)游走的相似性指標(biāo)，不過在Precision 衡量標(biāo)準(zhǔn)下，多數(shù)網(wǎng)絡(luò)中普遍較低，許多Precision 值甚至接近于0，這可能是與ACT 指標(biāo)更多地適用于AUC衡量標(biāo)準(zhǔn)，而不適用于Precision 標(biāo)準(zhǔn)。余弦相似性指標(biāo)Cos+同樣是基于隨機(jī)游走的相似性指標(biāo)，相比ACT 其效果有了一定的提升，但與其他相似性指標(biāo)相比，其總體效果較差。ACT 和Cos+的Precision 效果分析結(jié)果表明，部分基于隨機(jī)游走的相似性指標(biāo)更多地傾向于AUC 衡量標(biāo)準(zhǔn)，難以適應(yīng)于Precision衡量標(biāo)準(zhǔn)。在考慮了資源傳輸節(jié)點拓?fù)渚o密性后，TT 指標(biāo)在8 個網(wǎng)絡(luò)中表現(xiàn)普遍較好。多個網(wǎng)絡(luò)中如在Jazz、USAir、Email 和Infectious 中，其Precision 的提高幅度較高，明顯高于其他局部和全局相似性指標(biāo)。在mac-animal 中，TT 指標(biāo)與RA 相似，說明了當(dāng)前網(wǎng)絡(luò)中資源傳輸節(jié)點拓?fù)渚o密性的影響較低，其設(shè)置參數(shù)為0。在現(xiàn)實網(wǎng)絡(luò)的鏈路預(yù)測應(yīng)用中，建議參數(shù)設(shè)置為11.1，各個網(wǎng)絡(luò)中表現(xiàn)普遍較高。此外，本文所提方法時間復(fù)雜度介于共同鄰居指標(biāo)CN 和局部路徑指標(biāo)LP 之間，復(fù)雜度相對較低，可以應(yīng)用于大規(guī)模復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測。

綜上所述，本文方法能夠同時在2 個衡量指標(biāo)AUC 和Precision 下取得較好的效果。AUC 和Precision 作為鏈路預(yù)測2 個重要但角度不同的衡量標(biāo)準(zhǔn)，在一定程度上說明了本文方法的普適性較高。此外，本文方法在8 個不同網(wǎng)絡(luò)的實驗預(yù)測效果相對較高，也驗證了其在不同網(wǎng)絡(luò)數(shù)據(jù)集上的普遍應(yīng)用價值。

5 結(jié)束語

本文根據(jù)傳輸節(jié)點周圍拓?fù)渚o密性對資源傳輸節(jié)點傳輸概率的影響，結(jié)合節(jié)點拓?fù)渚o密性的特點，提出一種基于資源傳輸節(jié)點拓?fù)渚o密性的鏈路預(yù)測方法。從資源傳輸過程分析重要的傳輸節(jié)點，重點研究傳輸節(jié)點周圍拓?fù)潢P(guān)系的量化問題，以節(jié)點聚類系數(shù)為突破點，通過分析當(dāng)前聚類系數(shù)在刻畫資源傳輸節(jié)點有效性中存在的問題，提出相應(yīng)的資源傳輸緊密性量化方法，并基于資源傳輸緊密性，對任意未連邊節(jié)點間的資源傳輸量進(jìn)行刻畫，給出資源傳輸節(jié)點拓?fù)渚o密性指標(biāo)。在多個實際網(wǎng)絡(luò)數(shù)據(jù)中的實驗結(jié)果表明，本文相似性指標(biāo)適合于Precision標(biāo)準(zhǔn)，且相比其他指標(biāo)具有較好的預(yù)測效果。本文方法和思路可以為資源傳輸過程的刻畫提供一種新思路和借鑒。在后續(xù)研究中，將通過探討傳輸路徑有效性對資源傳輸過程的影響，進(jìn)一步豐富和拓展基于資源傳輸過程的鏈路預(yù)測方法。