陸圣宇，史 軍，劉 寶，姚金魁，金 毅

(江南計算技術(shù)研究所，江蘇 無錫 214083)

0 引 言

復(fù)雜網(wǎng)絡(luò)從宏觀角度分析，是具備自組織、自相似、小世界、無標(biāo)度中部分或全部性質(zhì)的網(wǎng)絡(luò)。近年來，復(fù)雜網(wǎng)絡(luò)不僅僅作為數(shù)據(jù)的表現(xiàn)形式，更代表著數(shù)據(jù)科學(xué)、網(wǎng)絡(luò)科學(xué)的主要研究方向，基于數(shù)據(jù)的復(fù)雜系統(tǒng)的數(shù)學(xué)模型正以一種全新的視角快速發(fā)展[1]。許多復(fù)雜系統(tǒng)都可以抽象成一種復(fù)雜網(wǎng)絡(luò)進行分析，比如常見的電力網(wǎng)絡(luò)、航空網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、計算機網(wǎng)絡(luò)以及社交網(wǎng)絡(luò)等，其研究價值日益凸顯。

鏈路預(yù)測[2]是復(fù)雜網(wǎng)絡(luò)中的高效建模分析方法，通過基于網(wǎng)絡(luò)節(jié)點的屬性信息和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息而展開。鏈路預(yù)測主要有兩個研究方向[3]，一是對客觀存在但仍然未知的網(wǎng)絡(luò)拓?fù)滏溌愤M行預(yù)測，二是對未來將要發(fā)生連接關(guān)系的網(wǎng)絡(luò)拓?fù)滏溌愤M行預(yù)測。

作為數(shù)據(jù)挖掘領(lǐng)域的研究模式之一，早期鏈路預(yù)測重點傾向于基于機器學(xué)習(xí)、馬爾可夫鏈[4]等方向。這些通過獲取節(jié)點屬性等外部信息來建立起高效預(yù)測優(yōu)勢，例如綜合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息與網(wǎng)絡(luò)節(jié)點屬性開展預(yù)測，或者通過對節(jié)點屬性定義節(jié)點對的相似性程度開展預(yù)測。但在多數(shù)情況下，對節(jié)點屬性信息的獲取存在明顯困難[2]。因此，在不使用節(jié)點屬性信息的前提下，通過獲取純粹的網(wǎng)絡(luò)結(jié)構(gòu)信息來定義相似性指標(biāo)，成為當(dāng)前鏈路預(yù)測的一種主流方法。其核心在于選擇定義網(wǎng)絡(luò)中節(jié)點間的相似性度量指標(biāo)，一個重要假設(shè)前提就是兩個節(jié)點之間相似性越大，相應(yīng)兩個節(jié)點之間存在鏈接的可能性就越大[5]。

在其他的鏈路預(yù)測算法中，當(dāng)前主要有基于似然分析的方法和機器學(xué)習(xí)方法。在基于似然分析的方法中，有通過族譜樹進行網(wǎng)絡(luò)層次劃分的層次結(jié)構(gòu)模型[6]，將節(jié)點聚類組成集合進行預(yù)測的連邊的隨機分塊模型[7]和根據(jù)網(wǎng)絡(luò)中封閉回路數(shù)定義網(wǎng)絡(luò)似然的閉路模型[8]。在機器學(xué)習(xí)方法中，針對鏈路預(yù)測主要有基于特征分類、概率圖模型和矩陣分類[9]，都是需要有監(jiān)督的機器學(xué)習(xí)方法。

文中重點從節(jié)點度數(shù)和相似性傳遞的角度分析二者在鏈路預(yù)測過程中的影響，將基于節(jié)點度數(shù)的偏好連接相似性矩陣作為轉(zhuǎn)移自洽相似性指標(biāo)的直接相似性輸入，通過矩陣求逆的方式求解對應(yīng)的轉(zhuǎn)移相似性，并通過調(diào)節(jié)直接相似性與轉(zhuǎn)移相似性比例參數(shù)ε，優(yōu)化最終鏈路預(yù)測結(jié)果的AUC值。然后就基于網(wǎng)絡(luò)結(jié)構(gòu)相似性的指標(biāo)算法進行簡要介紹；通過比較算法的特性，從基于偏好連接相似性和轉(zhuǎn)移自洽相似性指標(biāo)出發(fā)，構(gòu)造TSPA相似性指標(biāo)算法；最后結(jié)合經(jīng)典復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集進行對比分析實驗。

1 基于結(jié)構(gòu)相似性的鏈路預(yù)測指標(biāo)

基于結(jié)構(gòu)相似性的指標(biāo)代表了通過節(jié)點之間的結(jié)構(gòu)信息(例如節(jié)點的度、最近鄰居、二階鄰居等)進行加權(quán)計算獲得的相似性指標(biāo)。當(dāng)計算得到的相似性指標(biāo)越大，那么該節(jié)點對之間產(chǎn)生連邊的概率也越大。當(dāng)前大部分基于結(jié)構(gòu)相似性的鏈路預(yù)測相似度都從共同鄰居算法的思想出發(fā)，其主要優(yōu)點是共同鄰居信息的獲取較為容易且計算復(fù)雜度低。

1.1 CN指標(biāo)

在基于共同鄰居的相似性指標(biāo)集合中，CN指標(biāo)(common neighbors)最早來自于Lorrain等[10]提出的社交網(wǎng)絡(luò)中的個體結(jié)構(gòu)等價性，通過觀察，如果特定的節(jié)點對所共有或共享的外部節(jié)點數(shù)量較多，則判斷特定節(jié)點對之間存在高度的同質(zhì)性。Kossinets[11]在社交網(wǎng)絡(luò)的分析研究中發(fā)現(xiàn)，共同朋友越多的人成為好友的潛在可能性越大。Newman[12]同樣在科學(xué)家合作網(wǎng)絡(luò)中發(fā)現(xiàn)，存在更多共同的第三方科研合作者的科學(xué)家之間，在未來進行同一科研合作項目的可能性更大。

CN指標(biāo)如下：

suv=|Γ(u)∩Γ(v)|

(1)

其中，Γ(u)∩Γ(v)表示節(jié)點u與節(jié)點v所共有的鄰居節(jié)點集合。

1.2 考慮共同鄰居與節(jié)點度綜合計算的指標(biāo)

在CN指標(biāo)的基礎(chǔ)上，對CN指標(biāo)所定義的相似性結(jié)合節(jié)點度等參數(shù)進行額外步驟計算，衍生出Salton指標(biāo)、Jaccard指標(biāo)等8種相似性指標(biāo)。

(1)Salton指標(biāo)[13]。

Salton指標(biāo)在CN指標(biāo)的基礎(chǔ)上，計算過程融入了特定節(jié)點對的度參數(shù)，Salton指標(biāo)也稱作余弦相似性。

Salton指標(biāo)如下：

(2)

其中，ku和kv為節(jié)點u、v的度。

(2)Jaccard指標(biāo)[14]。

Jaccard指標(biāo)在CN指標(biāo)基礎(chǔ)上，除以節(jié)點對u、v鄰居并集的勢。

Jaccard指標(biāo)如下：

(3)

(3)Sorensen指標(biāo)[15]。

Sorensen指標(biāo)將CN指標(biāo)的相似度值乘以2再除以節(jié)點對u、v的度之和。

Sorensen指標(biāo)如下：

(4)

(4)HPI[16]與HDI[5]指標(biāo)。

HPI(hub promoted index)大度節(jié)點有利指標(biāo)主要用于新陳代謝網(wǎng)絡(luò)研究，該指標(biāo)認(rèn)為節(jié)點對之間的相似度與二者度數(shù)中較小者成反比。HDI(hub depressed index)大度節(jié)點不利指標(biāo)則認(rèn)為節(jié)點對之間相似度與二者度數(shù)中較大者成反比。

HPI指標(biāo)如下：

(5)

HDI指標(biāo)如下：

(6)

(5)LHN-I指標(biāo)[17]。

Leicht，Holme與Newman基于共同鄰居思想提出了LHN-I指標(biāo)，如下：

(7)

其中，節(jié)點u、v的度數(shù)乘積與相似度成反比。

1.3 考慮鄰居度數(shù)的指標(biāo)

在特定節(jié)點對的共同鄰居中，擁有大節(jié)點度數(shù)的共同鄰居，對特定節(jié)點對產(chǎn)生的影響、輻射往往會小于小節(jié)點度數(shù)的共同鄰居。在該思想的基礎(chǔ)上，先后出現(xiàn)了預(yù)測性能較好的AA指標(biāo)和RA指標(biāo)。

(1)AA指標(biāo)[18]。

在AA指標(biāo)中，根據(jù)共同鄰居節(jié)點的度，為每個共同鄰居節(jié)點賦予一個權(quán)重值，該值等于共同鄰居節(jié)點度的對數(shù)分之一。然后將權(quán)重值累加，獲得特定節(jié)點對之間的相似度。

(8)

(2)RA指標(biāo)[19]。

周濤等受網(wǎng)絡(luò)資源分配過程的啟發(fā)，提出RA指標(biāo)(resource allocation)。在RA指標(biāo)中，權(quán)重值由AA指標(biāo)中度的對數(shù)分之一的權(quán)重值變換為度數(shù)分之一。

(9)

RA指標(biāo)與AA指標(biāo)通過對共鄰節(jié)點度進行權(quán)重差異化處理，主要體現(xiàn)在RA指標(biāo)中為1/k遞減，而在AA指標(biāo)中為1/logk遞減，因此當(dāng)網(wǎng)絡(luò)中的平均度很小時，AA與RA指標(biāo)的計算結(jié)果近似一致。

1.4 考慮偏好連接的指標(biāo)

在PA指標(biāo)[20]中，在節(jié)點v和節(jié)點u之間產(chǎn)生無向邊的概率，應(yīng)該正比于節(jié)點u、v的度ku、kv之積。因此，在預(yù)測網(wǎng)絡(luò)過程中，大度節(jié)點之間更加傾向于產(chǎn)生連接關(guān)系。PA指標(biāo)在預(yù)測非常稀疏的路由網(wǎng)絡(luò)中，效率與準(zhǔn)確率都非常高。

suv=ku·kv

(10)

1.5 考慮自洽轉(zhuǎn)移相似性的指標(biāo)

孫舵等[21]在研究推薦系統(tǒng)時提出了轉(zhuǎn)移相似性的概念，通過假設(shè)節(jié)點之間相似性可以傳遞來刻畫節(jié)點之間的間接相似程度。該方法可以更加高效地利用已知的結(jié)構(gòu)信息。以節(jié)點A與節(jié)點B相連，節(jié)點B和節(jié)點C相連的簡單圖為例，節(jié)點C、節(jié)點A分別與節(jié)點B之間建立相似性，B和C之間也建立了相似性，通過B的相似性傳遞，A與C之間也可能存在潛在的相似性聯(lián)系。

TS指標(biāo)如下：

(11)

其中，等號右側(cè)第一項為間接相似性；等號右側(cè)第二項suy為輸入任意一種相似性指標(biāo)得到的直接相似性；ε為可調(diào)參數(shù)，用以調(diào)節(jié)直接與間接相似性的比例。當(dāng)直接相似性suy定義為鄰接矩陣時，轉(zhuǎn)移相似性矩陣可以等價表示如下：

STr=(I-εS)-1S

(12)

該方法由于需要原始相似性指標(biāo)作為測度輸入、涉及矩陣逆運算，算法客觀上存在計算開銷大的缺點。

2 一種基于轉(zhuǎn)移偏好自洽相似性的鏈路預(yù)測方法

2.1 TSPA指標(biāo)

上一節(jié)介紹了鏈路預(yù)測的常用相似性指標(biāo)，在充分考慮節(jié)點度信息與網(wǎng)絡(luò)結(jié)構(gòu)信息的基礎(chǔ)上，文中是將轉(zhuǎn)移自洽相似性與偏好連接方法相整合，提出一種新的鏈路預(yù)測方法—基于轉(zhuǎn)移偏好自洽相似性的鏈路預(yù)測方法(transferring similarity based on preferential attachment，TSPA)。

首先結(jié)合PA算法只考慮到了節(jié)點對的度數(shù)影響，且度數(shù)越高，二者連邊概率越大。整合進TS方法，為把傳遞相似信息納入，將PA方法與TS方法相結(jié)合，得到基于轉(zhuǎn)移偏好自洽相似性的TSPA方法，定義如下：

(13)

通過變形，等價表示如下：

(14)

TSPA相似性理解可以從兩個角度展開，一個是節(jié)點對之間已經(jīng)存在的連邊關(guān)系，另一個則是通過節(jié)點對的共同鄰居的局部結(jié)構(gòu)傳遞而具備的間接相似性。TSPA方法整合了PA與TS方法，在傳統(tǒng)PA方法中只通過計算兩個節(jié)點度數(shù)之積來建立相似性比較，而對間接的相似性信息沒有充分加以利用。TSPA方法通過中間節(jié)點的傳遞特性，針對性克服了結(jié)構(gòu)信息利用不充分的缺點。同時，TSPA方法中通過對ε參數(shù)的調(diào)優(yōu)，可以看到中間節(jié)點相似性傳遞對特定節(jié)點對的影響大小，結(jié)合不同特性的網(wǎng)絡(luò)，通過調(diào)節(jié)ε可以看到不同的預(yù)測結(jié)果。

2.2 TSPA算法設(shè)計

根據(jù)上一節(jié)描述，TSPA方法的算法描述如下：

輸入：特定網(wǎng)絡(luò)鄰接矩陣M；

輸出：相似性矩陣S，其中Su,v表示特定節(jié)點u、v產(chǎn)生連邊關(guān)系的相似性得分，Su,v越大表示連邊可能性越高，若Mu,v=1，則表示已經(jīng)產(chǎn)生連邊關(guān)系，在Su,v中直接置0。

算法步驟：

(1)構(gòu)造列向量存儲每個節(jié)點對應(yīng)的度：

deg_row=sum(M,2)

將鄰接矩陣M中每一行求和，即為每個節(jié)點對應(yīng)的度的列向量。

(2)將列向量Deg乘以其轉(zhuǎn)置，得到PA方法的相似性矩陣Sim：

Sim=deg_row * deg_row'

(3)結(jié)合PA測度輸入，計算傳遞相似性矩陣：

S=(I-ε*Sim)-1*Sim

(4)刪去S中值為1的已存在邊元素：

S=S-S?M

在步驟4中，?表示兩矩陣對應(yīng)位置元素相乘,對應(yīng)Matlab中的矩陣“.*”運算規(guī)則。

3 實驗與分析

實驗將現(xiàn)有的CN共同鄰居算法、RA資源分配算法、PA偏好連接算法和提出的TSPA算法應(yīng)用到復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測中的經(jīng)典數(shù)據(jù)集，通過分析比較各算法對應(yīng)的AUC值，對各算法預(yù)測性能進行對比分析。

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

實驗采用7個復(fù)雜網(wǎng)絡(luò)預(yù)測常用的數(shù)據(jù)集[2]，Router為Internet中路由器層次的網(wǎng)絡(luò)，節(jié)點表示路由器，連邊表示兩路由器通過光纖等方式直連進行數(shù)據(jù)包交換；USAir為美國航空網(wǎng)絡(luò)，每個節(jié)點對應(yīng)一個機場，機場間若存在直達航線則表示存在連接關(guān)系；Yeast為蛋白質(zhì)相互作用網(wǎng)絡(luò)，節(jié)點為蛋白質(zhì)大分子，若蛋白質(zhì)之間存在相互作用關(guān)系則認(rèn)為存在連接關(guān)系；PB為美國某政治論壇博客網(wǎng)絡(luò)，博主為網(wǎng)絡(luò)節(jié)點，如果博客間存在超鏈接關(guān)系則認(rèn)為兩個博主之間存在連接關(guān)系；NS為發(fā)表過復(fù)雜網(wǎng)絡(luò)為主題的科學(xué)家合作網(wǎng)絡(luò)，科學(xué)家為網(wǎng)絡(luò)節(jié)點，如果科學(xué)家之間存在論文合作關(guān)系，則認(rèn)為科學(xué)家之間存在連接關(guān)系；C.elegans為線蟲的神經(jīng)網(wǎng)絡(luò)，節(jié)點由線蟲的神經(jīng)元表示，神經(jīng)元的突觸或者間隙連接存在，則認(rèn)為神經(jīng)元之間存在連接關(guān)系。

表1將7個復(fù)雜網(wǎng)絡(luò)經(jīng)典數(shù)據(jù)集以統(tǒng)計量的形式展現(xiàn)出來,其中N為網(wǎng)絡(luò)節(jié)點數(shù)量，M為網(wǎng)絡(luò)的邊數(shù)，K為網(wǎng)絡(luò)平均度，C為聚類系數(shù)，D為網(wǎng)絡(luò)直徑，L為平均最短路徑。

表1 用于鏈路預(yù)測實驗的網(wǎng)絡(luò)基本統(tǒng)計特征

下面通過可視化的形式，展示測試的7個復(fù)雜網(wǎng)絡(luò)中的路由器Router網(wǎng)絡(luò)和PB博客關(guān)系網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。具體如圖1和圖2所示。

圖1 Router網(wǎng)絡(luò)

圖2 PB網(wǎng)絡(luò)

3.2 評價指標(biāo)

在鏈路預(yù)測算法評估中，存在AUC、精確度(precision)、排序分(ranking score)三個評價指標(biāo)。精確度指標(biāo)首先需要確定一個值L，L表示根據(jù)特定算法獲得的前L個預(yù)測結(jié)果，然后在前L個結(jié)果中對比真實鏈路情況，找出準(zhǔn)確預(yù)測的鏈路個數(shù)m，最終m/L的值即為精確度。精確度越大，則算法的準(zhǔn)確度越高。排序分則考慮了測試集中邊在最終排序總結(jié)果中的位置，取re為測試邊在排序中的名次，集合H為未知邊集合，則單條測試邊排序分為RSe=re/|H|。遍歷所有測試邊進行累加求均值，即可得到最終的排序分，排序分越小，說明算法準(zhǔn)確度越高。

AUC指標(biāo)[22]在鏈路預(yù)測、機器學(xué)習(xí)等領(lǐng)域應(yīng)用廣泛。AUC指標(biāo)從整體上把握衡量算法的精準(zhǔn)程度，相比Precision指標(biāo)[23]僅考慮前L條邊的預(yù)測準(zhǔn)確程度和Ranking Score指標(biāo)[24]更多考慮所預(yù)測邊的排序情況，AUC綜合衡量算法的準(zhǔn)確程度與實用性更強。

3.3 實驗過程與結(jié)果

在實驗過程中，將復(fù)雜網(wǎng)絡(luò)經(jīng)典數(shù)據(jù)集進行隨機劃分，訓(xùn)練集占總邊數(shù)的90%，測試集占總邊數(shù)的10%，每個數(shù)據(jù)集進行100次獨立實驗。在訓(xùn)練集計算過程中，通過先獲取數(shù)據(jù)集節(jié)點對間的Sim相似度矩陣，然后通過相似度矩陣測算各類邊的連邊概率，得到AUC值，并結(jié)合獨立實驗次數(shù)，得到最終的AUC均值。

網(wǎng)絡(luò)基本統(tǒng)計特征如表2所示。

表2 用于鏈路預(yù)測實驗的網(wǎng)絡(luò)基本統(tǒng)計特征

從不同種類算法的橫向角度比較，TSPA指標(biāo)在路由網(wǎng)絡(luò)、航空網(wǎng)絡(luò)、蛋白質(zhì)網(wǎng)絡(luò)、政治博客網(wǎng)絡(luò)中取得了較好的預(yù)測結(jié)果。TSPA在和RA、CN這兩個基于網(wǎng)絡(luò)結(jié)構(gòu)相似性預(yù)測性能較好的指標(biāo)對比中，在路由網(wǎng)絡(luò)這種低網(wǎng)絡(luò)平均度、低網(wǎng)絡(luò)聚類系數(shù)的環(huán)境下，取得了明顯的預(yù)測優(yōu)勢。

圖3 TSPA取不同ε參數(shù)的AUC值

在TSPA指標(biāo)與同源的PA指標(biāo)類比中，在選取的三個ε參數(shù)(-0.1、-0.05、-0.01)中，分別在7個真實網(wǎng)絡(luò)的預(yù)測中取得了對PA指標(biāo)的5、1、6個網(wǎng)絡(luò)的預(yù)測優(yōu)勢。即便在預(yù)測情況較低的參數(shù)(-0.05)下，剩余6個網(wǎng)絡(luò)預(yù)測AUC值也和PA指標(biāo)結(jié)果非常接近，體現(xiàn)了TSPA指標(biāo)較傳統(tǒng)PA指標(biāo)的預(yù)測穩(wěn)定性。具體如圖3和圖4所示。

圖4 TSPA與其他方法的AUC值對比

通過將基于偏好連接方法獲取的網(wǎng)絡(luò)度結(jié)構(gòu)信息，與轉(zhuǎn)移自洽相似性方法相整合，形成的全新TSPA指標(biāo)在真實網(wǎng)絡(luò)預(yù)測中得到了有效驗證。預(yù)測的AUC準(zhǔn)確度結(jié)果在與一眾經(jīng)典鏈路預(yù)測指標(biāo)對比中，建立了針對具體特征網(wǎng)絡(luò)的預(yù)測優(yōu)勢，并通過ε值的對比分析，表明如果將ε值調(diào)整為正數(shù)，將對TSPA指標(biāo)中最終預(yù)測結(jié)果產(chǎn)生反向降低AUC值的影響。

4 結(jié)束語

在綜合利用節(jié)點度信息與網(wǎng)絡(luò)結(jié)構(gòu)相似性傳遞信息的基礎(chǔ)上，提出了一種基于轉(zhuǎn)移偏好自洽相似性的鏈路預(yù)測方法TSPA。該方法將節(jié)點對之間的度乘積信息形成的相似性矩陣，作為測度信息傳入TS方法，并就具體的ε值進行驗證。TSPA方法相比傳統(tǒng)鏈路預(yù)測相似性方法，納入了更多的網(wǎng)絡(luò)結(jié)構(gòu)信息，在對低平均度、低聚類系數(shù)的網(wǎng)絡(luò)中展現(xiàn)出了更好的預(yù)測性能。

在后續(xù)的研究工作中，雖然TSPA在特定網(wǎng)絡(luò)中的預(yù)測優(yōu)勢明顯，但計算方法過程中涉及到矩陣求逆等操作，算法的時間開銷相比CN、RA等方法存在一定劣勢。在下一階段工作中，一是在多樣化研究和測試不同鏈路預(yù)測方法的基礎(chǔ)上，對元路徑的異質(zhì)信息[25]、局部路徑節(jié)點度冪指數(shù)規(guī)律[5]進行研究，降低對網(wǎng)絡(luò)結(jié)構(gòu)的計算規(guī)模，在提高或維持算法的預(yù)測精度的基礎(chǔ)上，降低算法流程上的時間開銷，使TSPA方法的預(yù)測效果得到進一步提高。