結合用戶互動加權圖的社交網絡鏈接預測

白 楊,鄧貴仕

1(遼東學院 信息工程學院,遼寧 丹東 118003)2(大連理工大學 系統工程研究所,遼寧 大連 116024)

1 引 言

隨著WEB2.0以及社交媒體的迅速發展,Facebook、Twitter、微博、人人網、微信等社交網絡已經成為人們日常生活中進行溝通、交流等活動必不可少的在線平臺.社交網絡是現實世界社交活動的反映[1],因此,在社交網絡中,人與人之間的交互行為形成了復雜的用戶關系,這種關系本質上并不僅僅是由直接交互的兩個用戶之間生成,比如復雜網絡研究中的FOAF[2]、“蝴蝶效應”[3]等原理,皆表明雖然表面上沒有聯系的兩個用戶,實際上有可能存在千絲萬縷的關系.例如在微博中,用戶通過“評論”、“轉發”等互動行為構成用戶互動關系,而這些互動關系表現出的主觀性和實時性,往往更能體現用戶之間真實的關系強弱,同時,也使社交網絡呈現出多樣性和加權性.對社交網絡的用戶關系進行分析,能推動網絡演化的理論研究,也對個性化推薦、社群劃分、社區發現等應用性研究具有重要意義.

社交網絡的用戶關系構成一種社會網絡結構,鏈接預測方法是分析社會網絡結構的有力輔助工具[4],可用于發現人和人之間的潛在關系.鏈接預測指通過已知的網絡結構信息預測網絡中尚未產生連接邊的兩個節點間產生鏈接的可能性[5],其分析過程通常以圖論為基礎.比如,用三元組G=(V,E,W)表示一個用戶關系網絡,如圖1所示.其中V={x,y,a,b,c,d,e}表示用戶的節點集,E表示節點之間的邊集,W表示節點之間邊上的權值集合,以用戶節點之間的關系相似度表示.例如節點x與e之間的邊的權值為相似度sxe,圖1中省略了其他用戶節點之間的相似度.用戶x和e之間以及用戶e和y之間存在直接相連的邊,而用戶x和y之間不存在直接相連的邊,即二者的關系的相似性計算無法獲得直接相似度.但是,通過觀察可知節點x和y之間存在很多公共節點,因此可以推測兩者之間存在一定的關聯.這里可以將預測x和y之間相似性的問題轉換為網絡節點鏈接預測問題,即通過已有的關系預測在x和y之間是否存在一條隱含的邊以及這條邊的權值是多少,然后根據權值判斷是否將y納入向x進行推薦的基礎信息中,即實現基于相似性的鏈接預測.

現有的鏈接預測研究主要集中在無權網絡上,只反映了網絡的拓撲結構和節點連接方式,不能全面客觀反映某些真實網絡的情況,針對加權網絡的鏈接預測適用范圍有限、預測結果不夠準確.并且,大多數鏈接預測算法僅單方面考慮了圖的局部或全局特性,在預測準確率和計算復雜度上難以均衡.

圖1 用戶關系網絡示意圖Fig.1 Diagram of user relationship networks

本文在對已有方法進行分析和總結的基礎上,在考慮用戶間接結構的基礎上,針對用戶互動行為分析,提出一種新的鏈接預測算法PWRALP,實現基于局部圖的綜合節點及路徑的加權網絡鏈接預測.

2 相關工作

主流的鏈接預測算法思想是通過節點的固有屬性定義節點的相似性,即兩個節點具有較多的共同特征,則兩者的相似度較高.其中,局部圖相似度算法以思路簡單、較易實現、計算復雜度較低、預測結果較好等優勢被廣泛采用,Liben-Nowell和Kleinberg[6]給出了9種相似性指數,Zhou[7]提出了RA和LP兩種局部圖相似性預測效果更好的指數.白萌[8]通過實證分析得出節點及路徑相結合的RALP指標的優越性,本文將從理論分析視角探討此種方法的合理性.

2.1 無權網絡的鏈接預測方法

資源分配指標RA的計算思想是考慮網絡中沒有直接相連的兩個節點x和y,以它們的共同鄰居作為媒介進行資源傳遞,將x的一些資源傳遞到y.假設網絡中每個節點都有1個單位的資源,將其平均分配給它的鄰居節點,則兩個節點的網絡結構相似度可以用節點接受到的資源數來定義.具體做法是首先計算節點x和y的共同鄰居節點集合中的每一個節點的度數,然后計算這些度數的倒數之和,式(1)表示x與y之間的相似度預測方法.

(1)

其中,z是x與y的共同鄰居,s(z)表示節點z的度,Γ(x)和Γ(y)分別表示節點x和y的鄰居節點集合.

然而,圖2(I)、圖2(II)子圖的節點b雖然是預測節點x和y的共同鄰居節點d的鄰居,但區別在于圖2(I)中b是y的鄰居,圖2(II)中b不是y的鄰居.而在RA算法中并沒有考慮類似b這樣的節點對鏈接預測的作用.結合現實世界中的朋友關系情況進行分析,假設我們不知道兩個人x和y是否是好友,x和y的共同好友的朋友是x或y的單方好友,如果這種類型的好友越多,那么x和y成為好友的可能性越大.即圖2(I)比子圖2(II)的預測結果大.而從節點之間的路徑方面考慮也驗證了上述說法的正確性:通過節點d為媒介,圖2(I)比圖2(II)多一個可達路徑x→d→b→y,這將對x和y的關系有加強作用.但是,經典的基于節點局部相似性的鏈接預測指標[7](如CN,AA,RA)都沒有考慮預測節點這種“單方鄰居”的作用.

圖2 節點x和y及共同鄰居網絡Fig.2 Networks including x,y and their co-neighbors

另外,RA指標利用預測節點的共同鄰居節點的度信息,卻忽略了預測節點的鄰居節點間的聯系,考慮到這個問題,周濤等人[9]提出了局部路徑LP指標,并根據實驗結果將局部圖界定在三階路徑范圍內,如式(2):

(2)

其中i,j是預測節點x和y間路徑上的節點,(A2)ij表示x和y間長度為2的路徑數目,(A3)ij表示x和y間長度為3的路徑數目,α是可調參數.LP指標算法考慮了預測節點對的部分路徑對相似性預測的貢獻,在一定程度上提高了預測精度,但卻忽略了路徑上傳輸節點的局部相似度對預測結果的影響.

對提出的“單方鄰居”問題,本文認為在考慮預測節點的鄰居時,不僅要考慮共同鄰居的資源分配,也要考慮單方鄰居的媒介作用.鑒于節點指標RA與路徑指標LP的優勢和不足,將兩個指標算法結合起來,以路徑數目規避單方鄰居這個問題.白萌[8]通過實測數據集實驗對比,發現RA與LP結合起來的RALP指標獲得了較好的預測結果,如式(3).

(3)

其中,lx→y是從節x到y的長度為3的路徑,i和j是路徑lx→y的中間節點,ε為可調參數.

2.2 加權網絡的鏈接預測方法

鏈接預測研究方法大部分都是針對無權網絡,只有很少一部分延展到加權網絡上.Lv[10]在RA基礎上提出了加權的WRA鏈接預測方法如式(4):

(4)

其中,wxz表示節點x和z之間邊的權值,s(z)為節點z的強度,其取值在α=0時,表示圖為無權圖,且s(z)是z的度;在α=1時,表示圖為簡單的加權圖,預測結果往往不及無權圖.因此,若采用式(4)作為加權圖的預測方法,則需要根據不同的數據集進行實測找出合適的α值.

白萌[8]在提出的RALP上引入權重值,給出WRALP指標,如式(5):

(5)

分析已有的加權網絡鏈接預測方法,可知WRA和WRALP均采用預測節點與其共同鄰居的邊權求和方式,這里只要任一預測節點與其共同鄰居的邊權和較大,則其共同鄰居對鏈接預測結果的貢獻程度也較大.與實際社會網絡對應,可以理解為只要兩個用戶中任何一位與其共同鄰居互動頻繁,則認為這兩個用戶相識的可能性較大,這與真實社會網絡并不相符.同時,確定WRA的最優α參數值也是一個難題,需要根據數據集進行實測,這往往需要耗費大量的運算時間.

Zhao[11]提出了基于可信路徑權重相似性的加權網絡鏈接預測方法rWRA,在多數數據集上取得了最高的相似度預測準確度,如式(6):

(6)

3 鏈接預測方法

3.1 相關定義

為描述用戶節點間相似性算法,首先給出相關形式化定義和說明:設加權社會網絡圖G=(V,E,W),節點集V、邊集E、邊的權重集合W,若x,y∈V,wxy為x和y連接邊的權重.特殊地,對于無權網絡,wxy默認為1.

定義1.節點強度

設G=(V,E,W),x,y∈V,Γ(x)∈V為x的鄰居節點.定義節點x的強度為式(7):

s(x)=∑y∈Γ(x)wxy

(7)

定義2.邊權強度

設G=(V,E,W),x,y∈V,定義節點x和y的邊權強度[12]為式(8):

(8)

swxy表示節點x和y連接邊的權重在它們所有鄰居節點連接邊權重之和中所占的比例.式(8)引用了式(7)中關于節點強度的定義,s(x)等于與x相連的所有邊的權重之和.特殊地,對于無權網絡,節點強度是節點的度.

3.2 一種加權圖鏈接預測算法PWRALP

借鑒Zhao[11]的可信任網絡的權值計算方法,以用戶與共同鄰居邊權乘積作為該共同鄰居的貢獻值,繼而擴展到局部路徑相似度的三階路徑的邊權強度積,提出基于邊權乘積的PWRALP(Product-weighted RALP)指標,如式(9):

ε∑(i,j)∈lx→yswxi·swij·swjy

(9)

3.3 基于PWRALP的用戶相似度模型

通過互動行為強度構成了的邊權,形成加權的用戶關系網絡.社交網絡最主要的特點是用戶之間存在的社會關系,如在網絡應用平臺上以諸如“關注、粉絲、圈子”等應用形式表示用戶之間的好友關系.由于平臺提供了良好的媒體中介功能,好友之間的互動性更會以“點贊”、“評論”、“轉發”和“分享”等互動行為有所加強進而有利于加強用戶之間的緊密性.互動形成的某種群體規范使不同的人具有了某種共同身份,這就形成了有實際意義的網絡群體[13].因此,用戶之間的互動特征是研究用戶關系挖掘的有效信息.

社交網絡的用戶互動關系分為弱關聯互動關系和強關聯互動關系[14].弱關聯操作指用戶之間隱含的互動關系,如經常關注同一個頁面,或共同使用同一個網站應用等;強關聯操作指的是用戶之間較為直接的互動關系,如轉發、點贊等行為.轉發行為表達了用戶對轉發內容的認可,用戶意圖的表達更為明確,因此本文以用戶之間的轉發行為來衡量用戶之間的相關程度,具體如式(10)所示:

(10)

其中,σxy表示用戶x對用戶y的相似度,υxy表示x對y的評論次數.一般而言,x對y的相似度與y對x的相似度不相同,因此,設定x和y的互動相似度Gi_Sim(Gragh-inter-Sim)如式(11):

(11)

用戶相似性預測算法的主要目的是在數據比較稀疏的情況下,預測兩個表面上沒有相似性鏈接的用戶之間的相似性,使這兩個用戶之間產生相似性鏈接,豐富數據集以便解決數據稀疏性帶來的問題.社交網絡具有同質性,網絡中用戶之間的鏈接數目越多(節點強度越大),用戶的互動行為越頻繁(邊權強度越大),用戶間存在鏈接的概率越大[15],這也是用戶相似性預測要解決的問題.

4 實 驗

4.1 實驗數據

通過網絡爬蟲技術從新浪微博上采集從2013年5月到2013年9月的微博信息,用戶數總量為150728個.對數據集相關的信息做以統計,相關數據信息包括微博文本內容及發布時間、戶關注列表、用戶轉發互動信息.對用戶互動關系信息進行分析,制作用戶轉發微博的統計圖,如圖3和圖4所示.

圖3中只有少數微博擁有大量的轉發用戶,而97%的微博數對應的轉發的用戶數小于20個,說明轉發互動數據稀疏.圖4中用戶的微博轉發數分布服從長尾分布,用戶平均轉發數少于20次的用戶占總用戶數的67%,需要過濾掉這些用戶.對數據集繼續進行清洗,獲得的實驗數據的統計信息如表1所示.

4.2 加權網絡鏈接預測實驗

根據式(11)計算用戶互動相似度(實驗中以轉發互動關系為代表),構建用戶互動關系網絡,根據式(9)進行基于互動關系的加權圖的鏈接預測.

圖4 每個用戶的轉發微博數分布Fig.4 Distribution of the number of forwarding micro-blog per user

4.2.1 評價指標

本文使用AUC指標和Precision指標來衡量算法的預測準確度.AUC是在測試集中邊的分數值比隨機選擇的一個不存在的邊的分數值高的概率,具體做法是:進行n次獨立比較,每次從測試集中隨機選取一條邊,與隨機選取的不存在的邊進行比較,如果測試集中邊的分數值大于不存在的邊的分數值,則加一分,累計次數為n′;如果兩個分數值相等,則加0.5分,累計次數為n",則AUC定義為:AUC=(n′+0.5n″)/n.由此可知,如果所有分數都是隨機產生的,AUC=0.5.因此,AUC>0.5度量了算法比隨機選擇的準確程度.Precision指標是指在前L個預測鏈接中,準確預測所占的比例,即Precision=m/L,表示如果排在前L的鏈接中有m個在測試集中,則有m個鏈接預測準確,因此,Precision值越大說明預測結果越準確.

表1 實驗數據統計結果
Table 1 Statistical results of experimental data

用戶數微博數用戶平均原創微博數7531864177114.7

4.2.2 實驗步驟及結果分析

以互動相似度作為變權重值時,對形成的社會關系網絡進行鏈接預測.分別采用4種算法WCN、WRA、WRALP、本文的PWRALP對建立的用戶互動關系網絡做鏈接預測實驗,比較預測準確性.我們對原始數據集進行了100次隨機劃分,得到含90%鏈接數的訓練集和含10%鏈接數的測試集.

在AUC指標評估方法中,分別進行了500、1000 和3000次隨機抽取比較,預測精度結果見表2.對訓練集中不存在的所有可能邊計算其分數值,并通過刪除孤立點數據的處理,得到包含7531個節點,12752條邊的網絡,計算節點對數量為7531×7530/2-12752=28341463.用戶節點的選取采用隨機抽取的方法,并且3個數量的每次抽取都是獨立進行的,節點關系的邊,是取兩個用戶節點有“轉發”關系的則視為一條邊.在Precision評估方法中,只有分數值排在前面的預測連邊才具有推薦意義,我們設定L的取值為500、1000和2000,取預測結果中的前L個鏈接與測試集進行比較,預測精度結果見表3.

表2 AUC結果
Table 2 AUC results

n=500n=1000n=3000WCN0.56730.73620.8601WRA0.56940.74910.8685WRALP0.57480.75860.8751PWRALP0.57980.76750.8853

由表2可以看出,這4種指標AUC值均非常接近,無法說明何種算法更優.原因在于不同規模的數據集中,兩個節點具有共同鄰居的概率不同,大規模網絡相較于中小規模網絡,這個概率要低,導致基于共同鄰居的鏈接預測方法的AUC值差別不大.因此,僅僅以AUC指標測試大規模數據集并不合適.表3中4種算法是分別進行了10次訓練集和測試集的隨機劃分,最終以計算平均值作為各組實驗結果,其中的ε=0.001.PWRALP的預測精度比WCN、WRA和WRALP均有所提高,由此可知,本文提出的加權方法在不同的推薦長度情況下均取得最優的預測結果.

表3 Precision結果
Table 3 Precision results

L=500L=1000L=2000WCN0.38870.59440.8116WRA0.32770.60180.8360WRALP0.44210.62940.8572PWRALP0.44780.63890.8726

5 結束語

本文針對節點鏈接預測指標未考慮“單方鄰居”作用的不足,將節點指標和路徑指標相結合,引入可信任路徑權重計算方法,提出基于邊權乘積的PWRALP加權相似性指標,通過對比實驗證明該方法能夠獲得更高的預測準確率.后續研究會對社交網絡的有向性進行分析,并與本文研究結果結合,對社交網絡的用戶關系鏈接預測做綜合分析.