基于異質模體特征的社交網絡鏈路預測

方祺娜，許小可

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

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

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

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

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

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

1 問題描述及評價指標

1.1 問題描述

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

本文將不區分用戶類型的社交網絡構建為同質網絡，將用戶類型區分為男性用戶與女性用戶的社交網絡構建為異質網絡。如圖1 所示，同質網絡中的節點代表用戶，異質網絡中的淺色節點代表女性用戶，深色節點代表男性用戶。

圖1 同質網絡與異質網絡

1.2 評價指標

1) 評價指標AUC

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

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

2) 評價指標Precision

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

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

2 預測方法

2.1 基于相似性指標的預測方法

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

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

S=A2+αA3

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

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

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

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

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

5) L3 指標：

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

2.2 基于同質模體特征的預測方法

基于同質模體特征的鏈路預測方法主要是針對不考慮節點類型差異的同質網絡，根據網絡的拓撲結構，構建不區分節點類型的模體結構特征，將其定義為同質模體。由于本文數據為基于男女性別差異的異質網絡數據，不考慮網絡中的節點類型時，三節點模體和四節點模體結構只有表1 的5 種類型。

本文基于同質模體的預測方法共涉及5 個模體特征，分別為1 個三節點模體和4 個四節點模體，代表了網絡鏈接的5 種關系模式。所有模體編號、圖示和關系模式如表1 所示，其中虛線表示待預測連邊。

表1 同質模體對應的關系模式

2.3 基于異質模體特征的預測方法

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

表2 異質模體對應的關系模式

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

圖2 基于異質模體特征的關系預測

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

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

3 預測結果分析

3.1 實證數據說明

本文使用百度貼吧數據與性接觸數據，分別構建同質網絡與異質網絡進行鏈路預測，網絡具體信息如表3 所示。

表3 實證網絡信息說明

百度貼吧數據為百度貼吧戀愛吧用戶評論數據，在該網絡中，節點代表貼吧中的用戶，依據性別劃分為男性用戶和女性用戶，連邊代表一名用戶對另一名用戶的發帖進行了評論或回復。本文將百度戀愛吧男女之間的評論關系設定為具有線上社交關系，戀愛吧數據構建的網絡，只使用男性節點與女性節點的社交關系構成連邊。

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

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

3.2 基于模體特征鏈路預測

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

表4 基于同質模體特征的鏈路預測結果

表5 基于異質模體特征的鏈路預測結果

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

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

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

圖3 鏈路預測異質模體特征的相關性分析

3.3 同質模體特征與異質模體特征預測方法比較

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

圖4 同質模體和異質模體邊的分布

圖5 同質模體特征與異質模體特征結構差異

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

表6 融合多個異質模體特征的鏈路預測結果

通過表6 可以發現，在兩個實證網絡數據中，融合多個異質模體特征的AUC 和Precision 值均高于單個異質模體特征和同質模體特征。結果表明在相同的網絡拓撲結構下，融合所有區分節點異質信息的異質模體特征，其鏈路預測準確性高于單個異質模體特征以及不考慮節點異質信息的同質模體特征。這是由于異質模體考慮了網絡中節點的異質信息，更全面準確地刻畫了網絡結構。

3.4 融合同質模體和異質模體特征的鏈路預測

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

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

表7 5 類方法的鏈路預測結果

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

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

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

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

圖6 男女性別互換的鏈路預測結果

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

圖7 鏈路預測同質模體與異質模體特征的相關性分析

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

4 結 束 語

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

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