王 瑤,寇 月,申德榮,聶鐵錚,于 戈
東北大學(xué) 計算機(jī)科學(xué)與工程學(xué)院,沈陽 110819
隨著微博、知乎、豆瓣等社交網(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é),并指出下一步研究計劃。
最早的鏈路預(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ù)雜度。
給出兩個網(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)用戶之間形成連接的概率。
如圖1 所示,此模型包括跨社交網(wǎng)絡(luò)構(gòu)建、對節(jié)點特征進(jìn)行處理、元路徑的自動提取、提取潛在空間特征和預(yù)測四部分。
Fig.1 ACP-MF-LP model framework圖1 ACP-MF-LP模型框架
不失一般性,本文以兩個社交網(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ò)連接起來。
如圖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ù)測。
在屬性較多的情況下,例如在微博網(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個特征向量組成矩陣即為降維后的特征值矩陣。 元路徑為鏈路預(yù)測提取的特征,因此利用用戶節(jié)點的活躍度和邊的活躍度來選擇元路徑,之后計算每條元路徑的權(quán)重,衡量元路徑對預(yù)測的貢獻(xiàn)程度。 節(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主要的交互途徑。 兩個節(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è)置閾值是為了防止路徑無休止迭代下去。 按照以往元路徑不加以權(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ù)。 求解出元路徑及所有元路徑的權(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 利用樹的結(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)造 在真實的數(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)簽。 一般用于分類的算法應(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 集成分類流程圖 在本章中,基于提出的鏈路預(yù)測模型,在數(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)計 將本文提出的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。 (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)簽選擇影響 本文提出了一種將多個網(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è)計出更高效的特征選擇方法。5 基于節(jié)點活躍度和邊活躍度的元路徑選擇
5.1 元路徑下的節(jié)點活躍度
5.2 元路徑下的邊的活躍度
5.3 元路徑的權(quán)重計算
6 基于元路徑相似性矩陣的分解方法
7 優(yōu)化策略
7.1 利用樹結(jié)構(gòu)解決元路徑的選擇
7.2 節(jié)點類的選擇
7.3 基于集成分類器的模型優(yōu)化
8 實驗與分析
8.1 數(shù)據(jù)集
8.2 實驗設(shè)置及對比實驗
8.3 實驗和結(jié)果
9 總結(jié)