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

東北大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，沈陽 110819

1 引言

隨著微博、知乎、豆瓣等社交網(wǎng)絡(luò)的普及，在線社交網(wǎng)絡(luò)成為人們生活中必不可少的交流工具。依據(jù)第42 次《中國互聯(lián)網(wǎng)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計報告》[1]中的統(tǒng)計，2018 年我國互聯(lián)網(wǎng)的普及率為57.7%，網(wǎng)民規(guī)模有8.02 億，可以看出互聯(lián)網(wǎng)發(fā)展迅速。網(wǎng)絡(luò)中的鏈路預(yù)測是指通過已知的網(wǎng)絡(luò)節(jié)點以及網(wǎng)絡(luò)結(jié)構(gòu)等信息，預(yù)測網(wǎng)絡(luò)中尚未產(chǎn)生連邊的兩個節(jié)點之間產(chǎn)生鏈接的可能性[2]。

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

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

本文的主要貢獻(xiàn)如下：

（1）提出了一種結(jié)合節(jié)點活躍度和邊的活躍度的自動提取元路徑的跨社交網(wǎng)絡(luò)鏈路預(yù)測方法，通過錨鏈接將多網(wǎng)聯(lián)系到一起，提取符合要求的特征。該方法可以有效提取相似度高的元路徑，提高預(yù)測準(zhǔn)確性。

（2）提出了對元路徑相似性矩陣進(jìn)行矩陣分解的方法，獲得一個隱藏特征空間相似性的表示，將網(wǎng)絡(luò)中與目標(biāo)類型對象相關(guān)的元路徑信息顯示。該方法可以有效整合個性化信息在網(wǎng)絡(luò)中表現(xiàn)的社會特征。

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

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

2 相關(guān)工作

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

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

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

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

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

3 問題定義

給出兩個網(wǎng)絡(luò)1、網(wǎng)絡(luò)2和訓(xùn)練節(jié)點對的信息，利用查找出的元路徑對目標(biāo)節(jié)點對之間形成的鏈接概率進(jìn)行預(yù)測。本章主要介紹對跨社交網(wǎng)絡(luò)鏈路預(yù)測的定義及問題描述。

社交網(wǎng)絡(luò)上的鏈路預(yù)測是指通過對網(wǎng)絡(luò)中的信息進(jìn)行提取獲得特征，預(yù)測網(wǎng)絡(luò)中節(jié)點存在鏈接的可能性的大小。首先，給出相關(guān)概念；之后，在此基礎(chǔ)上給出基于元路徑提取和矩陣分解的跨社交網(wǎng)絡(luò)鏈路預(yù)測問題的描述；最后，給出相關(guān)的解決方案。

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

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

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

定義4（節(jié)點活躍度）節(jié)點在不同元路徑的活躍度不同，在某條元路徑上鄰居節(jié)點越多，代表在此元路徑上越活躍，對網(wǎng)絡(luò)結(jié)構(gòu)的影響越大。

定義5（邊活躍度）假設(shè)兩個節(jié)點的連邊在多條元路徑上均出現(xiàn)過，這條邊在網(wǎng)絡(luò)中的活躍度比其他邊要高。

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

4 基于元路徑選擇和矩陣分解的跨社交網(wǎng)絡(luò)鏈路預(yù)測模型

如圖1 所示，此模型包括跨社交網(wǎng)絡(luò)構(gòu)建、對節(jié)點特征進(jìn)行處理、元路徑的自動提取、提取潛在空間特征和預(yù)測四部分。

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

4.1 跨社交網(wǎng)絡(luò)構(gòu)建

不失一般性，本文以兩個社交網(wǎng)絡(luò)為例，介紹兩個網(wǎng)絡(luò)如何構(gòu)造關(guān)聯(lián)。如圖2 給定網(wǎng)絡(luò)G1、G2為微博和豆瓣兩個社交網(wǎng)絡(luò)，圖中用戶1和用戶2是同一實體在不同網(wǎng)絡(luò)上的同一用戶。利用這種連接關(guān)系將兩個網(wǎng)絡(luò)融合為一個網(wǎng)絡(luò)?？缟缃痪W(wǎng)絡(luò)的構(gòu)建是給定源網(wǎng)絡(luò)和中間的錨鏈接，確定目標(biāo)網(wǎng)絡(luò)中相關(guān)節(jié)點之間的鏈接的可能性大小。如圖2 為跨網(wǎng)絡(luò)的連接，圖2中有兩個網(wǎng)間鏈接，用戶1和用戶2是同一個用戶，用戶3和用戶4是同一個用戶。利用網(wǎng)間的錨鏈接[4]將兩個網(wǎng)絡(luò)連接起來。

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

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

（1）元路徑的自動選擇

已有方法基于的是給定的元路徑集合，現(xiàn)實的社交網(wǎng)絡(luò)數(shù)據(jù)巨大，對元路徑不能一一列舉，也不能充分地表示訓(xùn)練集合中用戶節(jié)點之間的關(guān)系，因此需要提出一種可以針對網(wǎng)絡(luò)進(jìn)行自動篩選元路徑的方法，能夠?qū)⑻崛〉脑窂教卣靼凑詹煌呢暙I(xiàn)權(quán)重表示出來。

Fig.2 Connect across social networks圖2 跨社交網(wǎng)絡(luò)連接

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

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

4.3 對節(jié)點特征進(jìn)行降維處理

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

輸入的源網(wǎng)絡(luò)中的節(jié)點V∈(V,I)，V表示節(jié)點的集合(V1,V2,…,Vm)，I表示節(jié)點的屬性(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的協(xié)方差矩陣Cn×n

11.求出協(xié)方差矩陣的特征值及對應(yīng)的特征向量

12.對特征值進(jìn)行排序求前k個特征值對應(yīng)的特征向量組成矩陣A′m×k

13.輸出A′m×k

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

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

元路徑為鏈路預(yù)測提取的特征，因此利用用戶節(jié)點的活躍度和邊的活躍度來選擇元路徑，之后計算每條元路徑的權(quán)重，衡量元路徑對預(yù)測的貢獻(xiàn)程度。

5.1 元路徑下的節(jié)點活躍度

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

元路徑p下的節(jié)點u的活躍度為：

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

5.2 元路徑下的邊的活躍度

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

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

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

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

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

1.建立初始結(jié)構(gòu)，把元路徑候選集插入T

2.WhileT??do

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

4.W←選擇候選集T中相似性分?jǐn)?shù)S最大的集合

5.For每個節(jié)點對(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每個節(jié)點對(i,j)∈Wdo

15. Forj的鄰居節(jié)點s∈Vdo

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

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

18.將ed加入到E中；

19.Π←E中元路徑；

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

21.End for

22.End for

23. For每個結(jié)構(gòu)K∈Edo

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

25.IfK.S>θthen

26.將結(jié)構(gòu)K加入候選集T；

27. End if

28.End for

29.Returnγ,M

算法的5～8 行是對節(jié)點對之間的相似性進(jìn)行計算；9～12 行是對相似性分?jǐn)?shù)值最高的候選集對應(yīng)的元路徑進(jìn)行提??；13～23行對節(jié)點對進(jìn)行廣度優(yōu)先搜索，把元路徑的種類列舉出來；24～29 行把閾值內(nèi)的集合加入候選集中，設(shè)置閾值是為了防止路徑無休止迭代下去。

5.3 元路徑的權(quán)重計算

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

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

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

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

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

求解出元路徑及所有元路徑的權(quán)重ωi=[ω1,ω2,…,ωi]后，對每條元路徑對應(yīng)的結(jié)構(gòu)特征進(jìn)行加權(quán)組合，得出節(jié)點之間的相似性矩陣，然后使用矩陣分解MF選擇潛在空間最大的特征向量，發(fā)現(xiàn)節(jié)點之間潛在特征，去除不同元路徑之間的相關(guān)性。

具體的算法流程如下：

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

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

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

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

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)

/*基于梯度下降的優(yōu)化方法，將元素更新*/

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

/*基于梯度下降的優(yōu)化方法，將元素更新*/

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 優(yōu)化策略

7.1 利用樹結(jié)構(gòu)解決元路徑的選擇

利用樹的結(jié)構(gòu)有三方面的優(yōu)勢：首先在啟發(fā)式的搜索方式中可以減少搜索空間，其次計算多個節(jié)點對的元路徑可以最大限度地減少共同計算的次數(shù)，通過使用樹結(jié)構(gòu)顯示可能出現(xiàn)的路徑；樹結(jié)構(gòu)可以回溯重新使用，進(jìn)行多次擴(kuò)展。

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

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

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

輸出：元路徑p。

數(shù)據(jù)：樹T。

1.初始化根節(jié)點T

2.Whileu可以擴(kuò)展do

3.While 節(jié)點n是u的鄰居and 樹的深度

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

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

6.將T的子節(jié)點作為T繼續(xù)進(jìn)行搜索，直到不符合條件為止；

7.End if

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

Fig.4 Structure of tree圖4 樹的構(gòu)造

7.2 節(jié)點類的選擇

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

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

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

7.3 基于集成分類器的模型優(yōu)化

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

Fig.5 Node tag圖5 節(jié)點類標(biāo)簽

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

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

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

8 實驗與分析

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

8.1 數(shù)據(jù)集

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

Table 1 Weibo-Douban statistics of datasets表1 微博-豆瓣數(shù)據(jù)集統(tǒng)計

8.2 實驗設(shè)置及對比實驗

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

PathSim[9]：每條元路徑是按相同的權(quán)重進(jìn)行計算，即按兩個對象之間元路徑的條數(shù)進(jìn)行計算。

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

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

ACP-T：優(yōu)化查找元路徑的方法。

實驗環(huán)境：Intel?CoreTMi7-6700，8GB內(nèi)存，3.40GHz，操作系統(tǒng)Windows 8。

8.3 實驗和結(jié)果

（1）預(yù)測性能比較

Fig.7 ROC curve圖7 ROC曲線

由圖7可以看出，ACP相較于其他方法可以選出更有用的元路徑表示節(jié)點之間的關(guān)系，在實驗參數(shù)選擇最優(yōu)的情況下，可以看出本文提出的算法在精確度ROC上優(yōu)于基礎(chǔ)算法。

（2）權(quán)重的影響

提取的元路徑的權(quán)重可以分為：設(shè)為統(tǒng)一的權(quán)重1，即為PathSim 的方法；設(shè)為隨機(jī)的元路徑權(quán)重；設(shè)為經(jīng)過學(xué)習(xí)的權(quán)重。很明顯，由圖8 可以看出，通過權(quán)重學(xué)習(xí)的元路徑預(yù)測效果要好于其他兩種。由于基于隨機(jī)分配的權(quán)重可能使得關(guān)聯(lián)程度大的元路徑分的權(quán)重小，因此基于隨機(jī)的元路徑權(quán)重效果最差。

Fig.8 Influence of weight圖8 權(quán)重影響

（3）訓(xùn)練集大小的影響

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

Fig.9 Influence of training size圖9 訓(xùn)練集大小影響

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

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

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

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

Fig.11 Influence of parameter圖11 參數(shù)影響

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

（5）運(yùn)行時間比較

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

（6）類標(biāo)簽的選擇

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

Fig.12 Running time圖12 運(yùn)行時間

Fig.13 Influence of label selection圖13 類標(biāo)簽選擇影響

9 總結(jié)

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