周明強，王瑩

（重慶大學(xué)計算機學(xué)院，重慶 400044）

0 引言

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

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

1 問題的相關(guān)研究

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

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

社交網(wǎng)絡(luò)中常常出現(xiàn)孤節(jié)點的情況，即出現(xiàn)用戶節(jié)點僅擁有初始的配置信息，提出了基于社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和輔助信息進行社交網(wǎng)絡(luò)鏈路預(yù)測的算法。通過對社交網(wǎng)絡(luò)的用戶配置信息進行用戶屬性建模，提出了基于MAG模型社交網(wǎng)絡(luò)用戶輔助信息來衡量用戶間產(chǎn)生鏈接的關(guān)系強度指標(biāo)，避免了采用單一指標(biāo)無法準(zhǔn)確度量用戶的孤立點問題，使基于社交網(wǎng)絡(luò)的用戶鏈路預(yù)測能夠達到更好的算法效果。

基于社交網(wǎng)絡(luò)和傳統(tǒng)網(wǎng)絡(luò)的區(qū)別，社交網(wǎng)絡(luò)預(yù)測問題定義如下：

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

2 基于屬性模型構(gòu)建的社交網(wǎng)絡(luò)的鏈路預(yù)測算法實現(xiàn)

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

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

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

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

問題表示如下：

圖1

基于屬性模型構(gòu)建的社交網(wǎng)絡(luò)的鏈路預(yù)測算法（簡寫為NFLP算法）下面給出具體的算法描述：

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

輸出：輸出預(yù)測的連接列表

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

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

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

步驟4按分?jǐn)?shù)值進行排序，取前K名的連接節(jié)點輸出到連接列表

3 實驗結(jié)果和分析

本實驗采用斯坦福大型網(wǎng)絡(luò)數(shù)據(jù)集合（http://snap.stanford.edu/data）上獲得的社交網(wǎng)絡(luò)數(shù)據(jù)集。為了獲得真實的節(jié)點屬性，我們使用與數(shù)據(jù)集中相同的協(xié)議。節(jié)點屬性來自用戶配置文件，如性別、職位、機構(gòu)等。使用數(shù)據(jù)集的基本拓?fù)淝闆r如表1所示，本實驗的硬件環(huán)境如表2所示：

表1 數(shù)據(jù)集的基本拓?fù)涮卣?/p>

表2 實驗硬件環(huán)境

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

表3 潛在屬性的分布情況

從實驗產(chǎn)生的親和性矩陣為如下：

表4

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

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

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

余弦接近性（Salton Cosine Similarity）Salton指標(biāo)，定義如下：

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

大度節(jié)點有利（Hub Promoted，HPI）指標(biāo)，常常用于生物領(lǐng)域的拓?fù)湎嗨瞥潭?。對比實驗結(jié)果如表，在給定的數(shù)據(jù)集中，提出的鏈路預(yù)測算法優(yōu)于其他方法。

表5 算法AUC對比圖

圖2

4 結(jié)語

如何利用屬性信息準(zhǔn)確地推斷網(wǎng)絡(luò)中的孤立用戶鏈路是鏈路預(yù)測中的一個難題。許多傳統(tǒng)的鏈路預(yù)測方法已經(jīng)被提出，并且對鏈路預(yù)測問題的解決方案確實起了很大的作用。由于無法找到孤立用戶的拓?fù)浣Y(jié)構(gòu)信息，大多數(shù)傳統(tǒng)方法不能很好地解決孤立節(jié)點的預(yù)測問題，但孤立節(jié)點往往是最有可能產(chǎn)生連接的節(jié)點?；贛AG模型對屬性值對節(jié)點對生成連接的可能性進行聯(lián)合，該算法可用于解決實際工作中的相關(guān)問題，具有一定的實際意義。并采用Facebook數(shù)據(jù)集進行試驗，證明算法可以達到比較好的結(jié)果。

[1]呂琳媛.復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測[J].電子科技大學(xué)學(xué)報,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.