曹志威，樊志杰，，王青楊，韓偉力，李 欣

1(公安部第三研究所 信息安全技術(shù)部，上海 200120) 2(復(fù)旦大學(xué) 計算機科學(xué)技術(shù)學(xué)院，上海 201203) 3(四川大學(xué) 計算機學(xué)院，成都 610207) 4(中國人民公安大學(xué) 信息網(wǎng)絡(luò)安全學(xué)院，北京 100038)

1 引 言

在自然界中，大量的個體間存在著形形色色的相互關(guān)系，并且這種關(guān)系構(gòu)成了多種多樣的復(fù)雜系統(tǒng)[1].在復(fù)雜系統(tǒng)的研究中，通常用網(wǎng)絡(luò)結(jié)構(gòu)來描述這些系統(tǒng)間的相互關(guān)系，即網(wǎng)絡(luò)中的節(jié)點表示個體，網(wǎng)絡(luò)中的連邊表示個體間的相互作用[2-4].一般情況下，這類網(wǎng)絡(luò)是由不同個體間基于各自的規(guī)則所生成，并且在結(jié)構(gòu)上呈現(xiàn)出某些相似但又具有差異性的網(wǎng)絡(luò)特征屬性，同時在功能上不同的網(wǎng)絡(luò)具有各自不同的特征，通常將具有上述相關(guān)性質(zhì)的網(wǎng)絡(luò)統(tǒng)稱為復(fù)雜網(wǎng)絡(luò)[5-7].復(fù)雜網(wǎng)絡(luò)中一個重要的研究方向是鏈路預(yù)測，該項研究一方面有助于分析網(wǎng)絡(luò)中結(jié)構(gòu)性與功能性的聯(lián)系，另一方面也是分析網(wǎng)絡(luò)演化機制的重要工具[8].

鏈路預(yù)測主要是指：通過分析、挖掘網(wǎng)絡(luò)中的已知信息，包括節(jié)點、連邊等拓撲結(jié)構(gòu)屬性，構(gòu)建相應(yīng)的預(yù)測模型，進而預(yù)測網(wǎng)絡(luò)中尚未存在連邊的節(jié)點間產(chǎn)生連邊的概率有多大[9,10].現(xiàn)階段，鏈路預(yù)測在統(tǒng)計物理和計算機領(lǐng)域均有較豐富的研究成果.其中，在統(tǒng)計物理領(lǐng)域，研究者們主要是依據(jù)網(wǎng)絡(luò)的某種結(jié)構(gòu)特征來提出基于某種假設(shè)的網(wǎng)絡(luò)連邊生成機制，進而產(chǎn)生網(wǎng)絡(luò)中的節(jié)點連邊概率，并對其排序[11,12].在計算機領(lǐng)域，鏈路預(yù)測通常被認定為一種二分類問題，主要將網(wǎng)絡(luò)中不存在連邊的節(jié)點分為“會產(chǎn)生連邊”和“不會產(chǎn)生連邊”兩類[13，14].

近年來，鏈路預(yù)測在理論層面和實際應(yīng)用中均體現(xiàn)出較高的研究價值，因此受到各個領(lǐng)域研究者的廣泛關(guān)注.在理論層面上[15]，鏈路預(yù)測主要用于發(fā)現(xiàn)和研究網(wǎng)絡(luò)結(jié)構(gòu)的演化過程，由于不同類型的網(wǎng)絡(luò)通常存在不同的網(wǎng)絡(luò)演化機制，鏈路預(yù)測作為一種衡量不同演化機制好壞的比較方式發(fā)揮了重要的作用.通過該種方式了解網(wǎng)絡(luò)的演化機制，能夠使研究者們更深入的了解網(wǎng)絡(luò)拓撲結(jié)構(gòu)隨時間的演變過程和規(guī)律，進而能夠更精準的描述網(wǎng)絡(luò)未來的結(jié)構(gòu)特征.通常研究者們在分析真實網(wǎng)絡(luò)結(jié)構(gòu)時經(jīng)常會遇到數(shù)據(jù)不完整、數(shù)據(jù)假陽性等問題，在此鏈路預(yù)測就可以成為優(yōu)化原網(wǎng)絡(luò)結(jié)構(gòu)的重要工具.在實際應(yīng)用方面[16,17]，鏈路預(yù)測可以用于查找尚未被發(fā)現(xiàn)的網(wǎng)絡(luò)結(jié)構(gòu)，同時在開展其他相關(guān)研究前對網(wǎng)絡(luò)結(jié)構(gòu)進行精煉.由于復(fù)雜網(wǎng)絡(luò)是一種對復(fù)雜系統(tǒng)的抽象表示，在其構(gòu)建過程中由于時間、空間、實驗數(shù)據(jù)獲取方式上的局限性，網(wǎng)絡(luò)結(jié)構(gòu)中的較多重要信息還尚未被檢測到，導(dǎo)致了已知的網(wǎng)絡(luò)結(jié)構(gòu)中存在大量的缺失連邊信息.同時，由于復(fù)雜系統(tǒng)本身也在隨著時間不斷的演化，相應(yīng)的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)自然也是動態(tài)變化的.因此，依據(jù)已知的網(wǎng)絡(luò)結(jié)構(gòu)信息對其缺失信息進行有效的預(yù)測不僅能較準確的理解復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)，而且能為后續(xù)的相關(guān)實驗研究提供指導(dǎo).

在鏈路預(yù)測的研究中，基于節(jié)點相似性的鏈路預(yù)測是普適性最廣的預(yù)測算法.依據(jù)算法中考慮網(wǎng)絡(luò)拓撲結(jié)構(gòu)范圍的大小，通常將鏈路預(yù)測算法分為3類，分別是：局部性鏈路預(yù)測、全局性鏈路預(yù)測和半局部性鏈路預(yù)測.

1)局部性鏈路預(yù)測[18，19]：該類算法僅僅考慮網(wǎng)絡(luò)中每對節(jié)點間的局部拓撲信息.該類算法的優(yōu)勢是：時間復(fù)雜度較低、網(wǎng)絡(luò)大小的可擴展性較高；劣勢是：預(yù)測準確性較低、網(wǎng)絡(luò)類型的魯棒性較差.相對而言該類算法適合于大范圍的網(wǎng)絡(luò).

2)全局性鏈路預(yù)測[20，21]：該類算法主要關(guān)注網(wǎng)絡(luò)的全局拓撲信息.該類算法的優(yōu)勢是：預(yù)測準確性與網(wǎng)絡(luò)類型的魯棒性相對較高；劣勢是：時間復(fù)雜度較高、網(wǎng)絡(luò)大小的可擴展性較差.

3)半局部性鏈路預(yù)測[22，23]：該類算法依據(jù)的網(wǎng)絡(luò)拓撲信息介于局部和全局之間.該類算法時間復(fù)雜度相對較低、網(wǎng)絡(luò)類型的魯棒性相對較高，但其預(yù)測準確性在一些網(wǎng)絡(luò)上要優(yōu)于全局性鏈路預(yù)測算法.

近些年，深度學(xué)習(xí)由于其能夠自動學(xué)習(xí)數(shù)據(jù)中的深層次特征，因此其在模式識別、圖像檢測、目標(biāo)追蹤等領(lǐng)域得到了很好的應(yīng)用[24,25].正是考慮到自編碼器模型具有善于挖掘各種高維數(shù)據(jù)相關(guān)特征的能力，同時結(jié)合鏈路預(yù)測的性質(zhì)，本文提出一種基于降噪自編碼器(Denoising Autoencoder，DA)[26,27]的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測算法.本文的工作主要體現(xiàn)在以下3個方面：1)構(gòu)造一種適合于復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測的降噪自編碼器訓(xùn)練網(wǎng)絡(luò)結(jié)構(gòu)；2)依據(jù)降噪自編碼器具有數(shù)據(jù)恢復(fù)的能力，提出一種基于降噪自編碼器的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測模型；3)本文針對大量不同的網(wǎng)絡(luò)類型進行了對比實驗，結(jié)果表明DA算法與其他經(jīng)典的鏈路預(yù)測算法相比在預(yù)測準確性和魯棒性上均有明顯的優(yōu)勢.

2 背景介紹

2.1 問題描述及評價指標(biāo)

2.1.1 問題描述

在復(fù)雜網(wǎng)絡(luò)的研究中，通常將網(wǎng)絡(luò)抽象為圖，進而通過圖論的方式來研究網(wǎng)絡(luò)[28].在實際應(yīng)用中，通常將一個具體的網(wǎng)絡(luò)抽象成為節(jié)點集V和鏈路集E構(gòu)成的圖，即表示為G(V,E)，其中網(wǎng)絡(luò)的節(jié)點數(shù)為N=|V|，連邊數(shù)為M=|E|.鏈路預(yù)測問題通常不考慮網(wǎng)絡(luò)中的自環(huán)和多連接的情況，即僅考慮簡單無向圖.定義U是網(wǎng)絡(luò)中最多可能連邊組成的集合，即包含N(N-1)/2條連邊，其中集合U-E即表示不存在連邊組成的集合.鏈路預(yù)測中通常將網(wǎng)絡(luò)中的鏈路Er劃分為兩個部分，即訓(xùn)練集EV和測試集EV，其中ET∪EV=E且ET∩EV=?.鏈路預(yù)測的最終目標(biāo)是在集合U-ET中查找出將來產(chǎn)生的鏈路和真實缺失的鏈路.

2.1.2 評價指標(biāo)

鏈路預(yù)測主要有以下兩種評價指標(biāo)，即精確度(Precision)和AUC，這兩個指標(biāo)均是從不同角度來衡量鏈路預(yù)測算法的預(yù)測效果[29,30].

Precision指的是在不同的鏈路預(yù)測算法中，前L條鏈路中有多少條在測試集中，即被準確預(yù)測.假設(shè)通過相應(yīng)算法得到的預(yù)測結(jié)果中，排名在前L條的鏈路中，有m條存在于測試集中，則Precision定義為：

(1)

AUC指的是從測試集中隨機選擇一條鏈路的預(yù)測分數(shù)值高于U-E中不存在鏈路預(yù)測分數(shù)值的可能性.其計算方式是每次從測試集EV中隨機選擇一條鏈路，緊接著再從不存在鏈路U-E中隨機選擇一條鏈路，然后比較這兩條鏈路預(yù)測分數(shù)值的大小.假設(shè)在某次鏈路預(yù)測的實驗中，總共獨立比較了n次，其中測試集預(yù)測分數(shù)值較高的次數(shù)有n1次，兩者預(yù)測分數(shù)值相等的情況有n2次，則其AUC值定義為：

(2)

為了更好的衡量算法的整體性能，本文同步采用了基于Precision和AUC評估結(jié)果的準確度排序指標(biāo)，該指標(biāo)是一種綜合的、魯棒性較強的度量方式，主要用于評估算法在各種場景下的整體性能.對于每個網(wǎng)絡(luò)，該指標(biāo)要求所有被測試的算法基于Precision和AUC評價指標(biāo)的試驗結(jié)果進行降序排列.另外，本文還計算了反映每個鏈路預(yù)測算法在所有網(wǎng)絡(luò)上整體性能的平均排序指標(biāo)(Mean-ranking)，其形式化定義如下：

(3)

其中l(wèi)代表被測試網(wǎng)絡(luò)的個數(shù)，Ri代表一個被測試算法在第i個網(wǎng)絡(luò)中的排序.

2.2 相關(guān)技術(shù)研究

2.2.1 自編碼器

自編碼器(Autoencoder，AE)是一種用于提取特征的人工神經(jīng)網(wǎng)絡(luò)，其目標(biāo)是盡可能地將輸入內(nèi)容復(fù)現(xiàn)到輸出內(nèi)容[31，32].傳統(tǒng)自編碼器主要包括輸入層、隱藏層和輸出層，如圖1所示.

圖1 基本自編碼器網(wǎng)絡(luò)結(jié)構(gòu)Fig.1 Basic autoencoder network structure

該類自編碼器模型主要包括兩個部分：編碼網(wǎng)絡(luò)和解碼網(wǎng)絡(luò).其形式化定義如下：樣本數(shù)x經(jīng)過函數(shù)f編碼得到特征向量y，然后經(jīng)過解碼函數(shù)g得到輸出z：

y=f(x)，z=g(y)

(4)

函數(shù)f與g包含若干層如下變換：

xout=σ(Wxin+b)

(5)

其中σ是神經(jīng)網(wǎng)絡(luò)的激活函數(shù)，p={W,b}是網(wǎng)絡(luò)的參數(shù).自編碼器的損失函數(shù)定義為輸出z與輸入x之間的誤差：

Loss=d(z,x)

(6)

其中d是某種距離度量.通過梯度下降等優(yōu)化方法，使得損失函數(shù)取到局部最優(yōu)值或者全局最優(yōu)值，此時自動編碼器能夠最好地重構(gòu)原始數(shù)據(jù)，特征向量y可認為是提取的原始數(shù)據(jù)的特征.

2.2.2 降噪自編碼器

降噪自編碼器(DA)是自編碼器的一個拓展.其原理是對樣本數(shù)據(jù)集做隨機損壞處理，以輸入加了噪聲的數(shù)據(jù)x′去計算y′并得到重構(gòu)數(shù)據(jù)z′，經(jīng)過多次迭代修正網(wǎng)絡(luò)參數(shù)，這樣DA就學(xué)習(xí)了如何恢復(fù)被損壞的數(shù)據(jù)[33-35].損壞處理通常的方法是對一部分輸入數(shù)據(jù)隨機置零，或加入高斯噪聲.本實驗中采取以一定概率p使得輸入矩陣的元素值等于0：

(7)

這樣訓(xùn)練得出的降噪自編碼器能夠用來補全丟失數(shù)據(jù).鑒于此，本模型適合用于恢復(fù)復(fù)雜網(wǎng)絡(luò)中缺失的鏈路信息.

3 相關(guān)工作

本文選擇了7個經(jīng)典的鏈路預(yù)測算法進行對比分析，包括4個局部性鏈路預(yù)測算法，2個全局性鏈路預(yù)測算法，1個類局部性鏈路預(yù)測算法.接下來，將對下文中用到的各個對比算法進行形式化定義[8]：

x和y分別代表網(wǎng)絡(luò)中的任意兩個節(jié)點；Γ(x)和Γ(y)分別代表節(jié)點x和y的鄰居組成的集合；kx和ky分別代表節(jié)點x和y的度數(shù).

1)共同鄰居指標(biāo)(common neighbors，CN)：CN指標(biāo)是最簡單和通用的一種網(wǎng)絡(luò)節(jié)點相似性指標(biāo)，該指標(biāo)直接統(tǒng)計網(wǎng)絡(luò)中兩個節(jié)點間共同鄰居的總數(shù).該指標(biāo)假設(shè)網(wǎng)絡(luò)中兩個節(jié)點間的共同鄰居越多，這兩個節(jié)點間產(chǎn)生連邊的概率就越大.CN指標(biāo)定義為：

(8)

2)Salton指標(biāo)被稱為余弦相似性指標(biāo)，其定義為：

(9)

3)優(yōu)先鏈接指標(biāo)(preferential attachment，PA)：PA指標(biāo)是一種來源于無標(biāo)度網(wǎng)絡(luò)優(yōu)先連接機制的相似性指標(biāo).假設(shè)任意節(jié)點與節(jié)點vx之間產(chǎn)生連邊的概率與節(jié)點vx的度數(shù)成正相關(guān).該指標(biāo)定義為：

(10)

4)Cannistraci-Hebb指標(biāo)(CH)：CH指標(biāo)是局部的、無參數(shù)的，該指標(biāo)假設(shè)如果兩個節(jié)點之間的共同鄰居間是緊密相連的，那么這兩個節(jié)點間產(chǎn)生連邊的可能性就更大.即：

(11)

其中，γ(z)代表節(jié)點z的鄰居的子集.|γ(z)|代表節(jié)點z的局部社團度數(shù).

5)局部隨機游走指標(biāo)(local random walk，LRW)：假設(shè)一個粒子在t時刻從節(jié)點vx出發(fā)，并且定義在t+1時刻這個粒子剛好游走到網(wǎng)絡(luò)中節(jié)點vy的概率為Πyx(t)，那么其游走狀態(tài)的演化方程為：

Πx(t+1)=PTΠx(t)，t≥0

(12)

其中，Πx(0)表示的是一個N×1的向量，并且該向量第x個元素為1，其他元素均為0，即Πx(0)=ex.令qx為網(wǎng)絡(luò)中每個節(jié)點的初始資源分布，那么其t步隨機游走的過程可以描述為：

(13)

6)平均通勤時間指標(biāo)(average commute time，ACT)：假設(shè)一個隨機游走粒子從網(wǎng)絡(luò)中節(jié)點vx游走到節(jié)點vy需要的平均游走步數(shù)為m(x，y)，那么定義網(wǎng)絡(luò)中節(jié)點vx與節(jié)點vy的平均通勤時間為：

n(x，y)=m(x，y)+m(y，x)

(14)

上述方程的解可通過求解網(wǎng)絡(luò)中拉普拉斯矩陣L(L=D-A)的偽逆L+得到，即：

(15)

該指標(biāo)假設(shè)兩個節(jié)點之間的連接概率與其之間的平均通勤時間成正比，即：

(16)

由于M為網(wǎng)絡(luò)中連邊的總數(shù)，其對每對不相鄰的節(jié)點均相同，因此上述公式中將其忽略.

7)Katz指標(biāo)(Katz)：Katz指標(biāo)計算時考慮了兩個節(jié)點間網(wǎng)絡(luò)的所有路徑.該指標(biāo)定義為：

(17)

4 基于降噪自編碼器的鏈路預(yù)測算法

4.1 DA算法的實現(xiàn)機制

本文引入的降噪自編碼器模型通過網(wǎng)絡(luò)結(jié)構(gòu)與損失函數(shù)的構(gòu)造，在訓(xùn)練階段已經(jīng)學(xué)習(xí)并具有了數(shù)據(jù)降噪恢復(fù)的能力，進入到預(yù)測階段本模型將完整的訓(xùn)練集數(shù)據(jù)輸入到已訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)中，進而得到預(yù)測并修復(fù)整個復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集的目的.

結(jié)合鏈路預(yù)測問題研究，本文將鄰接矩陣A的每一個列向量作為輸入項傳送到降噪自編碼器中.降噪自編碼器輸入層中的每個單元代表原網(wǎng)絡(luò)中的某個節(jié)點與目標(biāo)節(jié)點之間的連接狀態(tài).對于輸入向量中被加入噪聲的那些節(jié)點，本文的目標(biāo)是將噪聲去掉，因此輸出的目標(biāo)向量應(yīng)該盡量和未加噪聲的數(shù)據(jù)相近.這樣降噪自編碼器會根據(jù)不同目標(biāo)節(jié)點的輸入而改變神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)，但是隱藏層中神經(jīng)元數(shù)是固定的，同時各個神經(jīng)元之間的參數(shù)是共享的，輸出層是一個維度和原網(wǎng)絡(luò)的節(jié)點數(shù)量相同的向量，因此能達到從低維數(shù)據(jù)中恢復(fù)高維信息的目的，進而得到預(yù)測復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的目的.

4.2 DA算法的步驟與實現(xiàn)

4.2.1 數(shù)據(jù)集劃分

本文中的實驗將網(wǎng)絡(luò)圖的邊劃分為訓(xùn)練集和測試集兩部分，劃分出90%的邊用于對網(wǎng)絡(luò)的訓(xùn)練，剩下10%的邊用于對預(yù)測結(jié)果的驗證.為了得到不同的網(wǎng)絡(luò)結(jié)構(gòu)，按照10%的比例隨機將訓(xùn)練集中的邊置零得到一個輸入數(shù)據(jù)x′，并將這個過程重復(fù)多次.

4.2.2 訓(xùn)練與預(yù)測網(wǎng)絡(luò)結(jié)構(gòu)構(gòu)建

構(gòu)建一個適合鏈路預(yù)測的降噪自編碼器首先要確定訓(xùn)練網(wǎng)絡(luò)的結(jié)構(gòu)，其次需要通過誤差反向傳播算法對網(wǎng)絡(luò)結(jié)構(gòu)的相關(guān)參數(shù)進行調(diào)節(jié)，最后需要借助訓(xùn)練好的網(wǎng)絡(luò)結(jié)構(gòu)進行鏈路預(yù)測.

1)訓(xùn)練網(wǎng)絡(luò)結(jié)構(gòu)

定義A為圖G的鄰接矩陣，則aij表示第i個節(jié)點與第j個節(jié)點之間的連接關(guān)系.aij=1表示節(jié)點vi和節(jié)點vj之間存在連接，aij=0表示節(jié)點vi和節(jié)點vj之間尚未存在連接.在鏈路預(yù)測研究中，通常將網(wǎng)絡(luò)劃分為訓(xùn)練集ET和測試集EV.考慮到降噪自編碼器的實現(xiàn)機制，本文擬將訓(xùn)練集中的部分鏈路進行噪聲加入的處理，然后通過網(wǎng)絡(luò)結(jié)構(gòu)與損失函數(shù)的構(gòu)造實現(xiàn)降噪的目的，進而使模型逐步具有數(shù)據(jù)修復(fù)與預(yù)測的能力.例如，假設(shè)本算法將訓(xùn)練集中存在的某條鏈路(Vi,Vj)∈ET劃分到測試集，即鄰接矩陣中對應(yīng)的元素aij被置零，則認為元素aij已加入噪聲.

2) 網(wǎng)絡(luò)參數(shù)調(diào)節(jié)

網(wǎng)絡(luò)的訓(xùn)練采用誤差反向傳播算法，誤差反向傳播算法是深度學(xué)習(xí)中應(yīng)用最廣泛的訓(xùn)練方法之一.同時，該算法是基于梯度下降的原理對目標(biāo)進行調(diào)整，進而通過尋找誤差曲面的最小值來對訓(xùn)練網(wǎng)絡(luò)中的節(jié)點之間是否會產(chǎn)生連接進行學(xué)習(xí).

3) 預(yù)測網(wǎng)絡(luò)結(jié)構(gòu)

網(wǎng)絡(luò)結(jié)構(gòu)訓(xùn)練完成后即進入到鏈路預(yù)測的階段.為了能夠預(yù)測鄰接網(wǎng)絡(luò)訓(xùn)練集中每個節(jié)點與該目標(biāo)節(jié)點之間是否會產(chǎn)生連接，本文提出的算法中將神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)中輸出層的神經(jīng)元個數(shù)增加到了N.

4.2.3 DA算法的實現(xiàn)

為了給訓(xùn)練集中的數(shù)據(jù)添加噪聲，本文將隨機選定訓(xùn)練集中10%的元素重新置零，緊接著將該加了噪聲的訓(xùn)練集輸入到降噪自編碼器，這樣能通過加噪聲和反復(fù)訓(xùn)練，達到讓降噪自編碼器學(xué)習(xí)如何去除噪聲的目的，也就是降噪的功能.最后將整個訓(xùn)練集當(dāng)作是加入了10%噪聲的數(shù)據(jù)，輸入到訓(xùn)練好的降噪自編碼器中，并用測試集進行驗證，進而得到模型的表現(xiàn).總的來說，將加入噪聲的訓(xùn)練集看成時間t時圖G的連接狀態(tài)，則完整的數(shù)據(jù)可以被認為是網(wǎng)絡(luò)在t+δt時的演化狀態(tài)，降噪自編碼器將從加入噪聲的數(shù)據(jù)中學(xué)習(xí)出無噪聲的原始數(shù)據(jù)集，從而達到預(yù)測復(fù)雜網(wǎng)絡(luò)演化狀態(tài)的目的.

實驗環(huán)節(jié)中，本文將某個節(jié)點對其他所有節(jié)點的連接狀態(tài)作為其向量描述，通過自動編碼和解碼獲得該節(jié)點對其他所有節(jié)點產(chǎn)生連接的可能性，遍歷完所有節(jié)點后將產(chǎn)生一個大小為n×n的打分矩陣.下面形式化定義這一過程：

1)訓(xùn)練階段

通過具有兩層編碼函數(shù)和兩層解碼函數(shù)的自編碼器可獲得預(yù)測向量z′i，如圖2所示.

圖2 降噪自編碼器網(wǎng)絡(luò)結(jié)構(gòu)Fig.2 Denoising autoencoder network structure

2)預(yù)測階段

對于一個具有n個節(jié)點的真實網(wǎng)絡(luò)，本文將v1…vn對應(yīng)的向量x1…xn分別輸入到模型中，將產(chǎn)生對應(yīng)的預(yù)測向量z1…zn，最終可還原成n×n的預(yù)測矩陣.

另外，用于訓(xùn)練鏈路預(yù)測降噪自編碼器的損失函數(shù)為：

Loss=‖z′-x‖2

(18)

主要用于確定訓(xùn)練次數(shù)和激活函數(shù)等神經(jīng)網(wǎng)絡(luò)中的超參數(shù)，同時用隨機梯度下降(SGD)法來優(yōu)化損失函數(shù)，最終用訓(xùn)練好的網(wǎng)絡(luò)驗證結(jié)果.

3)驗證階段

本文算法流程圖如圖3所示.

圖3 本文算法流程圖Fig.3 Algorithm flowchart

本文以最終的打分矩陣為依據(jù)計算本模型預(yù)測的準確率和AUC值.為了避免劃分數(shù)據(jù)集時產(chǎn)生的偶然誤差，本文對每個數(shù)據(jù)集進行了100次獨立的實驗，即對準確率和AUC值分別取平均值.

5 實驗結(jié)果分析

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

本文選擇了7個經(jīng)典的真實網(wǎng)絡(luò)進行對比實驗，主要包括生物網(wǎng)絡(luò)、社交網(wǎng)絡(luò)和技術(shù)網(wǎng)絡(luò)等.其中，F(xiàn)ootball網(wǎng)絡(luò)反映了參加世界錦標(biāo)賽足球隊間的競爭關(guān)系；FWMW網(wǎng)絡(luò)和FWFW網(wǎng)絡(luò)分別反映了各自屬地生物間的食物鏈關(guān)系；C.elegans網(wǎng)絡(luò)反映了線蟲中神經(jīng)元間的相關(guān)作用關(guān)系；Crime網(wǎng)絡(luò)描述了犯罪分子間的相互作用關(guān)系；Polblog是一種描述美國政治博客間超鏈接關(guān)系的網(wǎng)絡(luò)；ATC反映了美國各機場或航空中心間的飛行關(guān)系.

表1顯示了本文中所有被測試網(wǎng)絡(luò)的拓撲特征，其中N和|E|分別代表網(wǎng)絡(luò)中節(jié)點和鏈路總數(shù)；代表網(wǎng)絡(luò)平均度數(shù)；代表網(wǎng)絡(luò)平均最短路徑長度；C代表網(wǎng)絡(luò)平均簇系數(shù)；γ代表網(wǎng)絡(luò)同配系數(shù)；H代表網(wǎng)絡(luò)度的異質(zhì)性.

表1 測試網(wǎng)絡(luò)數(shù)據(jù)集拓撲特征Table 1 Topological characteristics of test network dataset

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

為了驗證DA算法在鏈路預(yù)測問題上的預(yù)測準確性和魯棒性，本文選擇了7個經(jīng)典的鏈路預(yù)測算法進行對比分析.同時，為了驗證DA算法對不同訓(xùn)練集大小的魯棒性，本文進行了面向不同訓(xùn)練集比例的對比試驗，其中訓(xùn)練集連邊數(shù)占網(wǎng)絡(luò)總連邊數(shù)的比例記為ξ.另外，為了權(quán)衡每對算法預(yù)測結(jié)果間的統(tǒng)計性差異，表2、表4、圖1和圖2中的所有結(jié)果均是基于100次試驗的平均值.

表3 訓(xùn)練集劃分比例為90%的預(yù)測準確性排序值Table 3 Precision-ranking evaluation of ξ=90%

表4 訓(xùn)練集劃分比例為90%的AUC評估值Table 4 AUC evaluation of ξ=90%

參數(shù)設(shè)置方面，本文中降噪自編碼器的編碼層和解碼層均為2層，學(xué)習(xí)率設(shè)置為5e-4，每一層的激活函數(shù)均為sigmoid.另外，數(shù)據(jù)全部經(jīng)過算法訓(xùn)練一次記為一個周期(epoch)，本算法中設(shè)定epoch=50.同時，每個epoch周期訓(xùn)練中使用的batch大小設(shè)定為1，即每次訓(xùn)練中輸入一個反映任一選定節(jié)點與其他節(jié)點連接狀態(tài)的向量.

1)預(yù)測準確性分析

表2分別顯示了當(dāng)ξ=90%時，所有對比算法在7個真實網(wǎng)絡(luò)中的預(yù)測準確性以及其對應(yīng)的排序值.表2中的倒數(shù)第二行和倒數(shù)第一行分別顯示了被測試算法在所有網(wǎng)絡(luò)上的平均預(yù)測準確性和基于預(yù)測準確性的平均排序.另外，在表2中，所有被測試的網(wǎng)絡(luò)依據(jù)網(wǎng)絡(luò)規(guī)模由小到大的順序從上到下依次排序，所有被測試的算法依據(jù)對應(yīng)的平均排序由小到大的順序從左到右依次排序.同時，每個網(wǎng)絡(luò)中表現(xiàn)最好的算法高亮顯示.

在表2中，可以發(fā)現(xiàn)DA算法在7個網(wǎng)絡(luò)中的6個表現(xiàn)最好，并且其橫跨所有網(wǎng)絡(luò)的平均預(yù)測準確性為0.2181，顯著高于其他算法.另外，為了更科學(xué)的評估算法的整體預(yù)測效果，本文引入了預(yù)測準確性排序指標(biāo).該指標(biāo)能夠衡量各個算法在所有網(wǎng)絡(luò)中的平均排序，反映了各個算法的整體預(yù)測能力.從表2中最后一行可以發(fā)現(xiàn)DA算法的平均排序為1.143，同樣優(yōu)于其他算法.相對而言，經(jīng)典的全局性Katz算法和局部性CH算法的平均排序分別是3.571和4.000，分別排在第2和第3的位置.其他算法在Precision指標(biāo)下的表現(xiàn)就稍遜色，DA算法與它們相比優(yōu)勢更明顯.

表4分別顯示了當(dāng)ξ=90%時，所有對比算法在7個真實網(wǎng)絡(luò)中的AUC評估值以及其對應(yīng)的排序值.該表的結(jié)構(gòu)分布形式與表2類似.在表4中，可以發(fā)現(xiàn)DA、Katz和PA算法基于AUC評價指標(biāo)的預(yù)測結(jié)果屬于第1梯隊，其他的算法屬于第2梯隊.其中，DA算法在7個網(wǎng)絡(luò)中的3個表現(xiàn)最好，并且其橫跨所有網(wǎng)絡(luò)的平均AUC評估值為0.7856，依然優(yōu)于其他算法.另外，從表4中最后一行可以發(fā)現(xiàn)DA算法基于AUC評估指標(biāo)的平均排序為2.571，與Katz算法并列排名第一.

表3和表5詳細統(tǒng)計了所有被測試算法在7個測試網(wǎng)絡(luò)中基于Precision和AUC評估指標(biāo)的平均排序結(jié)果.

表5 訓(xùn)練集劃分比例為90%的AUC排序值Table 5 AUC-ranking evaluation of ξ=90%

綜上所述，本文提出的DA算法一方面能夠較好的從殘缺數(shù)據(jù)中學(xué)習(xí)到有用的潛在特征信息，另一方面能夠有效的降低不同網(wǎng)絡(luò)結(jié)構(gòu)對算法的影響.然而，其他算法僅僅考慮了網(wǎng)絡(luò)的某類結(jié)構(gòu)特征，針對不同網(wǎng)絡(luò)類型的預(yù)測能力上不夠穩(wěn)定.因此，與這些經(jīng)典的鏈路預(yù)測算法相比，本文提出的DA算法對不同網(wǎng)絡(luò)類型的整體預(yù)測能力上優(yōu)勢明顯.

2)魯棒性分析

為了驗證DA算法對訓(xùn)練集所占比例ξ的魯棒性，本文對其進行了魯棒性分析，并設(shè)定ξ={0.3，0.5，0.7，0.9}.圖4和圖5分別顯示了訓(xùn)練集劃分比例為30%，50%，70%和90%的各個網(wǎng)絡(luò)中所有被測試算法的對比分析結(jié)果.從圖4和圖5中可以看出雖然降噪自編碼器在各個數(shù)據(jù)集上的準確率和AUC值均取得了不錯的結(jié)果，但是AUC的表現(xiàn)并不穩(wěn)定，尤其是在較大的網(wǎng)絡(luò)數(shù)據(jù)集中.其原因是網(wǎng)絡(luò)規(guī)模變大時，網(wǎng)絡(luò)結(jié)構(gòu)間的隱含特征也將隨之增多，通常較小的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)不能充分地表達出鏈路預(yù)測中正樣本(兩個節(jié)點間存在鏈路)和負樣本(兩個節(jié)點間不存在鏈路)之間的差別，導(dǎo)致預(yù)測準確性存在波動，但整體上還保持著相當(dāng)?shù)膬?yōu)勢.

圖4 不同算法在各個測試網(wǎng)絡(luò)中針對一系列訓(xùn)練集劃分比例的預(yù)測準確性Fig.4 Precision evaluation of the eight algorithms for a series of ξ values on the seven networks

圖5 不同算法在各個測試網(wǎng)絡(luò)中針對一系列訓(xùn)練集劃分比例的AUC評估值Fig.5 AUC evaluation of the eight algorithms for a series of ξ values on the seven networks

綜上所述，本文提出的DA算法在預(yù)測準確性與魯棒性分析方面均表現(xiàn)出明顯的優(yōu)勢，體現(xiàn)出本算法與其他經(jīng)典的鏈路預(yù)測算法相比具有較強的競爭性.

6 總 結(jié)

考慮到無監(jiān)督學(xué)習(xí)模型善于挖掘與分析各類高維數(shù)據(jù)的潛在特征，本文提出一種基于降噪自編碼器的鏈路預(yù)測算法.該算法首先通過訓(xùn)練學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，使其具有數(shù)據(jù)降噪的能力；緊接著將完整的訓(xùn)練集輸入到已訓(xùn)練好的網(wǎng)絡(luò)結(jié)構(gòu)中使其具有鏈路預(yù)測的能力.本文針對大量不同類型的網(wǎng)絡(luò)進行了對比實驗，結(jié)果表明本算法與其他經(jīng)典的鏈路預(yù)測算法相比在預(yù)測準確性和魯棒性上均體現(xiàn)出優(yōu)勢.同時，實驗結(jié)果表明，本文提出的算法不僅能夠從殘缺的數(shù)據(jù)中學(xué)習(xí)到有用的信息，而且能夠有效的降低不同網(wǎng)絡(luò)結(jié)構(gòu)對算法的影響.另外，本算法的提出能為將來鏈路預(yù)測的研究提供新的思路.

相對而言，本文的研究尚存在一定的缺陷，當(dāng)網(wǎng)絡(luò)規(guī)模較大時，網(wǎng)絡(luò)結(jié)構(gòu)間的隱含特征會隨之增多，通常較小的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)不能充分地學(xué)習(xí)到數(shù)據(jù)間的潛在特征，導(dǎo)致預(yù)測準確性存在波動.因此在將來的工作中，考慮會深入研究復(fù)雜網(wǎng)絡(luò)規(guī)模與神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)間的相互影響關(guān)系，進一步提升算法的預(yù)測能力.