基于屬性模型構建的社交網絡的鏈路預測

周明強，王瑩

（重慶大學計算機學院，重慶 400044）

0 引言

社交網絡是Web2.0的一種典型應用即社會性網絡服務（Social Networking Service，SNS），也是復雜網絡中的一個特例。鏈路預測是指如何通過已知的網絡結構等信息預測網絡中尚未產生連邊的兩個節點之間產生連接的可能性，它既包含了對未知鏈接的預測，也包含了對未來鏈接的預測。社交網絡鏈路預測，就是分析社交網絡的鏈路預測，它對信息檢索和電子商務中的推薦系統有著關鍵的作用，可以從最終的鏈接關系著手幫助使用者找到新的推薦用戶和潛在用戶，在網上購物提供合理和貼切的推薦。

如何在社交網絡中準確進行鏈路預測，就要考慮到社交網絡本身的特點，社交網絡的鏈接在多大程度上可以使用網絡本身固有的特性來建模，問題是網絡和節點如何相互關聯。真實的社交網絡通常具有豐富的結構特征，如同質性、異質性和核心-外圍性等。如果能夠找到網絡結構和輔助信息之間的聯系，則可以在一定程度上恢復缺失的鏈路信息。從技術角度來看,如何構建一種以原則性方式將節點（用戶配置文件信息）、邊（交互）的功能與網絡結構組合在一起的方法是核心問題。

1 問題的相關研究

在傳統的鏈路預測問題中，對于無向網絡G(V,E)，其中V={v1,v2,…vN}是節點集合，E={e1,e2,…eN}是邊的集合，N與M分別是節點數和邊數。一個圖的鄰接矩陣記為A，無向網絡中節點x和節點y對應的連接情況記為axy，當且僅當節點vx與vy之間有連邊時axy=1，否則 axy=0，如下所示：

計算節點對之間的相似度是鏈路預測的直觀解決方案。它是基于簡單的想法：越是相似的一對，他們之間聯系的可能性越大，反之亦然。通過相似性測量，其中每個非連接節點對（x，y）的評分分值高表示X和Y之間的相似性，同時預示著X和Y在未來會聯系在一起的概率很高，而低分也表示x和y不連接的概率高。

社交網絡中常常出現孤節點的情況，即出現用戶節點僅擁有初始的配置信息，提出了基于社交網絡拓撲結構和輔助信息進行社交網絡鏈路預測的算法。通過對社交網絡的用戶配置信息進行用戶屬性建模，提出了基于MAG模型社交網絡用戶輔助信息來衡量用戶間產生鏈接的關系強度指標，避免了采用單一指標無法準確度量用戶的孤立點問題，使基于社交網絡的用戶鏈路預測能夠達到更好的算法效果。

基于社交網絡和傳統網絡的區別，社交網絡預測問題定義如下：

定義1社交網絡圖：給出一個社交網絡圖G（V1,V2,E,NF1，NF2），其中節點 v∈G·N，e∈V1·V1。NF1為V1的節點屬性，NF2為V2的節點屬性。

2 基于屬性模型構建的社交網絡的鏈路預測算法實現

針對屬性模型構建的社交網絡，這里使用MAG模型對這個網絡進行建模，從而推斷網絡的生成。這里為了對選取的節點屬性進行選擇，將網絡中的節點建模為一個潛在特征向量，并且對每對節點之間的連接可能性進行建模。這里我們使用一種乘法屬性模型，這種模型可以根據節點的屬性進行建模。

在公式（1）中，Axy為鄰接矩陣，Ml為親和力矩陣，NFxl、NFyl為節點x，y的屬性向量。所以需要根據屬性估計親和力矩陣Ml，如圖為根據xy的各自的屬性向量來模擬xy間連接的可能性，通過親和力矩陣量化屬性對取值對連接的強度的影響以此來考量xy連接的可能性。

將用戶屬性按二元的方式用向量進行表示，將數據用鄰接矩陣的方式表示。由定義1可知我們將節點集劃分為兩個部分孤立節點部分，連接節點部分。如圖1中，當x的屬性向量為（0,1,1，…,1）,y的屬性為（1,1,1，…,0）,根據屬性對值（0,1），（1,1），（11），（1,0）在指定的屬性的親和力矩陣中找到強度值，用強度值得乘積來量化xy連接的可能性。

同時使用最大似然估計的方法對親和力矩陣進行估計M，簡單地考慮每個屬性只有2個取值，若所有屬性都是獨立存在的，則滿足伯努利分布,使用u來表示NF的分布情況，利用最常用的優化方法變分期望最大化（EM）方法來解決網絡表示學習問題。

問題表示如下：

圖1

基于屬性模型構建的社交網絡的鏈路預測算法（簡寫為NFLP算法）下面給出具體的算法描述：

輸入：輸入節點屬性列表，G的鄰接矩陣A

輸出：輸出預測的連接列表

步驟1從節點屬性列表按照定義生成屬性向量形成矩陣NF1，NF2

步驟2根據矩陣NF1，A估計親和力矩陣M

步驟3根據親和力矩陣M和矩陣NF2估計預測的連接列表

步驟4按分數值進行排序，取前K名的連接節點輸出到連接列表

3 實驗結果和分析

本實驗采用斯坦福大型網絡數據集合（http://snap.stanford.edu/data）上獲得的社交網絡數據集。為了獲得真實的節點屬性，我們使用與數據集中相同的協議。節點屬性來自用戶配置文件，如性別、職位、機構等。使用數據集的基本拓撲情況如表1所示，本實驗的硬件環境如表2所示：

表1 數據集的基本拓撲特征

表2 實驗硬件環境

經過實驗，將屬性映射到9個潛在屬性得到的分布情況如下：

表3 潛在屬性的分布情況

從實驗產生的親和性矩陣為如下：

表4

由于社交網絡的稀疏性，鏈路預測問題在本質上是非常困難的二元預測問題。其中，實際上只有很小一部分的鏈接存在，如現有連接鏈路占所有可能連接鏈路的百分比非常小。與許多現有的鏈路預測實驗類似，這里使用最常用的指標AUC（受試者工作特征下的面積）來測量算法的精確值，AUC值可以被解釋為隨機選擇的不可觀測鏈路比隨機選擇的不存在鏈路具更高的分數的概率，預測算法越準確。計算方法如下所示：

為了和該算法形成對比，這里使用傳統的鏈路預測方法進行對比實驗：

公共鄰居（Common Neighbors）CN指標：若節點x的鄰居集合為Γ（x）,節點 x的鄰居集合為Γ（y）,若兩者之間存在交集的節點越多，則節點x和節點y更相似。CN定義如下：

余弦接近性（Salton Cosine Similarity）Salton指標，定義如下：

Jaccard指標：一種計算個體間相似性的相似性指標。Jaccard指標的基本思想是，當節點對的共同鄰居數越多，則說明它們有更大的相似性，則Sxy就越高。同時，當節點對的兩個節點的度越低時，則說明它們的共同鄰居所占的比重就越大，在社交網絡當中，就說明了兩個用戶具有更大的共同交際范圍，此時他們也就更有可能成為新的好友，即形成新的連接。

大度節點有利（Hub Promoted，HPI）指標，常常用于生物領域的拓撲相似程度。對比實驗結果如表，在給定的數據集中，提出的鏈路預測算法優于其他方法。

表5 算法AUC對比圖

圖2

4 結語

如何利用屬性信息準確地推斷網絡中的孤立用戶鏈路是鏈路預測中的一個難題。許多傳統的鏈路預測方法已經被提出，并且對鏈路預測問題的解決方案確實起了很大的作用。由于無法找到孤立用戶的拓撲結構信息，大多數傳統方法不能很好地解決孤立節點的預測問題，但孤立節點往往是最有可能產生連接的節點。基于MAG模型對屬性值對節點對生成連接的可能性進行聯合，該算法可用于解決實際工作中的相關問題，具有一定的實際意義。并采用Facebook數據集進行試驗，證明算法可以達到比較好的結果。

[1]呂琳媛.復雜網絡鏈路預測[J].電子科技大學學報,2010,39（5）:651-661.

[2]Bhattacharyya P,Garg A,Wu S F..Analysis of User Keyword Similarity in Online Social Networks[J].Social Network Analysis and Mining,2011,1（3）:143-158..

[3]黃嘉烜,金小剛.Continuous Multiplicative Attribute Graph Model[J].Journal of Shanghai Jiaotong University（Science）,2017,（01）:87-91.

[4]Akcora C G,Carminati B,Ferrari E.User Similarities on Social Networks[J].Social Network Analysis and Mining,2013,3（3）:475-495.

[4]J.McAuley and J.Leskovec.Learning to Discover Social Circles in Ego Networks.NIPS,2012.

[5]J.McAuley and J.Leskovec.Learning to Discover Social Circles in Ego Networks.NIPS,2012.

[6]Anderson A,Huttenlocher D,Kleinberg J,et al.Effects of User Similarity in Social Media[C].Proceedings of the fifth ACM International Conference on Web Search and Data Mining,2012:703-712.