方祺娜，許小可

(大連民族大學信息與通信工程學院 遼寧 大連 116600)

信息時代，越來越多的人傾向于通過網(wǎng)絡(luò)平臺進行交流溝通[1]?；ヂ?lián)網(wǎng)技術(shù)的快速發(fā)展使得社交網(wǎng)絡(luò)的研究得到廣泛關(guān)注[2]，如何對社交網(wǎng)絡(luò)中復(fù)雜而龐大的用戶關(guān)系進行預(yù)測和推薦是社交網(wǎng)絡(luò)領(lǐng)域的研究熱點，也是鏈路預(yù)測的重要應(yīng)用方向[3]。鏈路預(yù)測能夠揭示網(wǎng)絡(luò)中用戶之間的潛在關(guān)系[4]，挖掘社交用戶的興趣，為用戶推薦朋友等，在社交服務(wù)中具有廣泛應(yīng)用[5]。

鏈路預(yù)測是網(wǎng)絡(luò)挖掘中的一個基本問題[6]，也是復(fù)雜網(wǎng)絡(luò)的研究熱點。復(fù)雜網(wǎng)絡(luò)根據(jù)結(jié)構(gòu)可以分為同質(zhì)網(wǎng)絡(luò)和異質(zhì)網(wǎng)絡(luò)[7]。同質(zhì)網(wǎng)絡(luò)中的節(jié)點和連邊為同一種類型，異質(zhì)網(wǎng)絡(luò)中的節(jié)點或連邊為多種類型。目前大多數(shù)鏈路預(yù)測算法只考慮了網(wǎng)絡(luò)的結(jié)構(gòu)信息，沒有考慮節(jié)點的屬性[8]，已有社交網(wǎng)絡(luò)鏈路預(yù)測問題的研究主要針對同質(zhì)網(wǎng)絡(luò)，針對異質(zhì)網(wǎng)絡(luò)的鏈路預(yù)測研究相對較少[9]。文獻[10]提出基于異質(zhì)網(wǎng)絡(luò)表征學習的鏈路預(yù)測算法，通過元路徑的隨機游走實現(xiàn)網(wǎng)絡(luò)表征學習進行異質(zhì)網(wǎng)絡(luò)鏈路預(yù)測。文獻[11] 根據(jù)元路徑的質(zhì)量權(quán)重建立預(yù)測模型，構(gòu)建了一種基于元路徑的鏈路預(yù)測方法。文獻[12] 通過挖掘有效、可用的元路徑，提出基于圖核的異質(zhì)網(wǎng)絡(luò)鏈路預(yù)測方法。雖然上述針對異質(zhì)網(wǎng)絡(luò)的鏈路預(yù)測方法取得了較好性能，但是它們主要采用元路徑方法利用連邊異質(zhì)性進行鏈路預(yù)測，這類方法只考慮了網(wǎng)絡(luò)中部分關(guān)系模式，因此還需要針對精細刻畫多類型用戶之間復(fù)雜的網(wǎng)絡(luò)關(guān)系進行研究，如從網(wǎng)絡(luò)的節(jié)點異質(zhì)性角度挖掘拓撲結(jié)構(gòu)特征進行精準預(yù)測。

在傳統(tǒng)的同質(zhì)網(wǎng)絡(luò)鏈路預(yù)測研究中，最經(jīng)典的方法是基于節(jié)點局部結(jié)構(gòu)的相似性，如共同鄰居、Adamic-Adar、資源分配指標(resource allocation,RA)[13]等。上述指標都是基于網(wǎng)絡(luò)中的共同鄰居特征，計算復(fù)雜度較低、準確率較高。然而如在以性別差異作為節(jié)點類型劃分的異質(zhì)網(wǎng)絡(luò)中，由于只有異性節(jié)點之間有連邊，同性節(jié)點之間無連邊，網(wǎng)絡(luò)中沒有共同鄰居節(jié)點，因此此類方法無法采用。文獻[13] 在共同鄰居的基礎(chǔ)上考慮三階路徑的因素，提出了預(yù)測準確率更高的局部路徑(local path,LP)指標，Katz 指標在三階路徑的基礎(chǔ)上進一步考慮了網(wǎng)絡(luò)的所有路徑。文獻[14] 提出了基于節(jié)點之間連接偏好的偏好連接相似性指標(preferential attachment, PA)。文獻[15] 重點研究了二部圖網(wǎng)絡(luò)，提出了該類網(wǎng)絡(luò)的CAR 方法。與現(xiàn)有基于共同鄰居的方法相比，該方法不僅基于網(wǎng)絡(luò)中的公共節(jié)點以及共同鄰居節(jié)點，同時引入共同鄰居之間鏈接的組合。文獻[16]基于RA 指標研究了預(yù)測準確度更高的，針對三階路徑的L3 方法。以上5 種方法可以用于網(wǎng)絡(luò)中缺少共同鄰居節(jié)點的異質(zhì)網(wǎng)絡(luò)鏈路預(yù)測研究，作為進行比較的基準算法。

模體是指網(wǎng)絡(luò)中出現(xiàn)頻率較高的子圖結(jié)構(gòu)[17]，是一種重要的網(wǎng)絡(luò)拓撲結(jié)構(gòu)[18]。模體可用以研究拓撲結(jié)構(gòu)中節(jié)點之間的交互模式，有助于理解復(fù)雜網(wǎng)絡(luò)的局部結(jié)構(gòu)和功能，是研究鏈路預(yù)測問題的重要方法。文獻[19] 最早提出利用模體結(jié)構(gòu)進行有向網(wǎng)絡(luò)鏈路預(yù)測分析，雖然基于模體特征進行鏈路預(yù)測的研究日益增多，但大多是在同質(zhì)網(wǎng)絡(luò)中進行分析。如文獻[20] 使用模體來描述刻畫科學家合作的關(guān)系模式，并通過模體的組合對科學家合作網(wǎng)絡(luò)進行預(yù)測。如果不區(qū)分節(jié)點類型來刻畫網(wǎng)絡(luò)的結(jié)構(gòu)特征，就忽略了節(jié)點的類型差異，無法充分利用節(jié)點的異質(zhì)信息。

同質(zhì)網(wǎng)絡(luò)的鏈路預(yù)測研究往往不存在或者沒有考慮節(jié)點的異質(zhì)信息，存在一定的局限性。為了充分利用節(jié)點異質(zhì)信息進行鏈路預(yù)測，本文提出基于異質(zhì)模體特征的鏈路預(yù)測方法，將網(wǎng)絡(luò)中不區(qū)分節(jié)點性別類型的模體結(jié)構(gòu)定義為同質(zhì)模體，區(qū)分節(jié)點性別類型的模體結(jié)構(gòu)特征定義為異質(zhì)模體，比較兩種方法的預(yù)測性能差異和兩種模體之間的關(guān)聯(lián)性。為了結(jié)合不同模體特征的優(yōu)勢，本文還提出了融合同質(zhì)模體與異質(zhì)模體特征的鏈路預(yù)測算法。實驗結(jié)果表明，相較于同質(zhì)模體特征，基于異質(zhì)模體特征的鏈路預(yù)測方法可以有效提升鏈路預(yù)測準確性，而融合同質(zhì)和異質(zhì)模體可以取得更好的預(yù)測效果。

1 問題描述及評價指標

1.1 問題描述

本文使用的社交網(wǎng)絡(luò)為無向網(wǎng)絡(luò)，形式為G(V,E)，V、E分別是網(wǎng)絡(luò)中的節(jié)點集合、連邊集合。定義節(jié)點類型映射函數(shù)f:V→A，其中每個節(jié)點v∈V都對應(yīng)特定的類型f(v)∈A；定義鏈接類型映射函數(shù)γ:E→R，其中每條鏈接e∈E都對應(yīng)特定的類型γ(e)∈R。當R和A滿足|A|＞1或|R|＞1時，即邊的類型數(shù)或者節(jié)點的類型數(shù)大于1，則該網(wǎng)絡(luò)定義為異質(zhì)網(wǎng)絡(luò)，反之為同質(zhì)網(wǎng)絡(luò)。

本文將不區(qū)分用戶類型的社交網(wǎng)絡(luò)構(gòu)建為同質(zhì)網(wǎng)絡(luò)，將用戶類型區(qū)分為男性用戶與女性用戶的社交網(wǎng)絡(luò)構(gòu)建為異質(zhì)網(wǎng)絡(luò)。如圖1 所示，同質(zhì)網(wǎng)絡(luò)中的節(jié)點代表用戶，異質(zhì)網(wǎng)絡(luò)中的淺色節(jié)點代表女性用戶，深色節(jié)點代表男性用戶。

圖1 同質(zhì)網(wǎng)絡(luò)與異質(zhì)網(wǎng)絡(luò)

1.2 評價指標

1) 評價指標AUC

AUC 作為衡量鏈路預(yù)測算法性能的一種重要指標，可以從整體上衡量算法的精確度[21]。AUC指標可描述為如下形式：每次從測試集中隨機選取一條存在的邊，然后隨機選取一條不存在的邊，比較這兩條邊的相似度得分。如果存在邊的分數(shù)大于不存在邊的分數(shù)，就加1 分；如果兩條邊的分數(shù)相等，就加0.5 分。這樣獨立比較n次 ，如果有n′次存在邊的分數(shù)值大于不存在邊的分數(shù)值，有n′′次兩條邊的分數(shù)值是相等的，則AUC 值可以定義為：

通常，上述評分算法計算出的AUC 值應(yīng)該至少大于0.5。AUC 的值越高，算法的精確度越高，但AUC 的值最高不會超過1。

2) 評價指標Precision

Precision 作為衡量鏈路預(yù)測算法精確度的指標之一，主要從局部衡量預(yù)測的準確性。該指標關(guān)注的是預(yù)測值排序在前L個預(yù)測邊中預(yù)測準確的比例。根據(jù)特征的分數(shù)值從大到小排序，如果有m條邊是真實存在即預(yù)測準確的邊，Precision 可以定義為：

由該式可知，m越大則Precision 值越高，預(yù)測越準確。

2 預(yù)測方法

2.1 基于相似性指標的預(yù)測方法

利用節(jié)點間的局域結(jié)構(gòu)相似性是研究鏈路預(yù)測問題的一種重要方法，該方法的前提假設(shè)為節(jié)點間的相似性越大，它們之間存在鏈接的可能性就越大。在以往研究中，基于共同鄰居相似性指標應(yīng)用廣泛、預(yù)測精度較高，但本文研究的異質(zhì)社交網(wǎng)絡(luò)數(shù)據(jù)由于只有不同類型的節(jié)點存在連邊，故不存在共同鄰居節(jié)點，因此無法基于共同鄰居的相似性指標進行預(yù)測。本文主要使用局部路徑指標LP 與偏好連接相似性指標PA、Katz、CAR 和L3 作為鏈路預(yù)測的基準方法。LP 指標在考慮共同鄰居的基礎(chǔ)上考慮了三階路徑的因素，更全面考慮了節(jié)點的局域結(jié)構(gòu)信息，可以有效提升預(yù)測精度；Katz指標在三階路徑的基礎(chǔ)上進一步考慮了網(wǎng)絡(luò)的所有路徑；PA 指標在網(wǎng)絡(luò)存在“富者愈富”的連接偏好時性能顯著，針對稀疏網(wǎng)絡(luò)的預(yù)測性能也較好[22]；CAR 方法不僅考慮網(wǎng)絡(luò)中的公共節(jié)點以及共同鄰居節(jié)點，同時引入共同鄰居節(jié)點之間鏈接的組合；L3 方法基于RA 指標進一步提出三階路徑的預(yù)測方法，可以有效提升鏈路預(yù)測準確度。

1) 局部路徑指標(LP)：

S=A2+αA3

式中， α為可調(diào)參數(shù)；A表示網(wǎng)絡(luò)的鄰接矩陣，(A)nxy表示節(jié)點vx和vy之間長度為n的路徑數(shù)。當α=0時，LP 指標就等價于CN 指標。

2) 偏好連接相似性(PA)：

式中，kn表示節(jié)點vn的度，在網(wǎng)絡(luò)中一條新邊連接到節(jié)點vn的概率正比于該節(jié)點的度kn。在不考慮增長的網(wǎng)絡(luò)中，新鏈接連接節(jié)點vx和vy的概率正比于兩節(jié)點度kxky的乘積。

3) 全局路徑指標(Katz)：

式中，Γ(x)為節(jié)點x的鄰居節(jié)點集合；Γ(y)為節(jié)點y的鄰居節(jié)點集合；CN(x,y)為節(jié)點x和節(jié)點y的三階鄰居數(shù)量；z為節(jié)點x和節(jié)點y的三階鄰居集合；γ(z)是節(jié)點z的局部社區(qū)度。

5) L3 指標：

式中，ku為節(jié)點u的度；axu代表節(jié)點x和節(jié)點u之間的相互作用。如果節(jié)點x和u之間存在相互作用，則axu=1，否則axu=0。

2.2 基于同質(zhì)模體特征的預(yù)測方法

基于同質(zhì)模體特征的鏈路預(yù)測方法主要是針對不考慮節(jié)點類型差異的同質(zhì)網(wǎng)絡(luò)，根據(jù)網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，構(gòu)建不區(qū)分節(jié)點類型的模體結(jié)構(gòu)特征，將其定義為同質(zhì)模體。由于本文數(shù)據(jù)為基于男女性別差異的異質(zhì)網(wǎng)絡(luò)數(shù)據(jù)，不考慮網(wǎng)絡(luò)中的節(jié)點類型時，三節(jié)點模體和四節(jié)點模體結(jié)構(gòu)只有表1 的5 種類型。

本文基于同質(zhì)模體的預(yù)測方法共涉及5 個模體特征，分別為1 個三節(jié)點模體和4 個四節(jié)點模體，代表了網(wǎng)絡(luò)鏈接的5 種關(guān)系模式。所有模體編號、圖示和關(guān)系模式如表1 所示，其中虛線表示待預(yù)測連邊。

表1 同質(zhì)模體對應(yīng)的關(guān)系模式

2.3 基于異質(zhì)模體特征的預(yù)測方法

基于異質(zhì)模特特征的鏈路預(yù)測方法主要針對異質(zhì)網(wǎng)絡(luò)，即網(wǎng)絡(luò)中不只存在一種節(jié)點類型。根據(jù)異質(zhì)網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，構(gòu)建區(qū)分節(jié)點類型的模體結(jié)構(gòu)特征，將其定義為異質(zhì)模體。本文主要基于男女性別進行節(jié)點類型區(qū)分，將節(jié)點分為男性節(jié)點與女性節(jié)點兩種類型。在基于異質(zhì)模體特征的預(yù)測方法中，三節(jié)點模體和四節(jié)點模體共涉及8 種模體特征，分別為2 個三節(jié)點模體和6 個四節(jié)點模體，代表了社交網(wǎng)絡(luò)中的8 種關(guān)系模式。所有模體編號、圖示和關(guān)系模式如表2 所示，其中虛線表示待預(yù)測連邊。

表2 異質(zhì)模體對應(yīng)的關(guān)系模式

基于異質(zhì)模體特征的社交網(wǎng)絡(luò)關(guān)系預(yù)測主要提取訓練集的模體特征，將每種預(yù)測邊上的模體數(shù)量作為特征值，男性節(jié)點與女性節(jié)點之間是否有連邊作為機器學習的分類標簽，得到預(yù)測結(jié)果后使用AUC 和Precision 指標衡量預(yù)測性能。圖2 為基于異質(zhì)模體特征的社交網(wǎng)絡(luò)關(guān)系預(yù)測的具體過程。

圖2 基于異質(zhì)模體特征的關(guān)系預(yù)測

如圖2 所示，圖2a 為一個7 節(jié)點的小型異質(zhì)網(wǎng)絡(luò)。本文數(shù)據(jù)為區(qū)分男女性別的異質(zhì)網(wǎng)絡(luò)數(shù)據(jù)，且只有男性節(jié)點與女性節(jié)點存在連邊。圖2a 中節(jié)點u為 男性節(jié)點，節(jié)點v為女性節(jié)點，邊(u,v)為待預(yù)測連邊，圖2b 中以異質(zhì)模體特征Y1、Y3、Y7、Y8 為例說明社交網(wǎng)絡(luò)關(guān)系預(yù)測的主要過程，異質(zhì)模體特征Y1、Y3、Y7、Y8 的具體數(shù)量即為不同模體的特征值。模體特征Y1 的計算方法為尋找節(jié)點u的鄰居節(jié)點，且該鄰居節(jié)點不是節(jié)點v的鄰居。模體特征Y7 的計算方法為尋找節(jié)點u和v各自的鄰居節(jié)點，且該鄰居節(jié)點不互為鄰居。其他模體特征的計算方法以此類推，通過計算得出模體特征Y1 的個數(shù)為2，模體特征Y3 的個數(shù)為1，模體特征Y7 的個數(shù)為1，模體特征Y8 的個數(shù)為1。

在進行社交網(wǎng)絡(luò)用戶關(guān)系預(yù)測時，計算圖2c 中所涉及的4 種模體在圖2a 小網(wǎng)絡(luò)中的數(shù)量，并將得到的每種模體數(shù)量作為機器學習方法的輸入，從而得到連邊的相似度得分，繼而進行網(wǎng)絡(luò)的鏈路預(yù)測。

3 預(yù)測結(jié)果分析

3.1 實證數(shù)據(jù)說明

本文使用百度貼吧數(shù)據(jù)與性接觸數(shù)據(jù)，分別構(gòu)建同質(zhì)網(wǎng)絡(luò)與異質(zhì)網(wǎng)絡(luò)進行鏈路預(yù)測，網(wǎng)絡(luò)具體信息如表3 所示。

表3 實證網(wǎng)絡(luò)信息說明

百度貼吧數(shù)據(jù)為百度貼吧戀愛吧用戶評論數(shù)據(jù)，在該網(wǎng)絡(luò)中，節(jié)點代表貼吧中的用戶，依據(jù)性別劃分為男性用戶和女性用戶，連邊代表一名用戶對另一名用戶的發(fā)帖進行了評論或回復(fù)。本文將百度戀愛吧男女之間的評論關(guān)系設(shè)定為具有線上社交關(guān)系，戀愛吧數(shù)據(jù)構(gòu)建的網(wǎng)絡(luò)，只使用男性節(jié)點與女性節(jié)點的社交關(guān)系構(gòu)成連邊。

性接觸網(wǎng)絡(luò)全稱為基于性接觸的經(jīng)驗時空網(wǎng)絡(luò) (empirical spatiotemporal network of sexual contacts[23])，該網(wǎng)絡(luò)是一名男性用戶與另一名女性用戶進行性接觸的線上溝通網(wǎng)絡(luò)數(shù)據(jù)，節(jié)點代表性接觸網(wǎng)絡(luò)中的用戶個體，分為男性用戶與女性用戶，連邊代表一名男性用戶與一名女性用戶進行了線上的聯(lián)絡(luò)，即具有特殊社交關(guān)系。

在進行鏈路預(yù)測實驗時，對于每個實證網(wǎng)絡(luò)數(shù)據(jù)，從正樣本和負樣本中分別隨機選取90%的數(shù)據(jù)作為訓練集ET，選取剩余10%的正負樣本數(shù)據(jù)作為測試集Ev，滿足訓練集與測試集正負樣本比例1:1。

3.2 基于模體特征鏈路預(yù)測

本文對所有單個模體特征(5 個同質(zhì)模體和8個異質(zhì)模體)和多個模體特征(所有5 個同質(zhì)模體和所有8 個異質(zhì)模體)進行鏈路預(yù)測，得到評價指標AUC 與Precision 的值。鏈路預(yù)測的結(jié)果如表4和表5 所示，單個模體特征的最好預(yù)測性能和多模體特征的預(yù)測效果加粗標出。

表4 基于同質(zhì)模體特征的鏈路預(yù)測結(jié)果

表5 基于異質(zhì)模體特征的鏈路預(yù)測結(jié)果

由表4 可以發(fā)現(xiàn)，使用單個同質(zhì)模體特征進行鏈路預(yù)測時，模體特征T3 的預(yù)測準確率和精確度最高。說明在社交網(wǎng)絡(luò)中，如果兩位無關(guān)系用戶分別與兩位其他用戶具有社交關(guān)系，則其他兩位用戶有社交關(guān)系的可能性較大。本文綜合多個同質(zhì)模體特征進行預(yù)測，發(fā)現(xiàn)多同質(zhì)模體特征的預(yù)測效果比單個同質(zhì)模體特征的最好預(yù)測效果高4.3%～16.6%，說明綜合多種用戶關(guān)系模式進行鏈路預(yù)測效果更好。

由表5 可以發(fā)現(xiàn)，使用單個異質(zhì)模體特征進行鏈路預(yù)測時，模體特征Y7 的預(yù)測準確率與精確度最高，說明在社交網(wǎng)絡(luò)中，如果兩位有關(guān)系的男女分別與兩位無關(guān)系的男女有關(guān)系，則另外兩位男女有關(guān)系的可能性越大。在Y7 與T3 的網(wǎng)絡(luò)拓撲結(jié)構(gòu)一致的情況下，異質(zhì)模體特征的預(yù)測效果優(yōu)于同質(zhì)模體特征的預(yù)測效果。本文綜合多個異質(zhì)模體特征進行預(yù)測，發(fā)現(xiàn)多異質(zhì)模體特征的預(yù)測效果比單個異質(zhì)模體特征的最好預(yù)測效果高5.2%～12.8%，說明綜合多種男女用戶關(guān)系模式進行鏈路預(yù)測效果更好。

除了比較鏈路預(yù)測的具體性能，本文還對8 種異質(zhì)模體特征進行了皮爾遜相關(guān)性分析，結(jié)果如圖3 所示。模體特征Y1 和Y3 具有較強相關(guān)性，Y2 和Y4 也具有較強相關(guān)性，主要原因是Y3與Y4 都是Y1 與Y2 的拓撲組合。Y7 與Y8 也具有較強相關(guān)性，是因為這兩個模體特征只關(guān)注待預(yù)測連邊中兩個節(jié)點的各自鄰居節(jié)點之間的結(jié)構(gòu)。Y1、Y2、Y5、Y7、Y8 可以視為一個相關(guān)性程度較高的集合，它們之間有較強的相關(guān)性，是因為它們的拓撲結(jié)構(gòu)都是以Y1 的拓撲結(jié)構(gòu)為基礎(chǔ)。

圖3 鏈路預(yù)測異質(zhì)模體特征的相關(guān)性分析

3.3 同質(zhì)模體特征與異質(zhì)模體特征預(yù)測方法比較

為了比較同質(zhì)模體特征與異質(zhì)模體特征之間的差異，本文對兩種模體結(jié)構(gòu)存在邊和不存在邊的分布情況進行比較分析。百度貼吧數(shù)據(jù)中同質(zhì)模體T1 和異質(zhì)模體Y1 存在邊和不存在邊的分布差別如圖4 所示。其中實線和虛線分別代表網(wǎng)絡(luò)中的存在邊和不存在邊的模體數(shù)量分布。研究發(fā)現(xiàn)，對于同質(zhì)模體而言，存在邊和不存在邊有很大程度的重疊，重疊程度越大越不利于鏈路預(yù)測。對于異質(zhì)模體，存在邊和不存在邊的重疊分布小于同質(zhì)模體，說明相較于同質(zhì)模體，使用異質(zhì)模體進行鏈路預(yù)測的性能更好。本文采用基于同質(zhì)模體特征方法與異質(zhì)模體特征方法進行鏈路預(yù)測，在相同的網(wǎng)絡(luò)拓撲結(jié)構(gòu)下，同質(zhì)模體和異質(zhì)模體具有一定的相關(guān)性。圖5 分別為相同的網(wǎng)絡(luò)拓撲結(jié)構(gòu)下，同質(zhì)模體與異質(zhì)模體之間的關(guān)聯(lián)性。其中節(jié)點代表用戶個體，節(jié)點之間的連邊代表用戶之間的社交關(guān)系。深色節(jié)點代表用戶性別為男性，淺色節(jié)點代表用戶性別為女性。

圖4 同質(zhì)模體和異質(zhì)模體邊的分布

圖5 同質(zhì)模體特征與異質(zhì)模體特征結(jié)構(gòu)差異

由圖5 可知，Y1、Y2 和T1，Y3、Y4 和T2，Y5、Y6 和T4 分別具有相同的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，為了探究相同網(wǎng)絡(luò)拓撲結(jié)構(gòu)下，考慮節(jié)點異質(zhì)信息和不考慮節(jié)點異質(zhì)信息的模體的鏈路預(yù)測效果，進行了基于單個異質(zhì)模體特征、單個同質(zhì)模體特征、同一網(wǎng)絡(luò)拓撲結(jié)構(gòu)下多異質(zhì)模體特征的鏈路預(yù)測，結(jié)果如表6 所示。

表6 融合多個異質(zhì)模體特征的鏈路預(yù)測結(jié)果

通過表6 可以發(fā)現(xiàn)，在兩個實證網(wǎng)絡(luò)數(shù)據(jù)中，融合多個異質(zhì)模體特征的AUC 和Precision 值均高于單個異質(zhì)模體特征和同質(zhì)模體特征。結(jié)果表明在相同的網(wǎng)絡(luò)拓撲結(jié)構(gòu)下，融合所有區(qū)分節(jié)點異質(zhì)信息的異質(zhì)模體特征，其鏈路預(yù)測準確性高于單個異質(zhì)模體特征以及不考慮節(jié)點異質(zhì)信息的同質(zhì)模體特征。這是由于異質(zhì)模體考慮了網(wǎng)絡(luò)中節(jié)點的異質(zhì)信息，更全面準確地刻畫了網(wǎng)絡(luò)結(jié)構(gòu)。

3.4 融合同質(zhì)模體和異質(zhì)模體特征的鏈路預(yù)測

以往關(guān)于鏈路預(yù)測的研究中，研究人員提出的基于網(wǎng)絡(luò)結(jié)構(gòu)相似性的方法大多只關(guān)注其中一種網(wǎng)絡(luò)結(jié)構(gòu)，即一種模體結(jié)構(gòu)。在應(yīng)用于社交網(wǎng)絡(luò)的鏈路預(yù)測算法中，往往也只研究了一種社交用戶之間的關(guān)系模式，忽略了社交用戶之間多種關(guān)系模式的組合。因此本文通過特征拼接的方式融合多種同質(zhì)模體和異質(zhì)模體結(jié)構(gòu)進行鏈路預(yù)測，旨在結(jié)合不同模體特征的優(yōu)勢，分析多模體結(jié)構(gòu)即多關(guān)系模式對鏈路預(yù)測準確性的影響，并將多模體結(jié)構(gòu)的預(yù)測結(jié)果與單模體結(jié)構(gòu)的預(yù)測結(jié)果進行比較。

在鏈路預(yù)測問題中，將所有同質(zhì)模體特征與所有異質(zhì)模體特征進行融合，鏈路預(yù)測的結(jié)果如表7所示，發(fā)現(xiàn)融合多同質(zhì)模體和異質(zhì)模體特征的鏈路預(yù)測準確率高于只使用多異質(zhì)模體特征的鏈路預(yù)測準確率。說明相較于只使用多異質(zhì)模體進行鏈路預(yù)測，融合同質(zhì)模體特征對提升鏈路預(yù)測準確性具有一定的積極作用。本文還將所有同質(zhì)模體特征、所有異質(zhì)模體特征、融合所有異質(zhì)模體和同質(zhì)模體特征與LP、Katz、PA 和CAR 和L3 進行了對比，結(jié)果如表7 所示，其中最好的預(yù)測效果已加粗標出。

表7 5 類方法的鏈路預(yù)測結(jié)果

由表7 中數(shù)據(jù)可知，融合多異質(zhì)模體和同質(zhì)模體特征的鏈路預(yù)測算法準確率最高，其AUC 比LP、PA、Katz 方法最多提升了27.1%，精確度最多提高了20.1%，該方法也優(yōu)于CAR 和L3 方法的精確度。這是因為相比CAR 和L3 方法，本文提出的基于多同質(zhì)模體和多異質(zhì)模體的鏈路預(yù)測方法考慮了更多網(wǎng)絡(luò)結(jié)構(gòu)的非局域信息。因此，在社交網(wǎng)絡(luò)中融合多同質(zhì)和異質(zhì)模體特征進行鏈路預(yù)測能夠有效提高預(yù)測的準確性。

盡管CN、LP 等局部相似性指標可使用堅實的理論和實證依據(jù)進行解釋，如社會學中的同質(zhì)性原理，即兩個相似的節(jié)點更大概率產(chǎn)生連邊[16]。但最新研究發(fā)現(xiàn)，并不存在某一類局域指標可在所有實證網(wǎng)絡(luò)中都取得最佳預(yù)測性能，有些網(wǎng)絡(luò)是基于二階路徑的相似性指標表現(xiàn)更好，而另一些是三階路徑指標取得更好性能。本文以特殊的異質(zhì)社交網(wǎng)絡(luò)為研究對象，這類網(wǎng)絡(luò)的突出特點是局域性指標失效而只能依靠刻畫結(jié)構(gòu)非局域性的模體結(jié)構(gòu)進行鏈路預(yù)測，因此對于研究其他網(wǎng)絡(luò)的非局域性指標具有一定的借鑒作用，同時考慮到節(jié)點角色的異質(zhì)性也有利于將此類方法應(yīng)用于二部分圖中[24]。

由于本文數(shù)據(jù)為實證網(wǎng)絡(luò)數(shù)據(jù)，每位用戶可能存在造假的動機和現(xiàn)象。為了驗證當節(jié)點的男女信息存在噪音情況下算法結(jié)果的穩(wěn)定性，本文以百度貼吧數(shù)據(jù)為例，進行男女節(jié)點性別互換。隨機選取實證數(shù)據(jù)中30%、40%、50%、60%的男女節(jié)點進行性別互換，互換后的鏈路預(yù)測結(jié)果如圖6 所示。

由圖6 可知，雖然對實證數(shù)據(jù)中的男女性別進行了一定比例的置亂，但實驗結(jié)果表明依舊是多同質(zhì)模體與異質(zhì)模體的鏈路預(yù)測算法準確性最高，其次是多異質(zhì)模體，均高于同質(zhì)模體的準確性。該結(jié)果與上文的實驗結(jié)果一致，因此本文算法具有一定的通用性和穩(wěn)定性。

圖6 男女性別互換的鏈路預(yù)測結(jié)果

在融合所有同質(zhì)模體和異質(zhì)模體特征的鏈路預(yù)測中，本文還對8 種異質(zhì)模體和5 種同質(zhì)模體進行皮爾遜相關(guān)性分析，結(jié)果如圖7 所示。

圖7 鏈路預(yù)測同質(zhì)模體與異質(zhì)模體特征的相關(guān)性分析

由圖7 可看出，異質(zhì)模體Y1 和Y3，Y2 和Y4 具有較強相關(guān)性，原因是模體特征Y3 與Y4 分別是模體特征Y1 與Y2 拓撲結(jié)構(gòu)的組合。異質(zhì)模體特征Y7 和Y8 與同質(zhì)模體特征T3 和T5 具有較強相關(guān)性，原因是這4 種模體的網(wǎng)絡(luò)拓撲結(jié)構(gòu)較為接近，都是以四節(jié)點方形拓撲結(jié)構(gòu)為基礎(chǔ)進行模體的構(gòu)建。同質(zhì)模體T1、T2 和T4 相關(guān)性也較強，這是由于3 種模體結(jié)構(gòu)均為同質(zhì)模體且拓撲結(jié)構(gòu)都是以T1 的拓撲結(jié)構(gòu)為基礎(chǔ)。

4 結(jié) 束 語

本文研究性接觸網(wǎng)絡(luò)與百度貼吧戀愛吧兩種特殊類型網(wǎng)絡(luò)，為了更精準地刻畫網(wǎng)絡(luò)結(jié)構(gòu)以及充分利用節(jié)點的異質(zhì)信息，本文提出了基于異質(zhì)模體的鏈路預(yù)測方法，驗證了異質(zhì)模體數(shù)量與鏈路預(yù)測準確率的相關(guān)性，構(gòu)建異質(zhì)模體特征進行關(guān)系預(yù)測。在此基礎(chǔ)上，提出融合多種同質(zhì)和異質(zhì)模體特征進行社交網(wǎng)絡(luò)鏈路預(yù)測方法。結(jié)果表明，基于異質(zhì)模體的預(yù)測方法可以有效提升鏈路預(yù)測準確性，融合多異質(zhì)和同質(zhì)模體特征的預(yù)測效果更為顯著。本研究有助于對社交網(wǎng)絡(luò)的用戶關(guān)系進行預(yù)測和推薦，在用戶行為分析、推薦系統(tǒng)等方面具有廣闊的應(yīng)用前景。后續(xù)研究將在異質(zhì)模體特征的基礎(chǔ)上引入樸素貝葉斯算法與角色函數(shù)，對異質(zhì)網(wǎng)絡(luò)中的信息進行更加充分的利用。

周濤教授對本文研究工作給予了一些指導(dǎo)和幫助，在此表示感謝。