祝丁愷，鐵治欣,2，洪順賀

(1.浙江理工大學(xué)信息學(xué)院，浙江 杭州 310018； 2.浙江理工大學(xué)科技與藝術(shù)學(xué)院，浙江 紹興 312369)

0 引 言

現(xiàn)實世界中的很多復(fù)雜系統(tǒng)可以抽象成復(fù)雜網(wǎng)絡(luò)模型進行分析研究，在對這些復(fù)雜網(wǎng)絡(luò)研究過程中，數(shù)據(jù)的缺失和不準(zhǔn)確是無法避免的。如何利用現(xiàn)有的數(shù)據(jù)來挖掘缺失的信息以及錯誤的數(shù)據(jù)是當(dāng)下需要解決的問題。近年來，鏈路預(yù)測被廣泛關(guān)注[1]。鏈路預(yù)測可以是預(yù)測復(fù)雜網(wǎng)絡(luò)中當(dāng)前不相連的節(jié)點之間連接的可能性，也可以是預(yù)測復(fù)雜網(wǎng)絡(luò)中確實存在的連邊但尚未被探測到，亦或是預(yù)測當(dāng)前復(fù)雜網(wǎng)絡(luò)存在的連邊中哪些是錯誤的連邊[2]。鏈路預(yù)測不僅在好友推薦、標(biāo)簽分類等實際場景中有著豐富的應(yīng)用，而且對網(wǎng)絡(luò)的結(jié)構(gòu)與演化[3-5]以及網(wǎng)絡(luò)中節(jié)點的相似性[6]刻畫起著重要的推動作用。

在鏈路預(yù)測的研究中，網(wǎng)絡(luò)的層次結(jié)構(gòu)是一個較少受到關(guān)注的點?，F(xiàn)實世界中的網(wǎng)絡(luò)通常具有一定的層次組織形式。層次隨機圖(HRG)作為一種可以從網(wǎng)絡(luò)數(shù)據(jù)中推斷出層次結(jié)構(gòu)的模型，不僅可以用于網(wǎng)絡(luò)中社團的挖掘，還可用來預(yù)測網(wǎng)絡(luò)中缺失的鏈接。Clauset等人[7]利用數(shù)學(xué)上的統(tǒng)計推斷工具(極大似然法[8]和蒙特卡洛抽樣算法[9-10])將層次隨機圖模型與觀測的網(wǎng)絡(luò)數(shù)據(jù)進行擬合來對網(wǎng)絡(luò)中的缺失鏈路進行預(yù)測。該方法不僅具有較高的預(yù)測準(zhǔn)確度，而且與現(xiàn)有的一些鏈路預(yù)測算法相比，更適用于一般的網(wǎng)絡(luò)結(jié)構(gòu)。

近年來，層次隨機圖模型在鏈路預(yù)測中的應(yīng)用被廣泛關(guān)注。為了提高層次隨機圖模型在二分網(wǎng)絡(luò)當(dāng)中的預(yù)測精度，2011年，Chua等人[11]提出了適合二分網(wǎng)絡(luò)的層次隨機圖模型(BHRG)。同年，Allen等人[12]提出了適用于加權(quán)網(wǎng)絡(luò)的層次隨機圖模型(wHRG)，同時針對那些邊具有多重屬性的加權(quán)網(wǎng)絡(luò)，他們又進一步提出了基于多重屬性加權(quán)網(wǎng)絡(luò)的層次隨機圖模型(vHRG)。2016年，田甜等人[13]將層次隨機圖模型應(yīng)用到腦網(wǎng)絡(luò)的鏈路預(yù)測中，實驗也達到了較為理想的效果。然而，利用該模型進行鏈路預(yù)測時具有較高的時間復(fù)雜度，這就導(dǎo)致現(xiàn)階段該模型只能適用于小規(guī)模網(wǎng)絡(luò)的鏈路預(yù)測，這大大限制了該模型的適用范圍。因此，尋找一種既能減少時間開銷又能準(zhǔn)確反應(yīng)網(wǎng)絡(luò)的真實結(jié)構(gòu)的方案已迫在眉睫。

本文深入研究基于層次隨機圖模型的鏈路預(yù)測過程，針對層次隨機圖模型的初始化階段，提出一種新的層次隨機圖初始化方案。該方案主要分為2個步驟：1)為網(wǎng)絡(luò)中的邊排序，本文引入節(jié)點相似性指標(biāo)(LHN-I指標(biāo))，利用該指標(biāo)對網(wǎng)絡(luò)中的邊進行排序；2)構(gòu)造層次隨機圖模型，本文設(shè)計一種將網(wǎng)絡(luò)中的頂點插入到層次隨機圖模型中的規(guī)則，當(dāng)將排序好的邊的頂點放入層次隨機圖模型中時，該規(guī)則能夠保證頂點在層次隨機圖模型中的唯一性?；谠摲桨笜?gòu)造出的層次隨機圖模型相較于現(xiàn)有的方案具有更佳的表現(xiàn)。

1 層次隨機圖模型與鏈路預(yù)測

1.1 HRG模型的基本概念

設(shè)真實網(wǎng)絡(luò)是一個具有n個頂點的簡單無向圖G，層次隨機圖可以看作是一種樹形圖D(本質(zhì)是一個二叉樹)，它由內(nèi)部節(jié)點、內(nèi)部邊以及葉子節(jié)點構(gòu)成。其中，G中的n個頂點對應(yīng)于D中的n片葉子節(jié)點。任意2片葉子節(jié)點i、j之間由D的n-1個內(nèi)部節(jié)點中的某一個r聯(lián)系起來，此內(nèi)部節(jié)點r也稱為i和j的最低共同祖先。內(nèi)部節(jié)點與內(nèi)部節(jié)點之間由一條內(nèi)部邊相連，共有n-2條這樣的內(nèi)部邊。每個內(nèi)部節(jié)點r會被賦予一個概率值pr，并且規(guī)定任意2個葉子節(jié)點i、j的連接概率pij就等于它們的最低公共祖先所對應(yīng)的概率值p即pij=pr。那么，由樹形圖D和概率值pr的集合(D,{pr})定義了一個層次隨機圖。圖1展示了一個含有7個頂點的簡單無向網(wǎng)絡(luò)及其對應(yīng)的某個層次隨機圖模型。

圖1 一個簡單無向網(wǎng)絡(luò)和其對應(yīng)的某個層次隨機圖模型

1.2 層次隨機圖與網(wǎng)絡(luò)的擬合

(1)

其中，Lr、Rr表示以r為內(nèi)部節(jié)點的左子樹和右子樹的葉子節(jié)點個數(shù)；Er表示以r為內(nèi)部節(jié)點的左子樹的葉子節(jié)點與右子樹的葉子節(jié)點之間反映在網(wǎng)絡(luò)中的真實連邊數(shù)。似然值越高說明該層次隨機圖與給定的網(wǎng)絡(luò)G擬合得越好。對于一個確定的層次隨機圖，利用極大似然法得出pr的最大似然估計值為：

(2)

那么，引入此最大似然估計值的樹形圖的似然為：

(3)

1.2.1 MCMC算法

為了尋找最適合觀察網(wǎng)絡(luò)的一個或多個層次隨機圖模型，使用遍歷比較的方法計算量極其龐大。為此，使用馬爾科夫鏈蒙特卡洛(MCMC)算法層次隨機圖空間集合進行抽樣，使得每個層次隨機圖抽取的頻次正比于該層次隨機圖的最大似然值。MCMC算法的步驟為：

Step1隨機構(gòu)造一個初始層次隨機圖來初始化馬爾科夫鏈。

Step2構(gòu)造馬爾科夫鏈，隨機選擇層次隨機圖中的一個內(nèi)部節(jié)點r，利用子樹重排技術(shù)改變該內(nèi)部節(jié)點的子樹位置以產(chǎn)生一個新的層次隨機圖D′。

Step3運行蒙特卡洛方法[9]直至平衡，每當(dāng)馬爾科夫鏈上產(chǎn)生新的層次隨機圖D′后，需利用Metropolis-Hastings(M-H)標(biāo)準(zhǔn)[15]來接受或者拒絕它。如果L(D′)-L(D)≥0,則接受D→D′的轉(zhuǎn)換，否則以概率L(D′)/L(D)判斷是否接受D′作為當(dāng)前樹形圖，如果不接受這種轉(zhuǎn)換，樹形圖保持原樣。M-H標(biāo)準(zhǔn)能夠確保馬爾科夫鏈?zhǔn)諗科胶狻?/p>

Step4當(dāng)馬爾科夫鏈趨于平穩(wěn)后，每隔一定的時間采樣一次，得到最佳層次隨機圖樣本。

1.2.2 子樹重排

為了能夠運行MCMC算法，需要找到一種能夠?qū)湫螆D集合中的每個元素聯(lián)系起來的方法。簡單來說，為了構(gòu)造一條馬爾科夫鏈，需要通過某種技術(shù)能夠?qū)?dāng)前形態(tài)的樹形圖轉(zhuǎn)換成另一種形態(tài)，這就是子樹重排技術(shù)。對于一個給定的樹形圖，它的任意一個內(nèi)部節(jié)點(非根節(jié)點)都由3部分組成：左子樹、右子樹以及兄弟子樹。而子樹重排技術(shù)就是對某個選定的內(nèi)部節(jié)點的子樹位置進行重新排列，如圖2所示。

圖2 子樹重排

對于一個選定的內(nèi)部節(jié)點，有2種方法可以重新排序這些子樹。以圖2(a)為例，假設(shè)粗框標(biāo)記的內(nèi)部節(jié)點r為當(dāng)前被隨機選中的內(nèi)部節(jié)點，該內(nèi)部節(jié)點的左子樹為a，右子樹為b，兄弟子樹為c。從此狀態(tài)出發(fā)，通過對選中的內(nèi)部節(jié)點的子樹之間的位置進行交換可以產(chǎn)生圖2(b)與圖2(c)這2種狀態(tài)。事實上，這3種狀態(tài)可以相互轉(zhuǎn)換。

1.3 基于HRG模型的鏈路預(yù)測算法

使用層次隨機圖模型進行鏈路預(yù)測的算法如下：

Step1導(dǎo)入網(wǎng)絡(luò)數(shù)據(jù)，構(gòu)造初始層次隨機圖并初始化馬爾科夫鏈。首先讀取網(wǎng)絡(luò)中數(shù)據(jù)，為層次隨機圖分配合適的內(nèi)存空間，通過選擇一個隨機的初始樹形圖初始化馬爾科夫鏈。

Step2運行MCMC算法直至平衡。從初始樹形圖D出發(fā)，在馬爾科夫鏈上的每一步都包括：1)隨機選取一個內(nèi)部節(jié)點，在對其子樹重排所產(chǎn)生的2種形態(tài)中隨機選擇一種以生成一個新的樹形圖D′；2)根據(jù)Metropolis-Hastings標(biāo)準(zhǔn)接受或拒絕新產(chǎn)生的樹形圖。

Step3抽樣。當(dāng)馬爾科夫鏈平衡時，從馬爾科夫鏈生成的樹形圖中每隔一定時間抽樣一次(可手動設(shè)置抽樣次數(shù))。

Step4鏈路預(yù)測并排序。對于還沒有已知連接的每對頂點(i,j)，計算它在每個被抽樣的樹形圖中的連接概率pij，然后求得pij的平均值。按照pij的大小進行從大到小排序，排在前面的說明連接的可能性越大。

Step5計算AUC[16]。利用AUC指標(biāo)對預(yù)測的結(jié)果進行分析，最終得出AUC值的大小，AUC值越高，說明算法的預(yù)測精度越好，當(dāng)AUC值>0.5時，說明算法要比隨機方法更好。

2 一種層次隨機圖模型初始化算法

在1.3節(jié)中介紹的利用層次隨機圖進行鏈路預(yù)測的算法中，步驟2的花費時間在整個算法花費時間中占據(jù)著較多的分量，也就是說從初始層次隨機圖迭代到收斂后的層次隨機圖需要花費大量的時間。通過研究發(fā)現(xiàn)，利用現(xiàn)有的方法構(gòu)造出的初始層次隨機圖的似然值往往與收斂后的層次隨機圖的似然值相差甚遠。在小規(guī)模的網(wǎng)絡(luò)當(dāng)中，這種隨機的構(gòu)造方法能夠花費較短的時間從初始似然值過渡到最優(yōu)似然值，然而，隨著網(wǎng)絡(luò)規(guī)模的增大，從初始狀態(tài)到最優(yōu)狀態(tài)所花費的迭代次數(shù)將呈指數(shù)上升。因此，為了減少從初始層次隨機圖到最優(yōu)層次隨機圖之間的迭代次數(shù)，本文提出一種層次隨機圖模型的初始化方法。

2.1 算法介紹

層次隨機圖模型是一種層級結(jié)構(gòu)，對于該模型的初始化，本文采用一種自下而上的構(gòu)造方法。其核心思想為：按序提取網(wǎng)絡(luò)中每條邊的2個頂點，將這2個頂點作為樹形圖的葉子節(jié)點并有選擇地使用內(nèi)部節(jié)點與它們關(guān)聯(lián)。在這之中涉及3個關(guān)鍵技術(shù)點：1)如何按序提取網(wǎng)絡(luò)中的邊，也就是說，使用什么準(zhǔn)則給網(wǎng)絡(luò)中的所有邊進行排序；2)如何判斷當(dāng)前邊的2個頂點是否重復(fù)，也就是說，應(yīng)該避免相同的頂點重復(fù)出現(xiàn)在樹形圖之中；3)該采用何種策略將被提取的邊的2個頂點放入到樹形圖的葉子節(jié)點當(dāng)中去。

對于第一個技術(shù)點，本文引入了相似性指標(biāo)的概念，利用相似性指標(biāo)作為權(quán)重的計算方法，為網(wǎng)絡(luò)中的所有邊按照權(quán)重的得分從大到小進行排序。對于第二個技術(shù)點，本文采用紅黑樹這一數(shù)據(jù)結(jié)構(gòu)，每當(dāng)提取邊的2個頂點時，判斷這2個頂點是否在紅黑樹當(dāng)中，并且將不在紅黑樹中的頂點插入到紅黑樹當(dāng)中。這樣，每次提取邊的頂點的過程中就可以判斷頂點是否重復(fù)出現(xiàn)。由于紅黑樹的查找、插入的時間復(fù)雜度為O(logn)，所以花費的時間較少。對于第三個技術(shù)點，本文總結(jié)了將邊的頂點插入到葉子節(jié)點的過程中遇到的所有情況，并對各自的情況給出了詳細(xì)的解決方案。設(shè)每條邊的頭頂點和尾頂點分別為Vx,Vy，頂點Vi對應(yīng)于層次隨機圖中的葉子節(jié)點為leafi，葉子節(jié)點leafi的最遠祖先節(jié)點為maxAncestori，頂點Vi的度稱為ki，被訪問過的頂點集合為{Vi}，那么將邊的頂點插入到葉子節(jié)點的過程中遇到的各個情況以及對應(yīng)的解決方案如下：

1)Vx?{Vi}且Vy?{Vi} 。

將Vx、Vy放入集合{Vi}中并生成葉子節(jié)點leafx和leafy，用一個內(nèi)部節(jié)點連接leafx和leafy。

2)Vx?{Vi}且Vy∈{Vi} 。

將Vx放入集合{Vi}中并生成葉子節(jié)點leafx，考慮如下情況：①如果kx>ky，那么首先找到maxAncestory，將maxAncestory與leafx用一個內(nèi)部節(jié)點進行連接；2)如果kx≤ky且leafy是其父節(jié)點的左孩子，那么首先用一個內(nèi)部節(jié)點連接leafx與leafy的父節(jié)點的右孩子，其次將leafy的父節(jié)點的右孩子替換成此內(nèi)部節(jié)點；③如果kx≤ky且leafy是其父節(jié)點的右孩子，那么首先用一個內(nèi)部節(jié)點連接leafx與leafy的父節(jié)點的左孩子，其次將leafy的父節(jié)點的左孩子替換成此內(nèi)部節(jié)點。

3)Vx∈{Vi}且Vy?{Vi} 。

將Vy放入集合{Vi}中并生成葉子節(jié)點leafy，考慮如下情況：①如果kx

4)Vx∈{Vi}且Vy∈{Vi} 。

若maxAncestorx與maxAncestory不是同一個，那么將leafx和maxAncestory用一個內(nèi)部節(jié)點進行連接，否則不進行任何操作。

結(jié)合上述3個技術(shù)點的解決方案，整個層次隨機圖模型的初始化算法如下：

1)計算網(wǎng)絡(luò)中每條邊的權(quán)重得分；

2)將網(wǎng)絡(luò)中邊的權(quán)重值按照從大到小進行排序；

3)選取當(dāng)前權(quán)重最大的那條邊，判斷該邊的2個頂點是否已出現(xiàn)在樹形圖中，并按照上述策略將需要被操作的頂點插入到層次隨機圖當(dāng)中；

4)重復(fù)步驟3，直至所有邊都提取完畢；

5)為每個內(nèi)部節(jié)點計算pr。

2.2 指標(biāo)的選擇

在2.1節(jié)中提到，為了初始化樹形圖，本文引入了相似性指標(biāo)的概念，然而相似性指標(biāo)眾多，不同的相似性指標(biāo)對于初始層次隨機圖的構(gòu)造會產(chǎn)生不同的影響。因此，為了探究采用哪個指標(biāo)構(gòu)造出的初始樹形圖的似然值更高，本文采用了6種不同的相似性指標(biāo)并構(gòu)造出了6種不同的初始層次隨機圖，這6種指標(biāo)如表1所示。

表1 相似性指標(biāo)

2.3 實驗分析

2.3.1 數(shù)據(jù)集與實驗環(huán)境

為了探究融入了哪一種指標(biāo)所構(gòu)造出的層次隨機圖模型似然值最高。本文分別使用FWFB、C.elegans和Metabolic這3個真實網(wǎng)絡(luò)進行實驗。實驗中所有被使用到的網(wǎng)絡(luò)都進行了無向化處理。表2展示了3個網(wǎng)絡(luò)的信息。

表2 數(shù)據(jù)集

FWFB是佛羅里達海灣雨季的食物鏈網(wǎng)絡(luò)[21]，其中每個頂點代表一種生物，每條邊代表生物之間的捕食關(guān)系。該網(wǎng)絡(luò)存在31條具有互惠關(guān)系的邊，在實驗過程中，這些互惠邊會被忽略。

C.elegans是線蟲的神經(jīng)元網(wǎng)絡(luò)[22]，其中每個頂點代表線蟲的神經(jīng)元，每條邊代表神經(jīng)元突觸或者間隙連接。該網(wǎng)絡(luò)是有向網(wǎng)絡(luò)，在實驗過程中會忽略邊的有向性。

Metabolic是線蟲的代謝網(wǎng)絡(luò)[23]，其中每個頂點代表代謝物(如蛋白質(zhì))，每條邊代表代謝物之間的相互作用。在該網(wǎng)絡(luò)中，由于某些代謝物可以自我迭代，因此存在一些自循環(huán)的邊，在實驗的過程中這些自循環(huán)的邊會被主動剔除。

所有實驗都是在基于4 GB內(nèi)存的Linux內(nèi)核和英特爾酷睿i3-2100 CPU的Deepin操作系統(tǒng)平臺上進行的。

2.3.2 實驗分析

在對樹形圖求對數(shù)似然的時候，其值通常為負(fù)數(shù)，為了方便在圖表中觀察似然值的結(jié)果，本實驗對其取相反數(shù)，因此似然值的相反數(shù)的值越小，說明初始HRG模型構(gòu)造得越理想。

圖3展示了基于不同相似性指標(biāo)的HRG模型的構(gòu)造算法在3種真實網(wǎng)絡(luò)下的表現(xiàn)情況。其中橫坐標(biāo)表示網(wǎng)絡(luò)的類型，縱坐標(biāo)表示在特定網(wǎng)絡(luò)下，利用不同的相似性指標(biāo)所構(gòu)造出的初始樹形圖的似然值的大小。從圖中可以明顯發(fā)現(xiàn)，融入了相似性指標(biāo)的初始HRG模型構(gòu)造方法比隨機構(gòu)造初始HRG模型有著更好的初始似然值。在這些相似性指標(biāo)當(dāng)中，基于LHN-I指標(biāo)構(gòu)造出來的HRG模型有著更好的初始似然值。

圖3 不同指標(biāo)在3個網(wǎng)絡(luò)中的表現(xiàn)

將原始構(gòu)造方法與基于LHN-I指標(biāo)的構(gòu)造方法單獨做對比，如圖4所示，在初始HRG模型似然值的結(jié)果上，基于LHN-I指標(biāo)的構(gòu)造方法比原始構(gòu)造方法在FWFB網(wǎng)絡(luò)、C.elegans網(wǎng)絡(luò)、Metabolic網(wǎng)絡(luò)中分別提升了25%、18%、42%左右。

圖4 基于LHN-I指標(biāo)構(gòu)造的初始HRG模型

因此，基于LHN-I的HRG模型構(gòu)造方法在一定程度上提高了初始HRG模型的質(zhì)量。

在1.3節(jié)中介紹的利用層次隨機圖進行鏈路預(yù)測的步驟中，現(xiàn)有的方法是采用隨機構(gòu)造初始層次隨機圖的方式來初始化馬爾科夫鏈，為了探究提高初始層次隨機圖的質(zhì)量能否提升MCMC算法的收斂速度，利用上述的3個網(wǎng)絡(luò)進行了3次實驗。對于每次實驗，分別使用隨機算法構(gòu)造初始層次隨機圖和使用初始化算法構(gòu)造初始層次隨機圖的方式來初始化馬爾科夫鏈，之后各自運行MCMC算法。

在FWFB網(wǎng)絡(luò)中，如圖5所示，若采用層次隨機圖初始化算法構(gòu)造出來的層次隨機圖模型來初始化馬爾科夫鏈，MCMC算法大約經(jīng)過了2 min逐漸趨于穩(wěn)定；而若使用隨機構(gòu)造出來的層次隨機圖來初始化馬爾科夫鏈，那么MCMC算法則需要大約8 min才逐漸趨于穩(wěn)定。因此，在使用了初始化算法的情況下，MCMC算法收斂所需的時間相較于隨機的方法大約提升了75%。

圖5 在FWFB網(wǎng)絡(luò)中2種算法的實驗對比

如圖6所示，在C.elegans網(wǎng)絡(luò)中，若采用層次隨機圖初始化算法構(gòu)造出來的層次隨機圖模型來初始化馬爾科夫鏈，MCMC算法收斂速度相對較快，大約經(jīng)過了0.5 min，MCMC算法逐漸趨于穩(wěn)定；而若使用隨機構(gòu)造出來的層次隨機圖來初始化馬爾科夫鏈，那么MCMC算法則需要3 min左右的時間才逐漸趨于穩(wěn)定。因此，在使用了初始化算法的情況下，MCMC算法收斂所需的時間相較于隨機的方法大約提升了83%。

圖6 在C.elegans網(wǎng)絡(luò)中2種算法的實驗對比

如圖7所示，在Metabolic網(wǎng)絡(luò)中，若采用層次隨機圖初始化算法構(gòu)造出來的層次隨機圖模型來初始化馬爾科夫鏈，MCMC算法大約經(jīng)過了3 min逐漸趨于穩(wěn)定；而若使用隨機構(gòu)造出來的層次隨機圖來初始化馬爾科夫鏈，那么MCMC算法則需要大約6 min才逐漸趨于穩(wěn)定。因此，在使用了初始化算法的情況下，MCMC算法收斂所需的時間相較于隨機的方法大約提升了50%。

圖7 在Metabolic網(wǎng)絡(luò)中2種算法的實驗對比

3 鏈路預(yù)測實驗與分析

3.1 N-HRG鏈路預(yù)測算法的步驟

結(jié)合新提出的HRG模型初始化方法，本文提出一種改進的基于層次隨機圖模型的鏈路預(yù)測算法(N-HRG)。N-HRG鏈路預(yù)測算法的流程如下：

Step1導(dǎo)入網(wǎng)絡(luò)數(shù)據(jù)，利用提出的HRG模型初始化方法構(gòu)造一個優(yōu)化的初始層次隨機圖來初始化馬爾科夫鏈；

Step2運行MCMC算法，直至馬爾科夫鏈平衡；

Step3抽樣；

Step4鏈路預(yù)測并排序；

Step5計算AUC[16]。

3.2 數(shù)據(jù)集的劃分與實驗環(huán)境

為了探究本算法的預(yù)測性能，依然使用2.3節(jié)中的3個網(wǎng)絡(luò)實例(FWFB網(wǎng)絡(luò)、Metabolic網(wǎng)絡(luò)以及Celegans網(wǎng)絡(luò))并將給定的網(wǎng)絡(luò)中的邊的集合分成2部分，一部分作為訓(xùn)練集，另一部分作為測試集。訓(xùn)練集是作為鏈路預(yù)測算法的輸入，而測試集是用來與鏈路預(yù)測算法的輸出進行比較。在劃分?jǐn)?shù)據(jù)集的過程中，需要確保訓(xùn)練集中的邊具有連通性，即不存在孤立的節(jié)點。數(shù)據(jù)集將按照5種不同的比例進行劃分，比例分別為10%和90%、20%和80%、30%和70%、40%和60%、50%和50%，前者為測試集所占的比例，后者為訓(xùn)練集所占的比例。

本次測試的這3種網(wǎng)絡(luò)的運行環(huán)境為：基于Linux內(nèi)核的Deepin操作系統(tǒng)，運行內(nèi)存為4 GB，CPU采用Inter Core i3-2100 3.1 GHz。

3.3 評價指標(biāo)

本文使用AUC指標(biāo)作為衡量鏈路預(yù)測精度的標(biāo)準(zhǔn)，AUC是指ROC曲線(Receiver Operating Characteristic Curve)下的面積[24]。按照定義，需要首先畫出ROC曲線，然后計算出ROC曲線所覆蓋的面積，最終得到AUC的值。事實上，對于樣本很多的情況，一般采用抽樣比較的方式得到一個近似的AUC而不需要繪制出ROC曲線。利用抽樣比較的方式，AUC可以被定義為：

(4)

其中，n代表獨立實驗的總次數(shù)，n′代表n次實驗當(dāng)中測試集中的邊的得分值大于不存在的邊的得分值的次數(shù)，n″代表測試集中的邊的得分值等于不存在的邊的得分值的次數(shù)。也就是說，獨立進行n次實驗，在每次實驗中，從測試集中和不存在的邊中各隨機抽取一條邊，比較兩者的得分值。如果測試集中的邊的得分值大于不存在的邊的得分值，那么加1分，如果測試集中的邊的得分值等于不存在的邊的得分值，那么加0.5分。

從式(4)可以看出，如果測試集中的邊的得分與不存在的邊的得分是隨機產(chǎn)出的，那么AUC的值近似為0.5。因此，如果一個鏈路預(yù)測算法的AUC>0.5，那么就說明該鏈路預(yù)測算法要比隨機的方法更好。

3.4 實驗分析

將本文方法與其他一些基于相似性指標(biāo)(Salton指標(biāo)[19]、Jaccard指標(biāo)[18]、CN指標(biāo)[17]以及ACT指標(biāo)[25])的鏈路預(yù)測算法進行比較，將訓(xùn)練網(wǎng)絡(luò)的密度作為輸入，輸出為各個算法在對應(yīng)訓(xùn)練網(wǎng)絡(luò)密度下的AUC大小。在實驗過程中，AUC值越高，預(yù)測精度越高。

在FWFB網(wǎng)絡(luò)中，如圖8所示，N-HRG方法在5個不同的訓(xùn)練網(wǎng)絡(luò)密度中的預(yù)測精度始終明顯高于其他方法，并且即使網(wǎng)絡(luò)數(shù)據(jù)在丟失了50%的情況下，N-HRG方法的AUC值還能保持在0.8附近，這意味著在網(wǎng)絡(luò)丟失一半細(xì)節(jié)的情況下，N-HRG方法還能保持較高的預(yù)測精度。值得注意的是，當(dāng)訓(xùn)練集的密度為50%時，基于Salton指標(biāo)的鏈路預(yù)測算法的AUC值反而低于0.5，這說明其預(yù)測精度要比隨機方法的差。

圖8 不同鏈路預(yù)測算法在FWFB網(wǎng)絡(luò)中的對比

如圖9所示，在C.elegans網(wǎng)絡(luò)中，在不同的訓(xùn)練集密度的測試下，這5種方法的預(yù)測精度都要比隨機方法的好。其中，除了基于ACT指標(biāo)的鏈路預(yù)測算法，其他算法的預(yù)測精度都隨著訓(xùn)練集密度的增加而增加，并且N-HRG算法在5個不同的訓(xùn)練網(wǎng)絡(luò)密度中的預(yù)測精度始終高于其他算法。當(dāng)訓(xùn)練集密度在80%和90%時，基于CN指標(biāo)的鏈路預(yù)測算法的預(yù)測精度與N-HRG算法的差距較小。當(dāng)訓(xùn)練集密度在50%時，N-HRG算法依然能保持著較高的預(yù)測精度，而其他算法只能得到較低的預(yù)測精度。

圖9 不同鏈路預(yù)測算法在C.elegans網(wǎng)絡(luò)中的對比

如圖10所示，在Metabolic網(wǎng)絡(luò)中，N-HRG算法在5個不同的訓(xùn)練集密度中的預(yù)測精度始終高于基于Salton指標(biāo)、Jaccard指標(biāo)以及ACT指標(biāo)的鏈路預(yù)測算法。在訓(xùn)練網(wǎng)絡(luò)的密度為50%和60%時，N-HRG算法的預(yù)測精度還優(yōu)于基于CN指標(biāo)的鏈路預(yù)測算法的預(yù)測精度。但當(dāng)訓(xùn)練網(wǎng)絡(luò)的密度大于80%時，基于CN指標(biāo)的鏈路預(yù)測算法的預(yù)測精度略微高于N-HRG算法的預(yù)測精度。值得注意的是，當(dāng)訓(xùn)練集密度在50%時，N-HRG算法的AUC值依然保持在0.8以上，而其他方法都位于0.8以下。

圖10 不同鏈路預(yù)測算法在Metabolic網(wǎng)絡(luò)中的對比

從整體來看，N-HRG算法的預(yù)測性能在實驗中有著較好的表現(xiàn)，并且當(dāng)網(wǎng)絡(luò)缺失大量細(xì)節(jié)的情況下，依然能保持較好的預(yù)測精度，這對一些實際應(yīng)用有著較大的幫助。除此之外，N-HRG方法在一些特定的網(wǎng)絡(luò)下(如食物鏈網(wǎng)絡(luò))的預(yù)測性能有著巨大的優(yōu)勢。

4 結(jié)束語

為了解決層次隨機圖模型在初始化階段效率不高的問題，本文提出了一種新的層次隨機圖模型初始化方法。在層次隨機圖的初始化階段，引入LHN-I指標(biāo)為網(wǎng)絡(luò)中的邊排序，并且設(shè)計了一種將網(wǎng)絡(luò)頂點插入到模型中的方法，使得構(gòu)造出的層次隨機圖模型具有較高的似然，這就間接減少了MCMC算法的迭代次數(shù)，進而降低了鏈路預(yù)測的時間消耗，提高了對更大規(guī)模網(wǎng)絡(luò)進行鏈路預(yù)測的可行性。除此之外，通過對3個真實網(wǎng)絡(luò)的鏈路預(yù)測實驗，結(jié)果表明基于N-HRG的鏈路預(yù)測算法相比于基于節(jié)點相似性的鏈路預(yù)測算法有著更好的預(yù)測精度。