元路徑選擇和矩陣分解的跨社交網絡鏈路預測*

王 瑤，寇 月，申德榮，聶鐵錚，于 戈

東北大學 計算機科學與工程學院，沈陽 110819

1 引言

隨著微博、知乎、豆瓣等社交網絡的普及，在線社交網絡成為人們生活中必不可少的交流工具。依據第42 次《中國互聯網網絡發展狀況統計報告》[1]中的統計，2018 年我國互聯網的普及率為57.7%，網民規模有8.02 億，可以看出互聯網發展迅速。網絡中的鏈路預測是指通過已知的網絡節點以及網絡結構等信息，預測網絡中尚未產生連邊的兩個節點之間產生鏈接的可能性[2]。

在現實世界里，信息實體是廣泛連接的，通過各種各樣的連接彼此相互關聯，這些連接一起形成不同領域的信息社交網絡[3]。現有的鏈路預測研究工作主要涉及單一的社交網絡，通過分析社交網絡內用戶的結構特征，找出兩個節點之間存在鏈接的可能性。實際上，面向多個社交網絡上的鏈路預測也具有重要意義，單一的網絡可能不能滿足需求，且單一網絡提供的用戶信息不如多個社交網絡用戶信息豐富。利用多個網絡上錨鏈接[4]用戶進行網與網連通之后，目標網絡的節點信息可以通過源網絡的節點信息得到補充，克服由于數據信息稀疏造成的冷啟動問題。然而，當前研究具有如下的局限性：（1）網絡數據稀疏，發現的鏈接只占所有鏈接的小部分，節點特征復雜，節點特征篩選方法不夠明確，屬性和數據字段利用率不高，節點相關性依賴于網絡的特點，不能直接包含在網絡中，挖掘信息不夠充分；（2）元路徑表示信息較少，基于給定的元路徑不能全面地捕捉節點之間信息；（3）對于異構社交網絡的鏈路預測研究較少，大部分在同構網絡中進行研究。

本文研究了基于元路徑的跨社交網絡的鏈路預測。例如，為了在微博中選擇可能感興趣的用戶推薦給特定用戶，需要分析用戶之間的偏好、朋友關系等一系列特征。同時，依據豆瓣轉發至微博的用戶群體在豆瓣網上分享電影以及對電影的評分等信息，對用戶喜愛偏好進行篩選，偏好相似的用戶形成連接的可能性越大。

本文的主要貢獻如下：

（1）提出了一種結合節點活躍度和邊的活躍度的自動提取元路徑的跨社交網絡鏈路預測方法，通過錨鏈接將多網聯系到一起，提取符合要求的特征。該方法可以有效提取相似度高的元路徑，提高預測準確性。

（2）提出了對元路徑相似性矩陣進行矩陣分解的方法，獲得一個隱藏特征空間相似性的表示，將網絡中與目標類型對象相關的元路徑信息顯示。該方法可以有效整合個性化信息在網絡中表現的社會特征。

（3）提出了基于元路徑選擇和矩陣分解的ACPMF-LP（autochoose path-matrix factorization-link prediction）時間復雜度上優于對比算法。

本文第2章介紹了鏈路預測的相關工作；第3章對本文問題進行定義；第4章提出基于元路徑選擇和矩陣分解的跨網絡鏈路預測模型；第5章提出基于節點和邊的活躍度的元路徑提取方法；第6章提出了對相似性矩陣的分解；第7章對相應方法進行優化；第8章為實驗部分，對提出的模型和算法進行測試；最后對全文進行總結，并指出下一步研究計劃。

2 相關工作

最早的鏈路預測問題是由Liben-Nowell和Kleinberg[5]提出，他們利用鄰居節點或路徑信息等非監督方法計算相似度值，有Adamic-Adar、Jacard、SimRank、Katz 等指標。接著，Hasan 等人[6]將局部社交網絡轉換為拓撲圖進行預測，提高了預測結果，并利用監督方法將相似性轉換為特征向量，即轉換為二分類問題進行研究。Lv[7]將鏈路預測分為三個研究方向，分別是：（1）基于相似性方法；（2）基于最大似然；（3）概率模型。

近年來，隨著網絡規模不斷擴大，一些預測方法無法適應網絡的變化，達不到令人滿意的計算速度和計算效果[8]，因此又相繼提出了同構網絡和異構網絡的概念。同構網絡即節點和邊為單一種類的實體，異構網絡是節點和邊為多種實體的網絡。并在異構網絡的基礎上提出了跨網的鏈路預測問題。鏈路預測中基本思路是挖掘特征，特征包括兩方面：節點和邊。

針對單網上的社交網絡鏈路預測研究，Han 等人[9]提出了異構社交網絡上基于元路徑PathSim的相似性指標，即將節點對通過不同的關系進行連接，衡量相同類型對象的相似性，但不具有廣泛的適應性。為了衡量不同類型節點的相似性，Ni等人[10]提出了基于路徑的隨機游走模型，但從路徑兩端分別游走的結果不相同，非對稱條件限制了其應用環境。Shi 等人[11]提出了HeteSim 算法度量異構網絡中任意節點對的相似性，可以計算不同類型的對象且有對稱性；但該方法復雜度高，而且對路徑的長度按照奇偶分類比較繁瑣。Shang等人[12]提出了基于元路徑的ESim 相似性指標的鏈路預測方法;上述方法中均是在單網上提取元路徑，沒有涉及多網問題，且元路徑是固定給定的，靈活性差，不能準確地切合語境，顯示節點之間的本質聯系；其他方法主要集中于提取特征和構造模型，對于機器學習難以表達的復雜細節很難識別。

針對網絡耦合方面，網絡耦合是將高維網絡轉換為低維空間上相對應的節點，降維后的網絡計算鏈路預測更加便捷。Huang 等人[13]提出了對異構網絡的耦合，利用不同節點之間的連邊信息刻畫不同的元路徑，利用損失函數最小化后計算距離進行預測。Swami 等人[14]使用meta-path 的隨機游走重構節點的鄰居，并運用異構的skip-gram[15]模型求解節點的網絡表示,上述方法均在單網上進行研究。

與已有工作相比，本文工作具有如下優勢：（1）將多個社交網絡中可能存在的鏈接關系應用元路徑自動提取算法進行分類，運用在大規模信息網絡中。（2）利用矩陣分解轉化為低維、稠密、實值的向量表示網絡中的節點，含有語義關系，利于計算存儲，自適應性強，且可以將異質信息投影到同一個低維空間中方便進行預測。（3）利用優化策略減少計算時間復雜度。

3 問題定義

給出兩個網絡1、網絡2和訓練節點對的信息，利用查找出的元路徑對目標節點對之間形成的鏈接概率進行預測。本章主要介紹對跨社交網絡鏈路預測的定義及問題描述。

社交網絡上的鏈路預測是指通過對網絡中的信息進行提取獲得特征，預測網絡中節點存在鏈接的可能性的大小。首先，給出相關概念；之后，在此基礎上給出基于元路徑提取和矩陣分解的跨社交網絡鏈路預測問題的描述；最后，給出相關的解決方案。

定義1（社交網絡）給定G(V,E)來表示社交網絡，其中V代表用戶集合，E代表用戶間的關系集合。

定義2（網間鏈接）存在于多個網絡之間的網間鏈接，例如給定兩個異構社交網絡Gs、Gt，以及兩個用戶vi∈Vs?Gs,vj∈Vt?Gt，即vi和vj是兩個不同社交網絡的用戶節點集合，若在現實生活中兩個用戶為同一個用戶，則稱兩者之間存在鏈接。

定義3（元路徑[8]）定義在網絡模式上的存在鏈接的兩類對象的一條路徑，即表示對象類型之間的一種復合關系，R1°R2°…°Rl，其中°代表關系之間的復合關系，Ai表示對象類型，Ri表示關系類型。

定義4（節點活躍度）節點在不同元路徑的活躍度不同，在某條元路徑上鄰居節點越多，代表在此元路徑上越活躍，對網絡結構的影響越大。

定義5（邊活躍度）假設兩個節點的連邊在多條元路徑上均出現過，這條邊在網絡中的活躍度比其他邊要高。

定義6（基于元路徑耦合的跨社交網絡鏈路預測）給出m個社交網絡的用戶信息社交圖Gi(i=1,2,…,m)，給出在網絡Gi中兩個目標對象(i,j)，找出兩個目標用戶之間形成連接的概率。

4 基于元路徑選擇和矩陣分解的跨社交網絡鏈路預測模型

如圖1 所示，此模型包括跨社交網絡構建、對節點特征進行處理、元路徑的自動提取、提取潛在空間特征和預測四部分。

Fig.1 ACP-MF-LP model framework圖1 ACP-MF-LP模型框架

4.1 跨社交網絡構建

不失一般性，本文以兩個社交網絡為例，介紹兩個網絡如何構造關聯。如圖2 給定網絡G1、G2為微博和豆瓣兩個社交網絡，圖中用戶1和用戶2是同一實體在不同網絡上的同一用戶。利用這種連接關系將兩個網絡融合為一個網絡。跨社交網絡的構建是給定源網絡和中間的錨鏈接，確定目標網絡中相關節點之間的鏈接的可能性大小。如圖2 為跨網絡的連接，圖2中有兩個網間鏈接，用戶1和用戶2是同一個用戶，用戶3和用戶4是同一個用戶。利用網間的錨鏈接[4]將兩個網絡連接起來。

4.2 ACP-MF-LP模型的基本思想

如圖1 所示是基于元路徑選擇和矩陣分解的ACP-MF-LP 鏈路預測模型框架，首先對網絡節點進行特征處理，之后利用節點和邊的活躍度利用ACP算法對元路徑進行提取，對元路徑進行整合后計算相似性矩陣并進行矩陣分解，最后利用集成分類方法選擇最優解結果。

（1）元路徑的自動選擇

已有方法基于的是給定的元路徑集合，現實的社交網絡數據巨大，對元路徑不能一一列舉，也不能充分地表示訓練集合中用戶節點之間的關系，因此需要提出一種可以針對網絡進行自動篩選元路徑的方法，能夠將提取的元路徑特征按照不同的貢獻權重表示出來。

Fig.2 Connect across social networks圖2 跨社交網絡連接

（2）基于相似性矩陣的分解

將提取的元路徑按照不同的權重整合后對給定的用戶節點進行預測，得到對用戶之間相似性的衡量矩陣，對相似性矩陣指標進行矩陣分解，可以得出在隱藏空間中的相似性特征，從而更好地進行鏈路分析預測。

4.3 對節點特征進行降維處理

在屬性較多的情況下，例如在微博網絡中，一個用戶的屬性可能包含用戶名、愛好、關注用戶、關注話題、轉發話題等一系列特征。這些特征之間可能存在相關性，不利于對特征進行挖掘；因此采用主成分分析（principal component analysis，PCA）方法對數據屬性進行降維，在確保數據信息丟失最少的原則下，用較少的綜合變量代替較多的變量，且變量之間的相關性最小。

輸入的源網絡中的節點V∈(V,I)，V表示節點的集合(V1,V2,…,Vm)，I表示節點的屬性(I1,I2,…,In)，將這n維特征映射到k維上(k

算法1特征處理算法

輸入：特征屬性矩陣Am×n，k為需要提取的k個特征。

輸出：降維后的特征矩陣A'm×k。

1.Fori=1 tom

2.Forj=1 ton

3.uji=+aji

4.End for

6.Forj=1 ton

8.End for

9.End for

10.求出矩陣A′m×n的協方差矩陣Cn×n

11.求出協方差矩陣的特征值及對應的特征向量

12.對特征值進行排序求前k個特征值對應的特征向量組成矩陣A′m×k

13.輸出A′m×k

算法的1～5 行為將矩陣的每一列屬性進行均值化；6～9 行對每一列屬性進行零均值化；10 行求出零均值后矩陣的協方差矩陣；11 行計算協方差矩陣的特征值和特征向量；12～13 行從大到小將特征值對應的前k個特征向量組成矩陣即為降維后的特征值矩陣。

5 基于節點活躍度和邊活躍度的元路徑選擇

元路徑為鏈路預測提取的特征，因此利用用戶節點的活躍度和邊的活躍度來選擇元路徑，之后計算每條元路徑的權重，衡量元路徑對預測的貢獻程度。

5.1 元路徑下的節點活躍度

節點在不同元路徑下的活躍度：兩個對象之間可能在不同領域形成連接，在某個元路徑下的鄰居數越多，互相影響越大，可能形成連接的可能性越大。因此，可對節點在某個元路徑下的活躍程度進行衡量。

元路徑p下的節點u的活躍度為：

其中，Γu,p是節點u在元路徑p條件下的鄰居節點集合，|Γu,p|是節點u在元路徑p下的鄰居節點數，|Γu,P|是節點u在網絡中的所有元路徑P中鄰居節點數。假設在元路徑p下的節點u的鄰居數量占總鄰居數量的比例越高，說明在元路徑p下節點的活躍度高，這條元路徑是u主要的交互途徑。

5.2 元路徑下的邊的活躍度

兩個節點間的連邊在多條元路徑下都存在，說明這條邊關系緊密；其次，邊的活躍度計算有助于消除節點間建立關系時的條件影響。例如在元路徑p1條件下兩個節點建立20次關系，而在元路徑p2 條件下建立5次關系，如果選擇了元路徑p2，則建立條件較低可能會帶來弱關系的連邊。因此，通過建立邊的活躍度可以降低產生弱連接的概率。

元路徑p下的邊e的活躍度為：

算法2自動篩選元路徑算法ACP(G,φ)

輸入：G=(V,E)，φ為訓練的節點集合，θ為閾值。

輸出：γ為選擇的元路徑集合，M為在元路徑γ下每個訓練集合的相似性矩陣。

1.建立初始結構，把元路徑候選集插入T

2.WhileT??do

3.m←{0,0,…,0};/*長度為|φ|，訓練集節點對在元路徑上匹配的相似性*/

4.W←選擇候選集T中相似性分數S最大的集合

5.For每個節點對(i,j)∈Wdo

6. If(i,j)∈φthen

7.m←S=VA(i,p)*VA(j,p)*EA(ij,p);end for

8.Ifm中有非0元素then

9.將W中的元路徑Π加入到γ中

10.M←M?m；

11.Break；

12.Else

13.新建一個空的集合E；

14. For每個節點對(i,j)∈Wdo

15. Forj的鄰居節點s∈Vdo

16.ed←j到s節點的邊的類型，d=1 表示正向，d=-1表示反方向；

17.IfE中沒有這種邊的類型then

18.將ed加入到E中；

19.Π←E中元路徑；

20.計算m(i,s)的值；

21.End for

22.End for

23. For每個結構K∈Edo

24.K.S=∑m(i,j)

25.IfK.S>θthen

26.將結構K加入候選集T；

27. End if

28.End for

29.Returnγ,M

算法的5～8 行是對節點對之間的相似性進行計算；9～12 行是對相似性分數值最高的候選集對應的元路徑進行提取；13～23行對節點對進行廣度優先搜索，把元路徑的種類列舉出來；24～29 行把閾值內的集合加入候選集中，設置閾值是為了防止路徑無休止迭代下去。

5.3 元路徑的權重計算

按照以往元路徑不加以權重區分的情況下，例如圖3是微博中對用戶-話題-用戶（U-T-U）這條元路徑進行計算時相對應的用戶之間相似性矩陣。利用PathSim 計算，針對不同的用戶用同樣的權重衡量時，則用戶之間的相似性如圖3 上部分所示，用戶2和用戶1、用戶3之間均存在相似性；而實際情況是在相同的話題上用戶1和用戶3更具有一致的偏向性，即擁有相同興趣愛好，形成鏈接的可能性越大。因此，元路徑針對不同的用戶權重也不相同，從而對元路徑權重進行衡量，能使得預測模型更有針對性。

Fig.3 User similarity by different weights on meta-path圖3 不同權重元路徑衡量用戶相似性

權重的大小衡量了元路徑在用戶關系之間起的作用，兩個用戶在某條元路徑下相似性大，關系緊密，但在另一條元路徑下，關系稀疏。因此，不同元路徑對同一實體相似性的衡量指標不同。對提取出來的元路徑進行整合，計算不同元路徑對網絡的影響權值，設置每條元路徑Π的權值ωi(i=1,2,…,|γ|)，且，使用分類方法中的線性回歸對g(ω)={ω1M1+，其中Mi是訓練集在每條元路徑下的相似性值的大小，對{ω1,ω2,…,ωγ}進行訓練，設置目標函數為，利用批量梯度下降的方法迭代更新ω的值。

最后一項是為了防止過擬合，{ω1,ω2,…,ωγ}為不同元路徑對預測產生的影響程度，即各個元路徑特征在預測中的作用，基于訓練集的線性回歸方法獲得{ω1,ω2,…,ωγ}的值。g(ω)的值為兩個節點在元路徑下的相似性分數。

6 基于元路徑相似性矩陣的分解方法

求解出元路徑及所有元路徑的權重ωi=[ω1,ω2,…,ωi]后，對每條元路徑對應的結構特征進行加權組合，得出節點之間的相似性矩陣，然后使用矩陣分解MF選擇潛在空間最大的特征向量，發現節點之間潛在特征，去除不同元路徑之間的相關性。

具體的算法流程如下：

算法3提取潛在空間特征的矩陣分解算法

輸入：根據元路徑得到的相似性矩陣Mij、迭代次數steps，選擇K維，正則化參數α、β，閾值τ。

輸出：矩陣分解后的矩陣MiK、MKj、M′ij。MiK和MKj為矩陣分解后的特征矩陣，M′ij為矩陣分解后節點之間相似性矩陣。

1.MiK、MKj～N(0,δ2)/*根據正態分布矩陣變量初始化，生成隨機矩陣*/

2.Forstep∈(0,steps)do

3.Forp∈(0,i)do

4. Forq∈(0,j)do

5.error=Mpq

6. Fork∈(0,K)do

7.error-=Mpk×Uqk

8. Fork∈(0,K)do

9.Mpk+=α(2×error×Mqk-βMqk)

/*基于梯度下降的優化方法，將元素更新*/

10.Mkq+=α(2×error×Mpk-βMkq)

/*基于梯度下降的優化方法，將元素更新*/

11.M′pq=Mpk×Mkq

12. End for

13.End for

14.End for

15.loss=0

16.loss+=(M′pq-error)2/*計算每一次迭代后損失值*/

17.Ifloss<τ

18.Break

19.End for

20.ReturnMiK、MKj、M′ij

7 優化策略

7.1 利用樹結構解決元路徑的選擇

利用樹的結構有三方面的優勢：首先在啟發式的搜索方式中可以減少搜索空間，其次計算多個節點對的元路徑可以最大限度地減少共同計算的次數，通過使用樹結構顯示可能出現的路徑；樹結構可以回溯重新使用，進行多次擴展。

在圖4 中，每個樹的節點存儲的是一系列節點對，樹的邊存儲的是元路徑的種類。

算法4元路徑搜索樹的算法ACP-T（AutoChoose-Path-Tree）（G，g，l）

輸入：圖G，節點對g(u,v)，元路徑長度l。

輸出：元路徑p。

數據：樹T。

1.初始化根節點T

2.Whileu可以擴展do

3.While 節點n是u的鄰居and 樹的深度

4.將(u,n)加入到T的一個節點的集合中；

5.并將根節點到邊類型作為一條元路徑放入p中；

6.將T的子節點作為T繼續進行搜索，直到不符合條件為止；

7.End if

8.輸出符合要求的元路徑集合p

Fig.4 Structure of tree圖4 樹的構造

7.2 節點類的選擇

在真實的數據集中，節點可以有很多類。例如：微博中某個明星既有演員的身份，又有作家的身份。這些類如果不按一定的規則約束，會增加滿足元路徑的條數，之前的方法并沒有規定節點的類型，這里提出規范節點類型的方法。即用標簽的分數LableScore確定節點類的屬性。

其中，a(φ)是節點對中符合類型的數量，b(φ)是在數據集中符合類型的數量。

如圖5 是將節點的標簽列舉出來。例如：節點（明星）對應圖4中（1,2）和（3,4），即節點對有2個，則a(φ)=2，在整個數據集中，假設有b(φ)=42 個，則，比其他節點標簽按分數值計算得要大，因此將明星作為節點的類標簽，作為元路徑中的節點標簽。

7.3 基于集成分類器的模型優化

一般用于分類的算法應用于鏈路預測問題上時，都會忽略樣本少的類別，達到最大化總體分類的精度，因此不能得到很好的分類效果。

Fig.5 Node tag圖5 節點類標簽

在鏈路預測問題中，正例樣本和負例樣本的數據不平衡是普遍存在的，因此將數據分為多個同少數類樣本數相同的數據，獲得多個相同數量的數據子集。對每個數據子集進行學習，建立多個分類器，最后通過投票方法集成分類器，使得集成的分類數據效果最好。

如圖6 所示，這部分由平衡數據、創建基本分類器、集成分類器三部分組成。這樣做既沒有添加網絡額外信息，也沒有忽略原有信息，保持了樣本分類情況。采取將大多數類隨機取樣，無放回地放入每個集合中，這樣保證每個訓練集合中正例和負例的樣本數量相等，就能避免數據不平衡的問題。

Fig.6 Ensemble classification flow chart圖6 集成分類流程圖

8 實驗與分析

在本章中，基于提出的鏈路預測模型，在數據集微博-豆瓣上測試本文提出的算法。

8.1 數據集

本文使用的數據集為真實的微博-豆瓣數據集，微博-豆瓣數據集包括抓取的用戶信息，用戶之間的評論和關注話題，豆瓣用戶以及用戶對電影評分、電影導演及演員等信息。具體信息如表1 所示。在提取元路徑時選擇閾值θ為0.8。

Table 1 Weibo-Douban statistics of datasets表1 微博-豆瓣數據集統計

8.2 實驗設置及對比實驗

將本文提出的ACP 算法與已有的算法進行對比。評價指標：一是AUC（area under curve），用來衡量鏈路預測算法的精確度；二是精確度Precision，定義在前L個預測邊中預測準確的比例；三是運行時間。本文比較了以下算法在表1 數據集上的運行效果。

PathSim[9]：每條元路徑是按相同的權重進行計算，即按兩個對象之間元路徑的條數進行計算。

PCRW（path-constrained random walks）[16]：基于隨機游走的相似性計算方法，利用路徑衡量對象之間游走的相似性大小。PCRW-X中X代表的是元路徑的長度，即元路徑規定在2到4之間取值。

ACP：本文提出的自動選擇元路徑的方法。

ACP-T：優化查找元路徑的方法。

實驗環境：Intel?CoreTMi7-6700，8GB內存，3.40GHz，操作系統Windows 8。

8.3 實驗和結果

（1）預測性能比較

Fig.7 ROC curve圖7 ROC曲線

由圖7可以看出，ACP相較于其他方法可以選出更有用的元路徑表示節點之間的關系，在實驗參數選擇最優的情況下，可以看出本文提出的算法在精確度ROC上優于基礎算法。

（2）權重的影響

提取的元路徑的權重可以分為：設為統一的權重1，即為PathSim 的方法；設為隨機的元路徑權重；設為經過學習的權重。很明顯，由圖8 可以看出，通過權重學習的元路徑預測效果要好于其他兩種。由于基于隨機分配的權重可能使得關聯程度大的元路徑分的權重小，因此基于隨機的元路徑權重效果最差。

Fig.8 Influence of weight圖8 權重影響

（3）訓練集大小的影響

實驗比較了不同訓練集大小對預測準確性的影響，從圖9 可以看出，在一定范圍內隨著訓練集數目增多，預測效果變好；訓練集數目超過一定范圍之后，訓練集的大小對預測結果影響不大；因為訓練集數量少不能挖掘充分的元路徑，訓練集過多則可能導致引入過多的噪音，所以設置合適的訓練集可以節省空間和訓練性能高的預測模型。

Fig.9 Influence of training size圖9 訓練集大小影響

（4）矩陣分解中K、α、β值選擇

在實驗數據集上，選取正則化參數α、β和閾值τ為最優值的前提下，觀察K取值不同對實驗結果造成的影響。由圖10可以看出，隨著K取值的增加，實驗結果AUC的值也在不斷增加，當AUC值增加到一定值時，隨著K的增加，AUC 值趨于平緩；由此看出K的選擇過小，用戶之間的隱式特征不能很好地表現出來，如果K值過大，則計算的復雜度就會增大，造成過擬合。

Fig.10 Influence of K圖10 K值影響

在K=15 且α選擇取最優值的前提下，圖11 是β在區間[0,0.2]上的預測精度。由圖11可以看出，β參數的改變能夠影響預測精度，在某個區間呈現上升趨勢，在β=0.08 時達到最優值。

Fig.11 Influence of parameter圖11 參數影響

在K=15 且β選擇取最優值的前提下，圖11是α在區間[0,0.1]上的預測精度。由圖11可以看出，α參數改變能夠影響預測精度，在α=0.02 時達到最優值。

（5）運行時間比較

實驗比較了幾種算法在元路徑固定長度為2～4下的運行時間以及不同訓練集下時運行時間的比較。從圖12可以看出，在給定元路徑長度的情況下，隨著訓練集數目的增多，運行時間也在增加，總體上本文提出的算法在運行時間上優于對比算法；隨著元路徑數目的增加，基于隨機游走的方法PCRW-2到PCRW-4運行時間明顯增加，本文提出的算法更適用于元路徑數目較多的情況下；在此基礎上，提出利用樹結構存儲元路徑，可以便于遍歷和回溯，能夠有效提高運行時間。

（6）類標簽的選擇

在選擇類標簽的時候，最好的方法是選擇最具代表性、LabelScore分數高的類別作為元路徑節點對象，實驗比較了進行類標簽選擇和不進行類標簽選擇情況下的ROC的值。從圖13可以看出，進行Label Select之后預測效率提升。

Fig.12 Running time圖12 運行時間

Fig.13 Influence of label selection圖13 類標簽選擇影響

9 總結

本文提出了一種將多個網絡聯系到一起進行鏈路預測的模型。提出了一種結合節點活躍度和邊活躍度的自動提取元路徑的方法，在此基礎上改進方法，從而實現對特征提取的目的，解決了對于用戶給定元路徑造成信息提取不夠完善的弊端。本文提出的鏈路預測方法通過實驗證明在召回率、準確率和運行時間上達到基本滿意的效果。下一步，將本文的預測方法擴展到動態的多個網絡，使其更加符合現實情況，并設計出更高效的特征選擇方法。