基于加權投影的二分網絡的鏈路預測

張佳慧 張 婷 呂來水 張 娜

(南京理工大學計算機科學與工程學院 江蘇 南京 210094)

0 引 言

網絡科學一直受到科學界關注的領域，尤其是那些模擬復雜系統組織的科學研究。網絡還可以很自然地描述各種社會結構。在這樣的網絡中，頂點表示實體，鏈接表示實體之間的通信或關系。社會網絡反映了個人或社會組織及其關系，如伙伴關系或友誼。社會網絡分析在社會學領域引起了越來越多的關注，它分析和探索社會對象之間的潛在關系。近年來，社交網絡分析在電子商務分析、市場建模等諸多商業領域也引起了人們的高度關注。

根據復雜網絡中已知節點的類型，可以將網絡分為單分網絡和二分網絡[1](如圖1所示)。單分網絡也可稱為單層網絡，是一種普遍廣泛研究的網絡類型；而二分網絡是指網絡中存在兩類節點，這兩類節點通過邊形成關聯，節點類內部沒有邊相連。該網絡形成的拓撲結構被稱為二分圖，現實生活中存在許多二分網絡，例如演員-電影網[2]、科學家-合作網[3]等。這兩類具有不同屬性的節點類型中，一類節點是參與某類活動、事件的主導者，如演員、科學家等，另一類節點是這些主導者從事的活動或者事件，例如電影、文章等，這些都可以作為區分為二分網絡中兩類節點的依據。

圖1 單分網絡和二分網絡

目前針對二分網絡的研究主要分為：(1) 把二分網絡投影到單層網絡上再進行網絡分析；(2) 直接基于原始二分網絡進行網絡研究。現在研究得比較多的是第一種，而針對二分網絡的投影又分為無權投影和加權投影[4]。圖2是簡單的無權投影，無權投影雖然簡便直接，但是卻丟失了關于二分網絡結構的信息，研究意義不大。而加權投影又分為很多種，各種加權投影的區別體現在對權重的設定不同，一種比較直接的投影方法是根據兩個節點的共同鄰居節點進行投影[5]，還有根據節點的貢獻程度不同而設置具體的權值函數[6]。

圖2 無權投影

鏈路測試[7]是網絡分析[8]中的一個重要研究領域。鏈路測試的目的是從網絡的現有拓撲特征中檢測未觀測到的鏈路，或者從網絡的當前拓撲結構中預測未來鏈路。在社會保障網絡中，鏈路測試用于發現恐怖分子或犯罪分子的地下組織[9]，而在人類行為網絡中，鏈路預測用于識別和分類人的活動和移動[10]。鏈路預測在反映社會關系的無線網絡中也有許多應用，如通信網絡、電子郵件網絡和傳感器網絡。在傳感器網絡中，利用鏈路預測來發現動態時間特性[11]，以保證信息傳輸保密[12]，實現最優路由[13]。

二分網絡是目前比較熱門的研究話題，基于二分網絡的鏈路預測具有廣泛的研究價值。針對單分網絡而言，鏈路預測有基于節點對之間相似度來進行研究的，如呂琳嬡[14]通過基于網絡結構的相似性得到很好的鏈路預測效果；基于拓撲結構展開的鏈路預測，如Liben-Nowell等[15]基于網絡連接結構的鏈路預測理論進行拓撲鏈路預測；針對機器學習研究出的鏈路預測方法，如Pujari等[16]將監督秩聚合應用于復雜網絡中的鏈路預測；運用概率學原理模型研究出的鏈路預測，如Lü等[17]基于可預測的模型機制來預測缺失鏈路的能力。針對二分網絡而言，其實是對單分網絡鏈路算法的一種提升、改進和創新。基于機器學習中監督學習的方法來訓練預測模型，如Benchettara等[18]將二分網絡中的鏈路預測看成是二類的分類問題，采用監督學習的方法來訓練預測模型；引入新的拓撲特征來實現對二分網絡中節點對的鏈路的概率的量化，如文獻[19]；基于圖模型來預測二分網絡中節點對的鏈路，如文獻[20]。二分網絡中產生的鏈接屬于不同類別，對應的鄰居節點也屬于不同類別，

本文主要通過一種基于資源分配的加權算法對二分網絡進行投影，并且利用得到的權值矩陣，來得到同類節點之間的相似度度量，通過節點之間的相似度度量計算出兩類節點未鏈接邊之間資源分配比重的比較，得到節點之間鏈路最高的連邊，從而達到鏈路預測的目的。最后利用AUC來對算法進行實驗，驗證本文算法的有效性和準確性。

1 投影相關知識

目前研究的技術中已存在許多關于投影方面的技術，有一些基于系數進行投影的技術，比如Eculidean、Pearson等。本節通過與其他技術進行比較的方法來體現本文算法的優勢。在每一種技術中，二分圖G的實體被認為是二元向量。假設有一個二分圖由兩類實體A={a1,a2,a3}和B={b1,b2,b3,b4,b5}組成。假設a1鏈接b1、b4和b5，那么a1={1,0,0,1,1}。在下面的介紹中，采用投影到類A上的做法。

1.1 基于Eculidean的投影

在數學中，歐幾里得距離或歐幾里得度量是歐幾里得空間中兩點間“普通”(即直線)距離[21]。使用這個距離，歐氏空間稱為度量空間。基于Euclidean的投影技術利用了歐氏距離的概念。a1和a2向量被認為是B維空間中的點，則a1和a2之間的歐氏距離為：

基于Eculidean的相似度與歐氏距離成反比，即s(a1,a2)=1/d(a1,a2)。基于Eculidean的相似度不僅強調了a1和a2中1的共存，而且還強調了0的數量。

1.2 基于Pearson的投影

Pearson相關系數是用來衡量兩個數據集合是否在一條線上面，即衡量定距變量間的線性關系[22]。基于Pearson的二分網絡投影技術，通過計算a1和a2向量的相關系數如下：

式中：cov(a1,a2)是a1和a2的協方差；σa1和σa2分別是a1和a2向量的方差。Pearson相似度也賦予了聯系的共同缺失的重要性，而不僅僅是共同存在的重要性。

通過計算例子中的Pearson相似度，其中a1={1,0,0,1,1}和a2={1,0,1,0,1}，得到結果s(a1,a2)=0.05/(0.3×0.3)。

2 二分圖相關知識

二分圖G=(U,V,E)表示二分網絡，其中U和V是G中節點的兩部分。本文使用字母(如c、d)表示U部分節點，使用小寫字母(如x、y)表示V部分節點。E是G中邊的集合。在同一組U或V中，節點之間沒有邊緣；即每條邊(c,x)∈E都滿足c∈U,x∈V。

假設U有n個節點，V有m個節點，G的鄰接矩陣采用非對角塊形式：

式中：0n×n和0m×m分別是n×n和m×m的全零矩陣。

An×m為n×m的非零矩陣。由于鄰接矩陣是對稱的，可以簡單地用矩陣An×m表示二分圖G，其中每一行表示U集合中的一個節點，每一列表示V集合中的一個節點。

圖3展示了演員-電影二分網絡。在這個網絡中，有兩種節點，分別被標注成圓形和正方形。圓形節點代表演員，正方形節點代表電影。使用N(c)={x|x∈V,(c,x)∈E}來表示圖G中的節點c的鄰居節點的集合。

為了分析二分網絡中的鏈路存在的可能性，首先將其映射到一個被稱為投影圖的單層網絡上。

定義1投影圖。給出一個二分圖G=(U,V,E)，它的U投影圖定義為單層網絡GU=(U,EU)，其中邊的集合是：

EU={(c,d)|c,d∈U,?x∈V,x∈N(c)∩N(d)}

從定義1可以看出，如果二分圖G中的U部分的節點c和d在V部分中至少有一個共同的鄰居，那么在U部分的投影圖中就存在一個鏈接(c,d)。同樣，可以定義G中的V部分的投影圖GV=(V,EV)，其中邊的集合是：

EV={(x,y)|x,y∈V,?c∈U,x∈N(x)∩N(y)}

3 主要方法

本文采用相似性度量獲得頂點之間的相似度得分，通過利用二部圖中的信息，根據二部圖中U部分和V部分節點是否存在共同鄰居，將二部圖投影到單部圖中。并采用基于資源的均勻分配加權算法，得到同類節點之間的資源分配權重。通過考慮復雜網絡的整體結構，利用資源分配比重的大小進行鏈路預測。由此，可以克服傳統相似性度量的大部分問題。

為了預測二分網絡中可能存在的鏈接，需要根據其投影圖定義其候選邊。

定義2候選邊。設二分圖G=(U,V,E)，c∈U,x∈V是圖中的兩個節點，(c,x)?E。圖中U部分的投影圖為GU=(U,EU)，通過對圖G添加一個新的鏈接(c,x)∈U×V，可以構建一個新的二分網絡G′=(U,V,E′)，其中E′=E∪{(c,x)}。G′U=(U,E′U)是圖G′的投影圖，把(c,x)稱為圖G在U部分投影的候選對(Candidate Pair，CP)。同樣地，也可以定義出V部分投影的候選對。

(c,x)是G=(U,V,E)中的一對節點，c∈U,x∈V且(c,x)?E。GU=(U,EU)是圖G中U部分的投影圖表示。圖GU中節點c∈U的鄰居節點的集合是NU(c)={d|d∈U,(c,d)∈EU}，同樣地,節點x∈V的鄰居節點的集合是NV(x)={c|c∈U,(c,x)∈E}。

也就是說，節點對(c,x)是U投影圖的候選節點，當且僅當：

NU(c)∩N(x)≠?且c?N(x)

如果(c,x)是圖G中的候選對，那么對于每個滿足NU(c)∩N(x)的節點D，在投影圖GU中就有一個鏈接(c,d)。既然(c,x)是圖G中的候選對，則c?N(x)，并且圖G中不存在邊(c,x)。如果向二分圖中添加邊(c,x)，那么對于每個滿足d∈NU(c)∩N(x)的節點，在GU中就會有一條新的連邊(c,d)，并且在圖G中c和d都與節點x有鏈接。既然GU中包含(c,d)，所以把(c,d)作為投影圖GU被候選對(c,x)覆蓋的一種模式。

通過網絡中資源分配過程的啟發，本文將資源分配的加權進行如下分解：

(1) 初始化V部分節點資源f(vx)=axc。

(2) 將V部分中每個節點得到的資源平均分配給與它相連的U部分的節點(二分網絡本身是不加權的)，則U部分的節點得到的資源是來自于每個與它相連的V部分節點通過平均分配得到的資源之和f(uc)：

式中：k(vx)表示在二分網絡中υx節點的度。

(3) 將U部分節點得到的資源再次平均分配到V部分節點中與它相連的節點上，與步驟(2)中類似，得到基于投影實現的V部分節點的資源分配值即得到關于候選對(c,x)的評分估計值S(ucvx)：

(4)wxy表示V部分節點中x希望分配給y的資源的比例。根據理解可得，S(ucvx)還可以寫成：

(5) 根據步驟(3)-步驟(4)可以計算出wxy：

wxy可以表示為V部分投影中，節點y對節點x的連邊的權值，并且wxy≠wyx,x和y的度決定了這兩個值的區別，根據節點生成的度和節點對之間的共同鄰居數可以看出，節點之間的權值是不對稱的。因此W={wxy}m×m表示經過基于資源分配的加權算法得到的加權投影矩陣。

(6) 根據步驟(4)得到的投影之后V部分分配到的資源值，可以預測U部分中每個節點c與V部分中未鏈接的節點x之間是否會產生鏈接。計算U部分中每個節點c與V部分中未鏈接節點x的S(ucvx)值：

(7) 根據每個節點c得到的所有S(ucvx)值，并對這些值進行降序排列，值最大的S(ucvx)所對應的節點x即為與節點c最有可能產生鏈接的節點，即完成一次鏈路預測，要預測每個U部分的節點c，需要對步驟(6)中的式子重復計算n次，完成整個鏈路預測。

本文方法也可以采用隨機游走的觀點來解釋。通過隨機漫步游走在二分網絡上的順序過兩類節點，那么S(ucvx)記錄了還有多久候選節點對(c,x)會在二分網絡中出現鏈接的概率。

4 實 驗

本文實驗采用了Southern Women、MovieLens兩個數據集來進行實驗驗證，并對實驗結果進行分析。實驗過程要采用Python來完成代碼設計，并進行結果分析圖的繪制。為了驗證算法的精確度，將本文算法(WLP)與基于Euclidean的相似度預測算法(ELP)和基于Pearson的相似度預測算法(PLP)進行比較。

4.1 Southern Women數據集實驗分析

Southern Women數據集由Davis在1930年收集，是二分網絡中被廣泛用來測試的數據集，其主要結構如下：18位婦女和14個由這些婦女形成的社會活動。在二分網絡中，把18位婦女當作一類節點，14個社會活動當作另一類節點。如果一個婦女參與了一類活動，那么該婦女與該活動之間就有一條連邊，而婦女節點之間不存在連邊。該數據集的網絡結構組成如圖4所示。該數據集的詳細數據信息如表1所示。

圖4 Southern Women網絡結構

表1 Southern Women數據結構

為了測試本文提出的算法，將該數據集的93條邊隨機分為兩部分：訓練集包含83條邊，測試集包含10條邊。訓練集作為已知信息處理，測試集用來評估算法的準確性。在該數據集上分別對算法WLP、ELP和PLP進行10次實驗，每次隨機抽取10%的數據作為測試集，剩下90%的數據作為訓練集。實驗結果如表2所示。

表2 Southern Women上的三種方法實驗結果(AUC)比較

可以看出，雖然三種方法的準確性有些時候很相似，但是在整體上來看，WLP算法能夠取得足夠高的準確性，說明本文算法具有有效性。

4.2 MovieLens數據集實驗分析

MovieLens數據集本身比較龐大，涵蓋了多個用戶對多部電影的評級數據，也包括電影詳細數據信息和用戶個人屬性信息。由于該數據集很大，通過整理該數據集，提取用戶的ID和電影的ID，如果用戶喜歡該電影，則用戶和該電影之間就有一條連邊，用戶和電影分別屬于二分網絡的兩類節點。該數據集對應有943個用戶節點和1 682個電影節點，由這兩類節點組成一個二分網絡。

為了測試本文算法，將該數據集的所有鏈邊分為訓練集和測試集，在該數據集上分別對算法WLP、ELP和PLP進行10次實驗，訓練集占90%，測試集占10%。訓練集作為已知信息處理，測試集用來評估算法的準確性。結果如表3所示。

表3 Movielens上的三種方法實驗結果(AUC)比較

大部分情況下，WLP的精確度高于ELP和PLP，10次實驗中分別有2次和1次結果低于ELP和PLP，可見WLP算法可以保持高精度準確性，說明本文算法具有一定的有效性。

5 結 語

本文提出一個基于資源分配加權投影的二分網絡鏈路預測算法。該算法通過將二分網絡圖投影到一個圖上，并通過資源分配得到投影圖的權值，根據所得權值可以得到兩個不同類節點之間的相似性度量，根據節點的相似性度量預測鏈路存在的可能性。本文將算法WLP與ELP和PLP進行實驗比較，得出本文算法略優于其他兩種算法的性能。當然，本文算法還有可以改進的地方，比如資源分配的初始值是否可以定義為其他值或者針對加權二分網絡的資源分配研究，這些都是下一步需要進行研究的內容。