基于廣義共同鄰居的有向網(wǎng)絡(luò)鏈路預(yù)測方法

趙學(xué)磊，季新生，劉樹新，趙宇

（信息工程大學(xué)，河南 鄭州 450001）

1 引言

近年來，復(fù)雜網(wǎng)絡(luò)逐漸成為探究真實(shí)復(fù)雜系統(tǒng)內(nèi)在機(jī)理的抽象化工具，其重要方向鏈路預(yù)測[1-4]得到了研究人員的持續(xù)關(guān)注。鏈路預(yù)測旨在利用網(wǎng)絡(luò)中已知信息預(yù)測網(wǎng)絡(luò)中的未知連接[5]、未來連接[6]或錯誤連接[7]，是復(fù)雜網(wǎng)絡(luò)與信息科學(xué)交叉融合的重要橋梁，對研究網(wǎng)絡(luò)演化[8-11]、未知鏈路探測[12]等具有巨大的實(shí)際應(yīng)用價值。

當(dāng)前，針對無向網(wǎng)絡(luò)的鏈路預(yù)測研究已取得眾多成果，呂琳媛[3-4]詳細(xì)對比分析了各種方法，并將其歸類為局部相似性、全局相似性指標(biāo)。局部相似性指標(biāo)優(yōu)勢在于計算復(fù)雜度低，適用大規(guī)模網(wǎng)絡(luò)。全局相似性指標(biāo)考慮全網(wǎng)拓?fù)湫畔㈩A(yù)測精度更高，但會付出較高計算代價。然而，前期研究集中于無向網(wǎng)絡(luò)，并且現(xiàn)有局部或全局指標(biāo)均難以直接應(yīng)用于有向網(wǎng)絡(luò)的預(yù)測。

局部相似性指標(biāo)以共同鄰居[13]（CN，common neighbor）指標(biāo)最具代表性，因有向網(wǎng)絡(luò)中連邊具有方向性，使無向共同鄰居衍生多種異構(gòu)形式，傳統(tǒng)預(yù)測方案忽略不同異構(gòu)形式之間差異，極大降低了有向網(wǎng)絡(luò)中的預(yù)測精度，甚至使預(yù)測失去意義。文獻(xiàn)[14]研究發(fā)現(xiàn)，有向網(wǎng)絡(luò)存在特殊的互惠機(jī)制，即節(jié)點(diǎn)傾向于建立反向的連接以回應(yīng)其他節(jié)點(diǎn)對自己的連接，故有向網(wǎng)絡(luò)中存在部分雙向的鏈接，稱之為互惠邊，互惠邊在促進(jìn)連邊產(chǎn)生時通常比單向連邊發(fā)揮更大作用，表示節(jié)點(diǎn)間具有更為緊密的局部結(jié)構(gòu)，而現(xiàn)有指標(biāo)僅利用網(wǎng)絡(luò)單向連邊進(jìn)行預(yù)測。文獻(xiàn)[15]則是通過對網(wǎng)絡(luò)中不同鄰居結(jié)構(gòu)下的連邊概率進(jìn)行統(tǒng)計并作為相似分值，在預(yù)測精度上取得了不錯的效果。Valverde等[16]利用社交平衡理論研究證實(shí)了繁雜的人際關(guān)系將導(dǎo)致社交群體的不同演化方向等。張揚(yáng)夫[17]曾受益于網(wǎng)絡(luò)特性分析，提出一般化相似度指標(biāo)，在共同鄰居基礎(chǔ)上提升了預(yù)測性能。然而，上述理論或方法仍無法使現(xiàn)有指標(biāo)普遍適用于有向網(wǎng)絡(luò)，缺少對局部鄰居異構(gòu)多樣性的量化區(qū)分，且目前算法性能對比基準(zhǔn)多采用無向網(wǎng)絡(luò)局部相似性指標(biāo)，該類指標(biāo)中共同鄰居含義在有向網(wǎng)絡(luò)中已然發(fā)生改變。因此，有向網(wǎng)絡(luò)的鏈路預(yù)測應(yīng)當(dāng)利用網(wǎng)絡(luò)中多樣的局部鄰居異構(gòu)形式進(jìn)行預(yù)測。

針對上述問題，本文提出基于廣義共同鄰居的鏈路預(yù)測算法，通過分析網(wǎng)絡(luò)中共同鄰居有向異構(gòu)體的具體作用，量化不同結(jié)構(gòu)對連邊產(chǎn)生的貢獻(xiàn)程度，并結(jié)合連邊概率將9種局部拓?fù)洚悩?gòu)體進(jìn)行融合，得到廣義上的共同鄰居計算方式，并基于此，針對有向網(wǎng)絡(luò)重定義8種基于CN的相似性指標(biāo)，使其有效利用共同鄰居中有向連邊信息并應(yīng)用于有向網(wǎng)絡(luò)。在12個真實(shí)數(shù)據(jù)集下實(shí)驗(yàn)對比，在AUC及Ranking Score衡量標(biāo)準(zhǔn)下所提方案大幅提升了預(yù)測準(zhǔn)確度，驗(yàn)證了所提方案的有效性。

2 相關(guān)工作介紹

經(jīng)典的CN算法認(rèn)為兩個節(jié)點(diǎn)間若存在更多共同鄰居，則兩節(jié)點(diǎn)更傾向于產(chǎn)生連邊。若引入兩節(jié)點(diǎn)度的影響，可從不同的角度衍生其他相似性指標(biāo)，具體包括Salton[18]指標(biāo)、Jaccard[19]指標(biāo)、S?rensen[20]指標(biāo)、HPI[21]指標(biāo)、HDI[22]指標(biāo)、LHN-I[23]指標(biāo)。另外，考慮共同鄰居節(jié)點(diǎn)的度時有Adamic-Adar[24]（AA）指標(biāo)、資源分配[25]（RA，resource allocation）指標(biāo)。在文獻(xiàn)[26]中，楊瑞琪等將上述指標(biāo)做了有向的變體使其盡可能適用于有向網(wǎng)絡(luò)，一定程度上提高了在有向網(wǎng)絡(luò)中的預(yù)測準(zhǔn)確性，本節(jié)對其改進(jìn)后的有向指標(biāo)進(jìn)行描述，同時為與其他較優(yōu)的有向算法仿真對比，還列出PA[27]、LP[28]、Katz[29]這3種主流指標(biāo)。現(xiàn)對相關(guān)指標(biāo)及其有向方式的定義簡介如下。

CN指標(biāo)：以節(jié)點(diǎn)間共同鄰居數(shù)目衡量連邊可能性，表示為

其中，Γout(x)表示節(jié)點(diǎn)x的出度鄰居節(jié)點(diǎn)，Γin(y)表示節(jié)點(diǎn)y的入度鄰居節(jié)點(diǎn)。

Salton指標(biāo)：在共同鄰居基礎(chǔ)上引入端節(jié)點(diǎn)度信息，與端節(jié)點(diǎn)度之積開方成反比，表示為

Jaccard指標(biāo)：兩節(jié)點(diǎn)鄰居集合中共同鄰居的占比，表示為

S?rensen：共同鄰居與端節(jié)點(diǎn)的度之和之比，表示為

HPI指標(biāo)：共同鄰居與端節(jié)點(diǎn)最小度的比值，表示為

HDI指標(biāo)：與HPI定義相似，表示為

LHN-I指標(biāo)：與Salton定義相似，分母為端節(jié)點(diǎn)度之積（相比之下沒有開根號），表示為

AA指標(biāo)：考慮共同鄰居節(jié)點(diǎn)度信息為共同鄰居節(jié)點(diǎn)賦予權(quán)重，節(jié)點(diǎn)權(quán)重為節(jié)點(diǎn)度的對數(shù)分之一（度越大權(quán)重越?。?，表示為

其中，kout(z)表示共同鄰居z的出度。

RA指標(biāo)：啟發(fā)于資源分配過程，將共同鄰居視為傳遞媒介，傳遞資源量與該節(jié)點(diǎn)的度成反比，表示為

PA指標(biāo)：節(jié)點(diǎn)與連邊概率正比于二者度之積，表示為

LP指標(biāo)：在二階共同鄰居上考慮了三階路徑因素，表示為

Katz指標(biāo)：全局考慮網(wǎng)絡(luò)所有路徑，表示為

3 基于廣義共同鄰居的相似性算法

現(xiàn)有基于共同鄰居的相似性指標(biāo)在有向網(wǎng)絡(luò)應(yīng)用時，其共同鄰居均定義為z∈Γout(x)∩Γin(y)，即節(jié)點(diǎn)對之間通過x→z→y的單向路徑連接的鄰居節(jié)點(diǎn)。而有向網(wǎng)絡(luò)的局部結(jié)構(gòu)遠(yuǎn)復(fù)雜于無向網(wǎng)絡(luò)，連邊方向的改變或互惠邊的存在將使局部結(jié)構(gòu)衍生多種異構(gòu)形式。該共同鄰居定義方式卻缺失多樣的有向異構(gòu)連邊信息，導(dǎo)致基于共同鄰居的預(yù)測指標(biāo)在有向網(wǎng)絡(luò)預(yù)測普遍精度較低。潘永昊等[30]研究了網(wǎng)絡(luò)內(nèi)在結(jié)構(gòu)的動力學(xué)特征，認(rèn)為不同結(jié)構(gòu)對新鏈路的產(chǎn)生效果不同。常圣等[31]研究發(fā)現(xiàn)，應(yīng)用勢理論篩選出有向網(wǎng)絡(luò)中不包含互惠邊的4種可定義勢子圖可顯著提高有向鏈路預(yù)測的精度。

因此，共同鄰居需面向有向網(wǎng)絡(luò)進(jìn)行重新定義，融合有向連邊異構(gòu)的多種局部拓?fù)鋵B邊的貢獻(xiàn)。

3.1 有向異構(gòu)下的廣義共同鄰居融合表示

有向網(wǎng)絡(luò)復(fù)雜性在于，節(jié)點(diǎn)x與y可通過出邊、入邊或互惠邊的形式連接到共同鄰居節(jié)點(diǎn)z，如圖1所示，S1結(jié)構(gòu)即節(jié)點(diǎn)x與y均經(jīng)由互惠邊連接到鄰居節(jié)點(diǎn)z。而z∈Γout(x)∩Γin(y)僅是S9結(jié)構(gòu)的單一表示，缺少對其他異構(gòu)形式的充分利用。該定義中，Γout(x)表示x的出度鄰居節(jié)點(diǎn)，可認(rèn)為在S3、S8、S9結(jié)構(gòu)中x→z的指向性節(jié)點(diǎn)對，Γin(y)表示y的入度鄰居節(jié)點(diǎn)，即S5、S7、S9結(jié)構(gòu)中z→y的指向性節(jié)點(diǎn)對。如此，其余8種異構(gòu)形式的共同鄰居均可通過改變連邊指向進(jìn)行描述，現(xiàn)將廣義共同鄰居（GMCN，generalized mutual common neighbor）定義如下。

定義1廣義共同鄰居：給定有向網(wǎng)絡(luò)G(V,E)，其中，V代表網(wǎng)絡(luò)節(jié)點(diǎn)集合，E代表網(wǎng)絡(luò)中連邊集合，該有向網(wǎng)絡(luò)中兩節(jié)點(diǎn)x與y的廣義共同鄰居定義如式（13）所示。

其中，Γbila(x)表示與節(jié)點(diǎn)x通過互惠邊連接的鄰居集合。

通過廣義共同鄰居定義方式，多樣的有向異構(gòu)形式均得到統(tǒng)一表述，保證了局部信息的充分利用。然而，將其應(yīng)用預(yù)測算法時9類異構(gòu)形式并非簡單的數(shù)目作和。Brzozowski等[32]曾在社交網(wǎng)站W(wǎng)aterCooler研究發(fā)現(xiàn)，好友關(guān)注關(guān)系網(wǎng)絡(luò)下，S7結(jié)構(gòu)的數(shù)量最多，但產(chǎn)生連邊比例最低；S1結(jié)構(gòu)的數(shù)量最少，但連邊比例最高，體現(xiàn)了互惠性在一些社交網(wǎng)絡(luò)演化中的重要作用。但食物鏈網(wǎng)絡(luò)中該現(xiàn)象卻幾乎不存在，而S9結(jié)構(gòu)產(chǎn)生連邊的比例最高，更加符合自然生物的層級捕食現(xiàn)象。

以C.elegans數(shù)據(jù)集為例進(jìn)行具體分析，首先統(tǒng)計該數(shù)據(jù)集中上述9類結(jié)構(gòu)數(shù)目，其次統(tǒng)計各結(jié)構(gòu)下產(chǎn)生連邊x→y的數(shù)目，計算得到各異構(gòu)體獨(dú)自的連邊率，如表1所示。

表1 C.elegans數(shù)據(jù)集不同異構(gòu)體數(shù)目及連邊率統(tǒng)計Table 1 Statistics of different isomers and edge rate of C.elegans

該數(shù)據(jù)集中，結(jié)構(gòu)S8的數(shù)目最多為39 786，基于該種結(jié)構(gòu)的連邊x→y數(shù)目為3 056條，連邊率僅7.70%；而結(jié)構(gòu)S1總數(shù)目僅1 022，其連邊數(shù)目卻可達(dá)到244，連邊率為23.90%。另外，結(jié)構(gòu)S6與S9具有一致數(shù)目，二者連邊率卻相差極大，S9連邊率已接近于S6的6倍，顯然二者對連邊產(chǎn)生的促進(jìn)作用不等，該差異性難以在簡單統(tǒng)計數(shù)目作和的計算方式下有效區(qū)分。且S6結(jié)構(gòu)表現(xiàn)出一種“反向?qū)蛹墶爆F(xiàn)象，恰與原CN指標(biāo)相反，這甚至?xí)种菩逻B邊的產(chǎn)生，數(shù)目越大抑制作用越大。因此，結(jié)構(gòu)數(shù)目并非連邊產(chǎn)生的決定因素，其連邊概率具有更加可信的參考價值。

對有向網(wǎng)絡(luò)中共同鄰居進(jìn)行一般化定義后，通過上述連邊率的分析，得出不同結(jié)構(gòu)促進(jìn)連邊產(chǎn)生的貢獻(xiàn)程度存在差異，因此將各個異構(gòu)形式的連邊概率作為其貢獻(xiàn)程度權(quán)值，通過該貢獻(xiàn)程度權(quán)值將各異構(gòu)體進(jìn)行融合計算，基于此將廣義共同鄰居算法（GMCN）定義如下。

定義2廣義共同鄰居算法：對于給定的有向網(wǎng)絡(luò)G(V,E)，網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)x與y之間的連邊可能性計算為

其中，pk表示9類結(jié)構(gòu)在給定網(wǎng)絡(luò)G(V,E)下的連邊概率，pk計算方式定義如下。

Γj(Γi(x))表示節(jié)點(diǎn)x的二階廣義鄰居，Γj(Γi(x))∩Γout(x)表示節(jié)點(diǎn)x與二階廣義鄰居直接相連的數(shù)目。

3.2 基于廣義共同鄰居的相似性算法

廣義共同鄰居的重新定義，有效涵蓋了有向網(wǎng)絡(luò)連邊的多樣異構(gòu)形式，而現(xiàn)有指標(biāo)中存在的覆蓋不足問題得以解決。將廣義共同鄰居定義應(yīng)用于現(xiàn)有基于共同鄰居的相似性指標(biāo)，重新定義基于廣義共同鄰居的相似性指標(biāo)，將各指標(biāo)重新表示如下。

GMJaccard：對Jaccard指標(biāo)的重定義，將多樣連邊形式的鄰居集合統(tǒng)一表述，量化區(qū)分，具體計算為

GMSalton：Salton指標(biāo)的擴(kuò)展，除應(yīng)用廣義共同鄰居外，端節(jié)點(diǎn)的度同時進(jìn)行了出入度等不同組合的統(tǒng)一表述，通過互惠邊連接的共同鄰居在計算時需采用該節(jié)點(diǎn)的出入度之和，具體計算為

上述公式中kout(x)表示節(jié)點(diǎn)x的出度，kin(x)表示節(jié)點(diǎn)x的入度，kbila(x)表示節(jié)點(diǎn)x的出入度之和，下同。

GMS?renson：S?renson指標(biāo)的擴(kuò)展，與GMSalton的擴(kuò)展方式相同，移除原S?renson指標(biāo)分子中的乘數(shù)2，表示為

GMHPI：HPI指標(biāo)的擴(kuò)展，表示為

GMHDI：HDI指標(biāo)的擴(kuò)展，表示為

GMLHN：LHN指標(biāo)的擴(kuò)展，表示為

GMAA：AA指標(biāo)的擴(kuò)展，對廣義下的共同鄰居的出度進(jìn)行加權(quán)計算，表示為

GMRA：與GMAA類似，是對RA指標(biāo)的擴(kuò)展，表示為

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

CN指標(biāo)因其簡潔性著名，該指標(biāo)及基于CN的算法計算復(fù)雜度為O(N3)[33]?；贕MCN的指標(biāo)計算程序等同于9類有向鄰居異構(gòu)體的加權(quán)分值之和，因pk為各網(wǎng)絡(luò)數(shù)據(jù)集的結(jié)構(gòu)特性，已知的數(shù)據(jù)集網(wǎng)絡(luò)連邊確定，kp為固定值，僅對未知數(shù)據(jù)集首次計算時需統(tǒng)計S1～S9的連邊概率，因此已知網(wǎng)絡(luò)數(shù)據(jù)集計算復(fù)雜度為O(9N3)=O(N3)，繼承了原指標(biāo)低復(fù)雜度的優(yōu)勢。

4 評價指標(biāo)及數(shù)據(jù)集介紹

4.1 評價指標(biāo)

鏈路預(yù)測評價指在公認(rèn)計算準(zhǔn)則下對比不同算法的得分。通常將網(wǎng)絡(luò)數(shù)據(jù)集E劃分為訓(xùn)練集ET及測試集。以訓(xùn)練集數(shù)據(jù)預(yù)測測試集連邊，以測試集和不存在邊集計算評價指標(biāo)得分，相似分值越高，連邊概率越大。本文采用AUC[34]及Ranking Score[35]（RS）兩種主流方式對所提方法進(jìn)行衡量。

AUC可簡單理解為在測試集中隨機(jī)選擇一條邊的分?jǐn)?shù)值比隨機(jī)選擇一條不存在邊的分?jǐn)?shù)值高的概率。從測試集TE和不存在邊集中各隨機(jī)選取一條邊，比較二者的分?jǐn)?shù)值，若測試集中的連邊預(yù)測分?jǐn)?shù)值高于不存在邊集中的預(yù)測分?jǐn)?shù)值累加1（n'表示），若二者相等累加0.5（n''表示）。AUC計算定義為

Ranking Score對所有未連邊按照相似分值大小排序，得到測試集的邊在最終排序中的位置，測試集連邊排名越高，排序分值越小時，說明該算法具有較好預(yù)測性能。以H為未連邊的集合（測試集中和不存在邊集的集合），網(wǎng)絡(luò)中某條測試邊的排序分為

整個系統(tǒng)的排序分可通過遍歷求得，計算方式如下。

4.2 數(shù)據(jù)集介紹

為使實(shí)驗(yàn)驗(yàn)證具有代表性，本文選定12個有向網(wǎng)絡(luò)真實(shí)數(shù)據(jù)集，涵蓋社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、引文網(wǎng)絡(luò)、航空交通網(wǎng)絡(luò)。數(shù)據(jù)集簡介如下。

1)Highschool（HS）[36]：伊利諾伊州一所小型高中男生之間的友誼關(guān)系網(wǎng)絡(luò)。

2)Residence hall（RH）[37]：澳大利亞國立大學(xué)校園217名居民之間的友誼關(guān)系網(wǎng)絡(luò)。

3)Adolescent health（AH）[38]：美國青少年健康關(guān)系網(wǎng)絡(luò)。

4)Physicians（PH）[39]：美國241名醫(yī)生之間的相互朋友關(guān)系網(wǎng)絡(luò)。

5)Usairport（UA）[40]：2010年美國機(jī)場之間的定向航班網(wǎng)絡(luò)。

6)Openflight（OF）[41]：OpenFlights.org項(xiàng)目收集的航班網(wǎng)絡(luò)。

7)C.elegans（CE）[42]：線蟲神經(jīng)元之間的突觸連接關(guān)系網(wǎng)絡(luò)。

8)SciMet（SM）[43]：引用“科學(xué)計量學(xué)”主題的論文引用網(wǎng)絡(luò)。

9)Kohonen（KH）[43]：有關(guān)“自組織映射”主題或“Kohonen”的論文引用網(wǎng)絡(luò)。

10)Wikivote（WV）[44]：維基選票網(wǎng)站的投票選舉關(guān)系網(wǎng)絡(luò)。

11)Chess（CH）[45]：國際象棋7 301個玩家之間的65 053場對戰(zhàn)關(guān)系網(wǎng)絡(luò)。

12)Air traffic control[45]（AC）：美國FAA飛行數(shù)據(jù)中心記錄的規(guī)劃航線網(wǎng)絡(luò)。

預(yù)測實(shí)驗(yàn)時，設(shè)定訓(xùn)練集比例0.9，測試集0.1，每數(shù)據(jù)集進(jìn)行50次獨(dú)立實(shí)驗(yàn)，AUC及Ranking Score結(jié)果取其50次實(shí)驗(yàn)的均值。各數(shù)據(jù)集統(tǒng)計特征如表2所示，包括網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模|V|、連邊數(shù)目|E|、最大出度kout_max、最大入度kin_max、平均度＜k>、集聚系數(shù)C。

表2 數(shù)據(jù)集基本特征參數(shù)Table 2 Basic characteristics of datasets

5 實(shí)驗(yàn)驗(yàn)證及分析

為了驗(yàn)證方法的有效性，針對所提基于廣義共同鄰居的相似性指標(biāo)，本節(jié)對比了現(xiàn)有指標(biāo)有向方式的AUC及Ranking Score，驗(yàn)證該方案整體預(yù)測精度的表現(xiàn)。

5.1 AUC結(jié)果及分析

首先，GMCN指標(biāo)AUC結(jié)果如表3所示。GMCN指標(biāo)的AUC在12數(shù)據(jù)集上均有大幅度提升，在CH數(shù)據(jù)集上相比CN指標(biāo)AUC提升幅度最大，由0.787提高至0.906。整體來看，社交關(guān)系網(wǎng)絡(luò)中提升普遍較高，4種社交網(wǎng)絡(luò)數(shù)據(jù)集的AUC平均提升8.23%，說明該類數(shù)據(jù)集中，錯綜復(fù)雜的局部連邊結(jié)構(gòu)中的潛藏信息可有效提高預(yù)測精度。PA、LP、Katz等指標(biāo)雖在部分網(wǎng)絡(luò)上表現(xiàn)突出，但其AUC值波動較大，如PA指標(biāo)的“富者越富”機(jī)制在社交類網(wǎng)絡(luò)中表現(xiàn)很差，AUC值低于0.7，甚至不及CN指標(biāo)。LP指標(biāo)考慮三階路徑因素，僅在航空、引文類網(wǎng)絡(luò)具有輕微優(yōu)勢；Katz指標(biāo)則考慮了全局路徑信息，約在半數(shù)網(wǎng)絡(luò)上略高于廣義共同鄰居方法，但其代價是付出極高的計算復(fù)雜度。因此，GMCN指標(biāo)與CN復(fù)雜度相當(dāng)，但與PA、LP相比卻具有更高的精度，HS、RH、CE數(shù)據(jù)集上，該類指標(biāo)甚至達(dá)到或高于利用全局路徑信息的Katz指標(biāo)的精度。

表3 AUC實(shí)驗(yàn)結(jié)果對比Table 3 Comparison of AUC results

其次，將廣義共同鄰居定義應(yīng)用現(xiàn)有指標(biāo)，得到基于GMCN的鏈路預(yù)測算法AUC結(jié)果，如表4所示。綜合來看，在12個數(shù)據(jù)集上，重定義指標(biāo)AUC值同樣有大幅提升，各指標(biāo)在社交類網(wǎng)絡(luò)上提升明顯，特別在AH數(shù)據(jù)集上AUC普遍由0.7提升至0.8之上，這一現(xiàn)象體現(xiàn)出社交平衡理論中多樣的正負(fù)關(guān)系的確具有重要價值，現(xiàn)有指標(biāo)僅通過單一的改進(jìn)無法使經(jīng)典指標(biāo)適用于有向網(wǎng)絡(luò)，應(yīng)從結(jié)構(gòu)上區(qū)分不同連邊的異構(gòu)體作用，從而有效提高預(yù)測精度。

表4 基于GMCN的相似性指標(biāo)AUC結(jié)果Table 4 AUC results of similarity index based on GMCN

縱向來看，各指標(biāo)之間差異化并不明顯，GMSalton、GMJaccard、GMS?renson、GMHPI、GMHDI、GMLHN指標(biāo)與GMCN預(yù)測精度相當(dāng)，AUC值保持在較小波動范圍，這也同無向網(wǎng)絡(luò)中該類指標(biāo)預(yù)測效果相符。另外，采用局部節(jié)點(diǎn)度信息的AA、RA指標(biāo)因僅計算到前述S9形式的共同鄰居，疏漏其余8種異構(gòu)鄰居的度信息，除在航空網(wǎng)絡(luò)有較高預(yù)測精度外，其余各類型網(wǎng)絡(luò)不及0.9。而重定義優(yōu)化之后的GMAA及GMRA則通過引入廣義共同鄰居，將數(shù)個網(wǎng)絡(luò)的AUC值提升至0.9以上。

不同數(shù)據(jù)集中GM類指標(biāo)與原指標(biāo)AUC對比如圖2所示。這里直觀地顯示了基于廣義共同鄰居的指標(biāo)有效提升了AUC預(yù)測性能，在多種類型數(shù)據(jù)集的AUC值普遍保持在0.9上下，AH、PH及AC數(shù)據(jù)集上AUC值雖較低，但相比原指標(biāo)，AUC提升近10%。GMCN指標(biāo)相比CN指標(biāo)提升效果最明顯，在上述12個數(shù)據(jù)集上平均AUC提升6.01%，其余幾種指標(biāo)AUC值普遍提高5%左右，GMLHN指標(biāo)稍有提升為0.47%。

圖2 不同數(shù)據(jù)集下GM類指標(biāo)與原指標(biāo)AUC結(jié)果Figure 2 AUC of GM-indexs and original indexs under different datasets

5.2 RS結(jié)果及分析

GMCN與CN的Ranking Score對比結(jié)果在表5中給出。首先從整體來看，GMCN指標(biāo)的預(yù)測性能仍然全面優(yōu)于CN指標(biāo)，并且在社交網(wǎng)絡(luò)上表現(xiàn)突出，相比CN指標(biāo)的RS分值平均降幅為30.9%，低于PA及LP指標(biāo)，在HS及RH等部分?jǐn)?shù)據(jù)集上低于Katz指標(biāo)，再次驗(yàn)證了基于GMCN的相似性指標(biāo)在社交類網(wǎng)絡(luò)的優(yōu)良預(yù)測性能。另外，在UA、CE、WV、CH等數(shù)據(jù)集上GMCN也可與LP、PA、Katz主流指標(biāo)達(dá)到相當(dāng)?shù)姆种?，體現(xiàn)了該類指標(biāo)整體預(yù)測排名準(zhǔn)確性的優(yōu)勢。

同時將GMSalton等8種基于GMCN的指標(biāo)在12個數(shù)據(jù)集下RS分值在表6中進(jìn)行對比。該8種指標(biāo)RS得分普遍遠(yuǎn)低于原指標(biāo)，均在各自網(wǎng)絡(luò)數(shù)據(jù)集上表現(xiàn)出更好預(yù)測效果，同時相比AUC衡量標(biāo)準(zhǔn)對比優(yōu)勢更為突出。如在HS數(shù)據(jù)集上原指標(biāo)RS分值由0.15降至0.09左右，優(yōu)化指標(biāo)的優(yōu)勢提升近40%，社交類網(wǎng)絡(luò)整體降幅明顯。其次，該類指標(biāo)在WV投票網(wǎng)絡(luò)、CH對戰(zhàn)網(wǎng)絡(luò)表現(xiàn)不俗，CH網(wǎng)絡(luò)RS得分由0.14降至0.07。航空網(wǎng)絡(luò)、生物網(wǎng)絡(luò)上，該類指標(biāo)在RS分值勝于原指標(biāo)。GMRA及GMRA相比其他新指標(biāo)降幅稍低，但已優(yōu)于AA及RA指標(biāo)，預(yù)測排名整體有了極大提升。因此，在RS分值評價方式下，基于廣義共同鄰居的相似性指標(biāo)對于各種類型的網(wǎng)絡(luò)數(shù)據(jù)均具有更好的預(yù)測表現(xiàn)。

表5 Ranking Score結(jié)果對比Table 5 Comparison of Ranking Score results

表6 基于GMCN的相似性指標(biāo)Ranking Score結(jié)果Table 6 Ranking Score results of similarity index based on GMCN

各新定義指標(biāo)與原有指標(biāo)在12個數(shù)據(jù)集上的Ranking Score效果對比如圖3所示。對比圖2和圖3可以直觀看到，RS結(jié)果與AUC的提升效果基本相對應(yīng)，其AUC值提升明顯的網(wǎng)絡(luò)的RS分值也更低。9個重定義的新指標(biāo)在各數(shù)據(jù)集中的RS分值均在原指標(biāo)曲線下方，說明數(shù)據(jù)集中的連邊在整體排序中更為靠前。對于4種社交網(wǎng)絡(luò)，GM類指標(biāo)的RS分值平均降低30.9%，Physicians網(wǎng)絡(luò)上RS分值降低了41%，效果最明顯的國際象棋對戰(zhàn)網(wǎng)絡(luò)RS降低達(dá)48.3%。另外，幾類網(wǎng)絡(luò)的降低普遍在15%～20%，同樣證實(shí)了基于廣義共同鄰居的相似性指標(biāo)在RS評價指標(biāo)下對不同網(wǎng)絡(luò)的適用性。

圖3 不同數(shù)據(jù)集下GM類指標(biāo)與原指標(biāo)Ranking Score結(jié)果Figure 3 Ranking score of GM-indexs and original indexs under different datasets

6 結(jié)束語

本文針對有向網(wǎng)絡(luò)中共同鄰居存在多種有向異構(gòu)形式，而現(xiàn)有指標(biāo)缺少對多種異構(gòu)形式下局部連邊信息有效綜合利用問題，提出了有向網(wǎng)絡(luò)中廣義共同鄰居的定義，并基于廣義共同鄰居重定義了基于CN的8種相似性指標(biāo)。以結(jié)構(gòu)連邊概率作為權(quán)重衡量促進(jìn)連邊的貢獻(xiàn)程度使其針對多種類型網(wǎng)絡(luò)具有普適性。十余個真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集仿真表明，廣義共同鄰居方式充分融合利用了共同鄰居多種異構(gòu)體間的局部結(jié)構(gòu)信息，在AUC、Ranking Score衡量指標(biāo)下，各新定義指標(biāo)預(yù)測性能得到了大幅提升。此外該類方法繼承了CN算法低復(fù)雜度的優(yōu)勢，適用較大規(guī)模網(wǎng)絡(luò)鏈路預(yù)測。