異質(zhì)信息網(wǎng)絡(luò)鏈接預(yù)測研究與新發(fā)展

張 悅, 王曉丹, 卜霄菲, 孫 可

(沈陽師范大學(xué) 軟件學(xué)院, 沈陽 110034)

0 引 言

數(shù)以萬計的互聯(lián)網(wǎng)用戶通過互動等自組織方式構(gòu)成了在線社交網(wǎng)絡(luò)(online social network, OSN),是現(xiàn)實世界的社交網(wǎng)絡(luò)與虛擬網(wǎng)絡(luò)的相關(guān)映射,其本質(zhì)體現(xiàn)了社交網(wǎng)絡(luò)用戶間的關(guān)系。

鏈接預(yù)測是社交網(wǎng)絡(luò)中的一個基本問題,受到計算機科學(xué)[1-3]、網(wǎng)絡(luò)科學(xué)[4-5]、生物學(xué)[6-10]等不同研究領(lǐng)域的廣泛關(guān)注。通常,鏈接預(yù)測問題可形式化為:給定T時刻網(wǎng)絡(luò)的快照,預(yù)測在接下來的T+1時刻將生成哪些鏈接,即預(yù)測和推薦未知的鏈接。

Liben-Nowell和Kleinber首次提出并系統(tǒng)地研究了預(yù)測用戶間新鏈接的問題。此后,該問題受到了學(xué)術(shù)界的廣泛關(guān)注?；谕|(zhì)性或“物以類聚”的原則,Liben-Nowell等人采用無監(jiān)督學(xué)習(xí)的方法處理鏈接預(yù)測問題。此類問題主要基于用戶節(jié)點的結(jié)構(gòu)或內(nèi)容相似性實現(xiàn)。

國內(nèi),呂琳媛和周濤[11]總結(jié)了鏈接預(yù)測領(lǐng)域相關(guān)研究,率先發(fā)表關(guān)于鏈接預(yù)測研究的綜述,介紹鏈接預(yù)測背景和意義、定義及問題、經(jīng)典算法、評價指標(biāo)及應(yīng)用,推動了該方向在國內(nèi)的發(fā)展。

如圖1所示,此時的鏈接預(yù)測研究范圍僅局限于簡單網(wǎng)絡(luò),即網(wǎng)絡(luò)中節(jié)點和邊均只有一種類型,且網(wǎng)絡(luò)結(jié)構(gòu)不隨時間變化,本文稱之為同質(zhì)信息網(wǎng)絡(luò)鏈接預(yù)測。根據(jù)是否需要訓(xùn)練模型,同質(zhì)信息網(wǎng)絡(luò)鏈接預(yù)測方法一般可分為3類。

1) 無監(jiān)督鏈接預(yù)測:僅通過計算用戶之間的相似度得分即可推斷出用戶間潛在的社交關(guān)系;

2) 有監(jiān)督鏈接預(yù)測:將存在的和不存在的鏈接分別視為正負(fù)實例,構(gòu)建分類/回歸模型來推斷潛在鏈接的標(biāo)簽/分?jǐn)?shù);

3) 半監(jiān)督鏈接預(yù)測:將存在的和不存在的鏈接分別視為正實例和未標(biāo)記實例,將鏈接預(yù)測問題進(jìn)一步轉(zhuǎn)化為PU(正實例和未標(biāo)記實例)學(xué)習(xí)問題。

圖1 社交鏈接預(yù)測圖示Fig.1 Graphical representation of social link prediction

近年來,社交網(wǎng)絡(luò)研究發(fā)展到了一個新的維度。為了獲得不同類型的社交網(wǎng)絡(luò)提供的服務(wù),用戶通常同時參與多個在線社交網(wǎng)絡(luò)。此外,網(wǎng)絡(luò)中包含多種節(jié)點與邊的類型,且網(wǎng)絡(luò)隨時間不斷演化?；诙嗑W(wǎng)絡(luò)、多類型節(jié)點與邊的鏈接預(yù)測,本文稱之為異質(zhì)信息網(wǎng)絡(luò)鏈接預(yù)測。異質(zhì)信息網(wǎng)絡(luò)的建模為研究人員提供了從全局視角研究用戶社交行為的機會,可以更加全面的了解用戶的社交活動模式,這對于社交網(wǎng)絡(luò)的鏈接預(yù)測任務(wù)有很大的幫助。

1 問題定義

給定一個社交網(wǎng)絡(luò)G=(V,E),其中V代表用戶,|V|=N個用戶的集合。E表示用戶間的邊,E=V×V是|E|=M條用戶關(guān)系的集合。eij∈E表示從用戶vi到用戶vj的一條有向關(guān)系。無向網(wǎng)絡(luò)中,eij=eji,在這種情況下,我們用eij或eji來表示用戶ei與ej之間的關(guān)系。本文將以無向圖為例進(jìn)行介紹相關(guān)定義,這些定義也可以很容易擴展到有向圖。

同質(zhì)信息網(wǎng)絡(luò)鏈接預(yù)測:

給定一個已知社交網(wǎng)絡(luò)G=(V,E)和預(yù)測函數(shù)Fun(),已知的社交關(guān)系集合E,未知的社交關(guān)系集合為B。設(shè)用戶數(shù)為|V|=N的網(wǎng)絡(luò)的全關(guān)系集合為U,且|U|=N·(N-1)/2,可知B=U-E。預(yù)測目標(biāo):fun∈B,表示網(wǎng)絡(luò)中節(jié)點vr與vt之間沒有鏈接。對于任意fun,由Fun(E,fun)輸出數(shù)值prb,該數(shù)值用以描述節(jié)點vr與vt間產(chǎn)生鏈接關(guān)系的可能性。同質(zhì)信息網(wǎng)絡(luò)鏈接預(yù)測僅涉及社交網(wǎng)絡(luò)G中同種節(jié)點及同種鏈接,預(yù)測未來一段時間內(nèi)的新鏈接。

異質(zhì)信息網(wǎng)絡(luò)鏈接預(yù)測:

設(shè)G=(V,E)是一個包含各種信息的網(wǎng)絡(luò),其中集合V=UiVi包含多種節(jié)點,Vi,i∈{1,2,…,|V|}是相同類型節(jié)點的集合。E=UiEi包含節(jié)點間多種類型的鏈接,其中Ei,i∈{1,2,…,|Ei|}是相同類型鏈接的集合。鏈接預(yù)測的任務(wù)是預(yù)測節(jié)點間是否存在鏈接。異質(zhì)信息網(wǎng)絡(luò)鏈接預(yù)測同時涉及多個社交網(wǎng)絡(luò)G1,G2,…,Gn,且不同類型的節(jié)點和鏈接。

2 異質(zhì)信息網(wǎng)絡(luò)鏈接預(yù)測

對于同質(zhì)信息網(wǎng)絡(luò)鏈接預(yù)測,呂琳媛和周濤等人將文獻(xiàn)[11]發(fā)表前國內(nèi)外學(xué)者關(guān)于鏈接預(yù)測的研究成果做了詳細(xì)的描述,限于篇幅,與該篇綜述相同的部分我們在這里不做介紹。

隨著社交網(wǎng)絡(luò)的快速發(fā)展,人們常常同時參與到越來越多不同類型的社交網(wǎng)絡(luò)中,享受不同的服務(wù)。這些在線社交網(wǎng)絡(luò)可以表示為包含豐富信息的異質(zhì)信息網(wǎng)絡(luò)。通常,異質(zhì)信息包括誰(who)、在哪里(where)、何時(when)和做什么(what)。

異質(zhì)信息網(wǎng)絡(luò)的出現(xiàn)促使了鏈接預(yù)測問題研究的新發(fā)展。根據(jù)鏈接預(yù)測問題的輸入及輸出的不同,異質(zhì)信息網(wǎng)絡(luò)的鏈接預(yù)測問題可歸結(jié)為交叉網(wǎng)絡(luò)鏈接預(yù)測、基于遷移的鏈接預(yù)測、異構(gòu)網(wǎng)絡(luò)鏈接預(yù)測、耦合網(wǎng)絡(luò)鏈接預(yù)測。

2.1 交叉網(wǎng)絡(luò)鏈接預(yù)測

交叉網(wǎng)絡(luò)鏈接預(yù)測的目的是預(yù)測源網(wǎng)絡(luò)和目標(biāo)網(wǎng)絡(luò)之間的跨域鏈接。利用源網(wǎng)絡(luò)和目標(biāo)網(wǎng)絡(luò)的共同點,預(yù)測節(jié)點在多個社交網(wǎng)絡(luò)之間的對應(yīng)關(guān)系。

Kong等[12]是第一個提出anchor link并應(yīng)用該種鏈接進(jìn)行交叉網(wǎng)絡(luò)鏈接預(yù)測的。在分析了Twitter和Foursquare數(shù)據(jù)后發(fā)現(xiàn),同一用戶在不同網(wǎng)絡(luò)上的多個賬戶間大多是相互隔離的,沒有任何連接。預(yù)測這些賬戶在多個社交網(wǎng)絡(luò)之間的對應(yīng)關(guān)系是許多網(wǎng)間應(yīng)用的重要先決條件,例如使用來自多個網(wǎng)絡(luò)的信息進(jìn)行鏈接預(yù)測和社區(qū)分析等。

圖2描述了基于異質(zhì)信息網(wǎng)絡(luò)進(jìn)行交叉網(wǎng)絡(luò)鏈接預(yù)測問題。每個用戶在2個網(wǎng)絡(luò)中分別擁有2個賬戶。在每個網(wǎng)絡(luò)中,用戶間通過社交鏈接相互聯(lián)系。此外,每個用戶還通過在線活動與一組位置、時間戳和文本內(nèi)容連接。值得注意的是,圖2中的前2個用戶還具有另一種類型的鏈接,連接2個網(wǎng)絡(luò)中相同用戶的賬戶。文獻(xiàn)將這些鏈接稱為anchor link(錨鏈接)。每個anchor link用于連接屬于同一用戶的一對賬戶。預(yù)測anchor link的任務(wù)是發(fā)現(xiàn)在現(xiàn)實世界中,哪對賬戶屬于同一用戶,即圖2中的?所示。但文中假設(shè)anchor link是2組用戶賬戶之間的一對一關(guān)系,并且預(yù)測前少數(shù)跨網(wǎng)絡(luò)的anchor link是已知的。

圖2 交叉網(wǎng)絡(luò)鏈接預(yù)測問題圖形表示Fig.2 Graphical representation of link prediction in cross networks

文獻(xiàn)設(shè)計了2階段方法來解決anchor link預(yù)測的主要挑戰(zhàn)。第1個階段用于處理異質(zhì)信息的特征提取,即利用每個網(wǎng)絡(luò)中的社交鏈接和跨2個網(wǎng)絡(luò)的已知anchor link提取社交特征訓(xùn)練SVM,用于鏈接預(yù)測;第2個階段負(fù)責(zé)解決一對一約束問題。由于SVM預(yù)測不滿足一一對應(yīng)的約束條件,文獻(xiàn)將SVM的實值得分作為第2階段的輸入,根據(jù)一一對應(yīng)的約束條件,共同推導(dǎo)出anchor link。

Tang等人[13]將交叉網(wǎng)絡(luò)鏈接預(yù)測研究著眼于跨領(lǐng)域協(xié)作推薦。研究數(shù)據(jù)表明,跨學(xué)科合作對社會已經(jīng)產(chǎn)生了巨大的影響。然而,研究人員往往很難建立這樣的跨領(lǐng)域合作。原因在于跨領(lǐng)域協(xié)作的模式、協(xié)作的形成機制、以及能否能預(yù)測該類型的協(xié)作均處于未知狀態(tài)。針對以上問題,該文獻(xiàn)定義并研究了跨領(lǐng)域協(xié)作推薦問題。文獻(xiàn)提出了3個模型對潛在的合作者進(jìn)行排名和推薦,并提出了一種跨領(lǐng)域的主題建模方法(CTL),CTL分別對源域和目標(biāo)域的主題分布以及域之間的相關(guān)性建模,用于學(xué)習(xí)和區(qū)分協(xié)作主題與其他主題。

跨領(lǐng)域協(xié)作推薦問題的輸入由源域GS和目標(biāo)域GT組成,每個域都與主題模型相關(guān)聯(lián)。值得注意的是,源域和目標(biāo)域可以重疊。

問題定義給定(1)源域GS和目標(biāo)域GT,(2)主題模型θ和θ′分別與2個域中的用戶關(guān)聯(lián),預(yù)測目標(biāo)是從源域GS為特定用戶vq對目標(biāo)域中的潛在合作者進(jìn)行排名和推薦。

圖3展示了一個CTL學(xué)習(xí)示例。在CTL學(xué)習(xí)之前,每個作者只在源域或目標(biāo)域中具有主題分布(來自其他域的主題的概率為零)。CTL平滑了跨2個域的主題分布。來自源域的用戶也有從目標(biāo)域提取的主題的概率,反之亦然。訓(xùn)練CTL模型之后,獲得了一組2個域之間的“協(xié)作主題”,即在合作文件中具有最高后驗概率的主題。例如,在圖3的右側(cè),框中顯示了這些協(xié)作主題。

圖3 CTL模型圖形表示Fig.3 Graphical representation of CTL model

2.2 基于遷移的鏈接預(yù)測

基于遷移的鏈接預(yù)測的重點是利用源網(wǎng)絡(luò)的監(jiān)督信息,提高目標(biāo)網(wǎng)絡(luò)的預(yù)測性能。該類型的鏈接預(yù)測主要為了解決真實社交網(wǎng)絡(luò)稀疏性問題,即目標(biāo)網(wǎng)絡(luò)中節(jié)點之間現(xiàn)有的鏈接只是網(wǎng)絡(luò)中所有潛在鏈接的很小一部分。

Dong等人[14]給出了遷移鏈接預(yù)測的形式化定義,并基于“人們在不同社交網(wǎng)絡(luò)具有相似交友原則”的社交理論,構(gòu)建出了3種跨異構(gòu)網(wǎng)絡(luò)的普遍社交模式。結(jié)合普遍社交模式,提出了一種基于遷移的排序因子圖模型(TRFG),并將其與網(wǎng)絡(luò)結(jié)構(gòu)信息相結(jié)合,有效地提高了預(yù)測性能。

問題定義給定源網(wǎng)絡(luò)GS和目標(biāo)網(wǎng)絡(luò)GT,其中GS中有大量已存在鏈接。目標(biāo)是學(xué)習(xí)預(yù)測函數(shù)f:(GT/GS)→YT,該函數(shù)利用源網(wǎng)絡(luò)中的鏈接信息推斷目標(biāo)網(wǎng)絡(luò)中的潛在鏈接,即用于生成通過利用源網(wǎng)絡(luò)中的信息在目標(biāo)網(wǎng)絡(luò)中創(chuàng)建鏈接的概率。

在目標(biāo)網(wǎng)絡(luò)中,節(jié)點vs與vi間是否存在鏈接的概率p(Y/G)=∏f(vs,vi,ysi)g(Xc.Yc),由屬性相關(guān)因子f(vs,vi,ysi)和社交相關(guān)因子g(Xc,Yc)決定。最終,根據(jù)p(Y/G)對候選列表進(jìn)行排序,并為給定的用戶推薦朋友。

圖4 TRFG模型圖形表示Fig.4 Graphical representation of TRFG model

圖中vs表示目標(biāo)網(wǎng)絡(luò)中欲與其他用戶創(chuàng)建鏈接的給定用戶。{v1,v2,v3,v4}為4個候選推薦用戶,v5和v6是vs的朋友。{ys1,…,y56}是為用戶對定義的潛在變量,每對用戶代表對應(yīng)的一對用戶是否會形成鏈接。

Zhang等[15]認(rèn)為預(yù)測社交網(wǎng)絡(luò)中新用戶的潛在鏈接比預(yù)測活躍用戶更能增加社交網(wǎng)絡(luò)的黏性。然而,在現(xiàn)實的社交網(wǎng)絡(luò)中,新用戶的信息分布可能與活躍用戶有較大差別。新用戶可能只有少量活動,甚至在網(wǎng)絡(luò)中沒有活動,即沒有社交鏈接或其他輔助信息。傳統(tǒng)的鏈接預(yù)測方法難于解決。文獻(xiàn)為新用戶從其他社交網(wǎng)絡(luò)傳輸額外的信息。

文獻(xiàn)注意到,一個社交網(wǎng)絡(luò)(如Foursquare)中的新用戶可能已經(jīng)加入另一個社交網(wǎng)絡(luò)(如Twitter)并活躍了很長時間。同一用戶在不同網(wǎng)絡(luò)中的賬戶稱之為anchor,不同社交網(wǎng)絡(luò)中同一用戶賬戶間的鏈接稱之為anchor link。通過anchor link,目標(biāo)網(wǎng)絡(luò)中的新用戶可以借助其在源網(wǎng)絡(luò)中豐富的鏈接信息和輔助信息提高新用戶在目標(biāo)網(wǎng)絡(luò)中的鏈接預(yù)測性能。

文獻(xiàn)研究了面向新用戶的鏈接預(yù)測問題,提出了一種基于監(jiān)督的SCAN-PS方法,利用多個比對異構(gòu)社交網(wǎng)絡(luò)中的信息解決鏈接預(yù)測問題。

圖5描述了SCAN-PS方法的工作原理。SCAN-PS方法可以使用目標(biāo)網(wǎng)絡(luò)和比對源網(wǎng)絡(luò)中存在的異構(gòu)信息,并且是由跨2個比對的社交網(wǎng)絡(luò)構(gòu)建的。利用anchor link,可以在比對的源網(wǎng)絡(luò)中精確定位用戶的對應(yīng)賬戶及其信息。如果同時使用2個比對網(wǎng)絡(luò),則從比對網(wǎng)絡(luò)中提取不同類別的特征。為了使用多個網(wǎng)絡(luò),這些提取的特征向量被合并到一個擴展的特征向量中。利用擴展后的特征向量和目標(biāo)網(wǎng)絡(luò)的標(biāo)簽,構(gòu)建跨網(wǎng)絡(luò)分類器,判斷目標(biāo)網(wǎng)絡(luò)中是否存在與這些新用戶相關(guān)的社交鏈接。

2.3 異構(gòu)網(wǎng)絡(luò)鏈接預(yù)測

異構(gòu)網(wǎng)絡(luò)鏈接預(yù)測的重點是給定源網(wǎng)絡(luò)和目標(biāo)網(wǎng)絡(luò)的部分多種類型鏈接,預(yù)測源網(wǎng)絡(luò)和目標(biāo)網(wǎng)絡(luò)中其余的單類型或多類型鏈接。

Yang等[16]提出了一種新的異構(gòu)網(wǎng)絡(luò)概率傳播方法——多關(guān)系影響傳播(MRIP)。MRIP適用于稀疏網(wǎng)絡(luò)中的鏈接預(yù)測,并可以捕獲不同類型鏈接之間的相關(guān)性,提高了預(yù)測的準(zhǔn)確性。根據(jù)作者在無監(jiān)督學(xué)習(xí)方面的工作,進(jìn)一步設(shè)計了基于拓?fù)浣Y(jié)構(gòu)和鏈路時間戳的異構(gòu)網(wǎng)絡(luò)中的無監(jiān)督模型MRIP和有監(jiān)督學(xué)習(xí)方法。有監(jiān)督學(xué)習(xí)方法將MRIP和時間作為特征,構(gòu)建了一個有效的異構(gòu)網(wǎng)絡(luò)鏈接預(yù)測模型。

問題定義給定異構(gòu)網(wǎng)絡(luò),可以將其建模為G=(V1∪V2∪…∪VM,E1∪E2∪…∪EN),其中Vx(x∈N)表示同一類型x的節(jié)點集,Ei(i∈M)表示類型為i的鏈接集。預(yù)測目標(biāo)是預(yù)測節(jié)點對u和v之間是否存在或?qū)⒋嬖趇類型的鏈接,其中u∈Vx,v∈Vy。

圖5 SCAN-PS方法圖形表示Fig.5 Graphical representation of SCAN-PS method

在無監(jiān)督鏈接預(yù)測中,預(yù)測目標(biāo)獲得數(shù)值s(u,v,i)∈[0,1],表示節(jié)點u和v之間存在鏈接的可能性,其中i是鏈接類型。而在有監(jiān)督學(xué)習(xí)中,預(yù)測目標(biāo)將獲得標(biāo)簽值(0,1),用于判定給定節(jié)點u和v之間是否會形成i類型的鏈接。

MRIP模型的構(gòu)建基于以下考慮:

1) 對于任何給定的鏈接類型i,影響不僅通過類型i的鏈接傳播,還通過其他類型的鏈接傳播。

2) 通過其他鏈接類型j傳播的概率取決于鏈接類型i和鏈接類型j之間的相關(guān)性。

MRIP采用廣度優(yōu)先的搜索過程來傳播概率。使用影響分值flow(v,u,i)作為對新鏈接可能性的估計:

其中,v和u代表節(jié)點,score(v)是源節(jié)點(廣度優(yōu)先搜索源節(jié)點)與節(jié)點v之間鏈接的概率,β=0.05是katz因子,σ(i,j)表示條件概率probability(i/j),即鏈接類型i和鏈接類型j的相關(guān)性。|E(v,u)|-1表示節(jié)點v和u之間除了類型i之外的鏈接類型數(shù)。

公式的前半部分是受鏈接類型i影響的程度,后半部分則是通過其他類型的鏈接傳播的影響,例如類型j。

Sun等[17]在關(guān)注了由多類型對象和關(guān)系組成的異構(gòu)網(wǎng)絡(luò)的鏈接預(yù)測問題的同時,注意到前期研究大多只關(guān)注某一鏈接是否會在未來出現(xiàn)的問題,而很少關(guān)注什么時間出現(xiàn)。因此,文獻(xiàn)研究了在異構(gòu)網(wǎng)絡(luò)中何時會發(fā)生某種關(guān)系的預(yù)測問題。

文獻(xiàn)首先將鏈接預(yù)測問題擴展到關(guān)系預(yù)測問題,使用基于元路徑的方法系統(tǒng)地定義了目標(biāo)關(guān)系和拓?fù)涮卣鳌Ｈ缓?利用提取的拓?fù)涮卣髦苯訉﹃P(guān)系構(gòu)建時間分布進(jìn)行建模。

問題定義異構(gòu)信息網(wǎng)絡(luò)是包含多種對象和鏈接類型的網(wǎng)絡(luò),定義為具有類型映射函數(shù)Φ:V→A和鏈接映射函數(shù)φ:E→R的有向圖G=(V,E)。每個對象v∈V屬于一個特定類型Φ(v)∈A,和每個鏈接e∈E屬于一個特定的鏈接類型或關(guān)系φ(e)∈R。給定A∈A和B∈A兩種類型之間的目標(biāo)關(guān)系〈A,B〉,時間間隔T0=[t0,t1),預(yù)測目標(biāo)是利用T0時段聚合網(wǎng)絡(luò)中提取的拓?fù)涮卣黝A(yù)測鏈接構(gòu)建時間t(t≥t1)。

系統(tǒng)地定義了異構(gòu)網(wǎng)絡(luò)中的拓?fù)涮卣骱?文獻(xiàn)提出了基于廣義線性模型GLM的預(yù)測模型,該模型直接將建立關(guān)系的時間作為拓?fù)涮卣鞯暮瘮?shù)進(jìn)行建模,并提供了在不同假設(shè)條件下學(xué)習(xí)每個拓?fù)涮卣鞯南禂?shù)的方法。在模型訓(xùn)練階段,首先為每個采樣對象對〈ai,bi〉收集時間間隔T0=[t0,t1)中拓?fù)涮卣鱴i,其中Φ(ai)=A,Φ(bi)=B。其次,如果ti在未來的訓(xùn)練間隔Ti=[t1,t2)內(nèi),記錄他們的第一次建立關(guān)系的時間yi=ti-t1;如果在T1時間間隔內(nèi)沒有觀察到新的關(guān)系,則記錄關(guān)系建立時間yi≥t2-t1。通過學(xué)習(xí)GLM模型,獲得與每個拓?fù)涮卣飨嚓P(guān)的最佳系數(shù),使關(guān)系構(gòu)建時間的當(dāng)前觀測值最大化。

2.4 耦合網(wǎng)絡(luò)鏈接預(yù)測

耦合網(wǎng)絡(luò)鏈接預(yù)測的重點是利用源網(wǎng)絡(luò)、交叉網(wǎng)絡(luò)、部分目標(biāo)網(wǎng)絡(luò)的鏈接信息,預(yù)測目標(biāo)網(wǎng)絡(luò)中的鏈接。Dong等人[18]提出了耦合網(wǎng)絡(luò)的概念,并基于此研究了耦合網(wǎng)絡(luò)鏈接預(yù)測問題。該問題利用源網(wǎng)絡(luò)的結(jié)構(gòu)信息和源網(wǎng)絡(luò)與目標(biāo)網(wǎng)絡(luò)間的相互作用來預(yù)測目標(biāo)網(wǎng)絡(luò)中的鏈接。由于目標(biāo)網(wǎng)絡(luò)的信息缺失,使得提取特征和訓(xùn)練實例變得困難。為了解決該問題,文獻(xiàn)提出了一個統(tǒng)一的框架CoupledLP。首先將信息從源網(wǎng)絡(luò)傳播到目標(biāo)網(wǎng)絡(luò),然后使用耦合因子圖模型CoupledFG將隱含的信息合并到目標(biāo)網(wǎng)絡(luò)中進(jìn)行鏈接預(yù)測。耦合因子圖模型既考慮了每個網(wǎng)絡(luò)的屬性特征,又考慮了2個網(wǎng)絡(luò)之間基于結(jié)構(gòu)元路徑的特征。

給定網(wǎng)絡(luò)G={V,E},其中V={vi}表示節(jié)點集合,E?V×V表示節(jié)點間邊的集合,且鏈接表示為eij=(vi,vj)∈E。源網(wǎng)絡(luò)GS=(VS,ES)和目標(biāo)網(wǎng)絡(luò)GT=(VT,ET),如果存在交叉鏈接eij=(vi,vj)使得節(jié)點vi∈VS且另一個節(jié)點vj∈VT,源網(wǎng)絡(luò)GS和目標(biāo)網(wǎng)絡(luò)GT構(gòu)成耦合網(wǎng)絡(luò)。耦合網(wǎng)絡(luò)中所有交叉鏈接eij的集合構(gòu)成交叉網(wǎng)絡(luò)GC=(VC,EC)。

問題定義耦合網(wǎng)絡(luò)G=(GS,GT,GC)中,給定源網(wǎng)絡(luò)GS和交叉網(wǎng)絡(luò)GC,預(yù)測目標(biāo)是學(xué)習(xí)一個預(yù)測函數(shù):f:(GS,GC)→YT。其中,YT表示目標(biāo)網(wǎng)絡(luò)GT中潛在鏈接e=(vi,vj)的標(biāo)簽ye的集合。若ye=1表示目標(biāo)網(wǎng)絡(luò)中節(jié)點vi與vj間存在鏈接,ye=0則表示目標(biāo)網(wǎng)絡(luò)中節(jié)點vi與vj間不存在鏈接。

由問題定義可知,文獻(xiàn)應(yīng)用源網(wǎng)絡(luò)的結(jié)構(gòu)信息和源網(wǎng)絡(luò)與目標(biāo)網(wǎng)絡(luò)的交互信息(交叉網(wǎng)絡(luò)),預(yù)測目標(biāo)網(wǎng)絡(luò)中缺失的鏈接。面臨的最大挑戰(zhàn)是沒有目標(biāo)網(wǎng)絡(luò)的任何信息,且源網(wǎng)絡(luò)與目標(biāo)網(wǎng)絡(luò)均為具有多種類型對象的異構(gòu)網(wǎng)絡(luò)。為了解決上述問題,文獻(xiàn)提出了兩階段框架CoupledLP解決耦合網(wǎng)絡(luò)的鏈接預(yù)測問題。

第1階段豐富目標(biāo)網(wǎng)絡(luò)結(jié)構(gòu)

基于3個啟發(fā)式規(guī)則(直接傳播、耦合傳播、共引傳播)推斷目標(biāo)網(wǎng)絡(luò)中最具潛力的鏈接。將推斷出的網(wǎng)絡(luò)命名為隱式目標(biāo)網(wǎng)絡(luò)GT′?；陔[式目標(biāo)網(wǎng)絡(luò),可以提取更豐富的結(jié)構(gòu)特征,否則目標(biāo)網(wǎng)絡(luò)將很難用于特征提取。

第2階段構(gòu)建耦合因子圖模型

基于隱式目標(biāo)網(wǎng)絡(luò),文獻(xiàn)構(gòu)建了耦合因子圖模型CoupledFG。該模型應(yīng)用基于源網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)特征、基于隱式目標(biāo)網(wǎng)絡(luò)的特征和基于耦合網(wǎng)絡(luò)的結(jié)構(gòu)元路徑特征進(jìn)行有監(jiān)督學(xué)習(xí),預(yù)測目標(biāo)網(wǎng)絡(luò)中的鏈接的標(biāo)簽集合YT。

耦合因子圖模型CoupledFG的目標(biāo)是在給定觀測特征和模型參數(shù)的情況下,最大化耦合網(wǎng)絡(luò)中鏈接的形成概率P(Y/X,G)。

3 總 結(jié)

近年來,鏈接預(yù)測研究已經(jīng)取得了快速的發(fā)展。基于社交網(wǎng)絡(luò)的鏈接預(yù)測的研究方法也隨著網(wǎng)絡(luò)數(shù)據(jù)的復(fù)雜化而不斷變化。社交鏈接預(yù)測任務(wù)不再相互獨立,而是表現(xiàn)出較強的相關(guān)性和相互影響,為進(jìn)一步學(xué)習(xí)異質(zhì)信息網(wǎng)絡(luò)中用戶之間的交互模式提供了前所未有的機遇。本文首先介紹了鏈接預(yù)測問題的形式化描述,然后將異質(zhì)信息網(wǎng)絡(luò)中鏈接預(yù)測進(jìn)行了分類,并結(jié)合國內(nèi)外相關(guān)的研究成果對異質(zhì)信息網(wǎng)絡(luò)鏈接預(yù)測學(xué)習(xí)方法、理論和模型進(jìn)行了詳細(xì)的闡述。