方祺娜，許小可

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

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

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

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

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

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

1 問題描述及評價(jià)指標(biāo)

1.1 問題描述

本文使用的社交網(wǎng)絡(luò)為無向網(wǎng)絡(luò)，形式為G(V,E)，V、E分別是網(wǎng)絡(luò)中的節(jié)點(diǎn)集合、連邊集合。定義節(jié)點(diǎn)類型映射函數(shù)f:V→A，其中每個(gè)節(jié)點(diǎn)v∈V都對應(yīng)特定的類型f(v)∈A；定義鏈接類型映射函數(shù)γ:E→R，其中每條鏈接e∈E都對應(yīng)特定的類型γ(e)∈R。當(dāng)R和A滿足|A|＞1或|R|＞1時(shí)，即邊的類型數(shù)或者節(jié)點(diǎn)的類型數(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é)點(diǎn)代表用戶，異質(zhì)網(wǎng)絡(luò)中的淺色節(jié)點(diǎn)代表女性用戶，深色節(jié)點(diǎn)代表男性用戶。

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

1.2 評價(jià)指標(biāo)

1) 評價(jià)指標(biāo)AUC

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

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

2) 評價(jià)指標(biāo)Precision

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

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

2 預(yù)測方法

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

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

1) 局部路徑指標(biāo)(LP)：

S=A2+αA3

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

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

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

3) 全局路徑指標(biāo)(Katz)：

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

5) L3 指標(biāo)：

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

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

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

本文基于同質(zhì)模體的預(yù)測方法共涉及5 個(gè)模體特征，分別為1 個(gè)三節(jié)點(diǎn)模體和4 個(gè)四節(jié)點(diǎn)模體，代表了網(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é)點(diǎn)類型。根據(jù)異質(zhì)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，構(gòu)建區(qū)分節(jié)點(diǎn)類型的模體結(jié)構(gòu)特征，將其定義為異質(zhì)模體。本文主要基于男女性別進(jìn)行節(jié)點(diǎn)類型區(qū)分，將節(jié)點(diǎn)分為男性節(jié)點(diǎn)與女性節(jié)點(diǎn)兩種類型。在基于異質(zhì)模體特征的預(yù)測方法中，三節(jié)點(diǎn)模體和四節(jié)點(diǎn)模體共涉及8 種模體特征，分別為2 個(gè)三節(jié)點(diǎn)模體和6 個(gè)四節(jié)點(diǎn)模體，代表了社交網(wǎng)絡(luò)中的8 種關(guān)系模式。所有模體編號、圖示和關(guān)系模式如表2 所示，其中虛線表示待預(yù)測連邊。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

通過表6 可以發(fā)現(xiàn)，在兩個(gè)實(shí)證網(wǎng)絡(luò)數(shù)據(jù)中，融合多個(gè)異質(zhì)模體特征的AUC 和Precision 值均高于單個(gè)異質(zhì)模體特征和同質(zhì)模體特征。結(jié)果表明在相同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下，融合所有區(qū)分節(jié)點(diǎn)異質(zhì)信息的異質(zhì)模體特征，其鏈路預(yù)測準(zhǔn)確性高于單個(gè)異質(zhì)模體特征以及不考慮節(jié)點(diǎn)異質(zhì)信息的同質(zhì)模體特征。這是由于異質(zhì)模體考慮了網(wǎng)絡(luò)中節(jié)點(diǎn)的異質(zhì)信息，更全面準(zhǔn)確地刻畫了網(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)進(jìn)行鏈路預(yù)測，旨在結(jié)合不同模體特征的優(yōu)勢，分析多模體結(jié)構(gòu)即多關(guān)系模式對鏈路預(yù)測準(zhǔn)確性的影響，并將多模體結(jié)構(gòu)的預(yù)測結(jié)果與單模體結(jié)構(gòu)的預(yù)測結(jié)果進(jìn)行比較。

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

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

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

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

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

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

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

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

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

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

4 結(jié) 束 語

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

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