元路徑選擇和矩陣分解的跨社交網(wǎng)絡(luò)鏈路預(yù)測(cè)*

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

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

1 引言

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

3 問(wèn)題定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）元路徑的自動(dòng)選擇

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

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

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

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

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

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

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

算法1特征處理算法

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

輸出：降維后的特征矩陣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é)方差矩陣的特征值及對(duì)應(yīng)的特征向量

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

13.輸出A′m×k

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

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

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

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

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

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

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

5.2 元路徑下的邊的活躍度

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

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

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

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

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

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

2.WhileT??do

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

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

5.For每個(gè)節(jié)點(diǎn)對(duì)(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.新建一個(gè)空的集合E；

14. For每個(gè)節(jié)點(diǎn)對(duì)(i,j)∈Wdo

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

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

17.IfE中沒(méi)有這種邊的類型then

18.將ed加入到E中；

19.Π←E中元路徑；

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

21.End for

22.End for

23. For每個(gè)結(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 行是對(duì)節(jié)點(diǎn)對(duì)之間的相似性進(jìn)行計(jì)算；9～12 行是對(duì)相似性分?jǐn)?shù)值最高的候選集對(duì)應(yīng)的元路徑進(jìn)行提取；13～23行對(duì)節(jié)點(diǎn)對(duì)進(jìn)行廣度優(yōu)先搜索，把元路徑的種類列舉出來(lái)；24～29 行把閾值內(nèi)的集合加入候選集中，設(shè)置閾值是為了防止路徑無(wú)休止迭代下去。

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

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

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

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

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

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

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

具體的算法流程如下：

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

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

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

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/*計(jì)算每一次迭代后損失值*/

17.Ifloss<τ

18.Break

19.End for

20.ReturnMiK、MKj、M′ij

7 優(yōu)化策略

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

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

在圖4 中，每個(gè)樹(shù)的節(jié)點(diǎn)存儲(chǔ)的是一系列節(jié)點(diǎn)對(duì)，樹(shù)的邊存儲(chǔ)的是元路徑的種類。

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

輸入：圖G，節(jié)點(diǎn)對(duì)g(u,v)，元路徑長(zhǎng)度l。

輸出：元路徑p。

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

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

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

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

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

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

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

7.End if

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

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

7.2 節(jié)點(diǎn)類的選擇

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

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

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

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

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

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

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

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

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

8 實(shí)驗(yàn)與分析

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

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

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

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

8.2 實(shí)驗(yàn)設(shè)置及對(duì)比實(shí)驗(yàn)

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

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

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

ACP：本文提出的自動(dòng)選擇元路徑的方法。

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

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

8.3 實(shí)驗(yàn)和結(jié)果

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

Fig.7 ROC curve圖7 ROC曲線

由圖7可以看出，ACP相較于其他方法可以選出更有用的元路徑表示節(jié)點(diǎn)之間的關(guān)系，在實(shí)驗(yà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)過(guò)學(xué)習(xí)的權(quán)重。很明顯，由圖8 可以看出，通過(guò)權(quán)重學(xué)習(xí)的元路徑預(yù)測(cè)效果要好于其他兩種。由于基于隨機(jī)分配的權(quán)重可能使得關(guān)聯(lián)程度大的元路徑分的權(quán)重小，因此基于隨機(jī)的元路徑權(quán)重效果最差。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

9 總結(jié)

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