結(jié)合用戶互動加權(quán)圖的社交網(wǎng)絡(luò)鏈接預(yù)測

白 楊,鄧貴仕

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

1 引 言

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

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

現(xiàn)有的鏈接預(yù)測研究主要集中在無權(quán)網(wǎng)絡(luò)上,只反映了網(wǎng)絡(luò)的拓撲結(jié)構(gòu)和節(jié)點連接方式,不能全面客觀反映某些真實網(wǎng)絡(luò)的情況,針對加權(quán)網(wǎng)絡(luò)的鏈接預(yù)測適用范圍有限、預(yù)測結(jié)果不夠準(zhǔn)確.并且,大多數(shù)鏈接預(yù)測算法僅單方面考慮了圖的局部或全局特性,在預(yù)測準(zhǔn)確率和計算復(fù)雜度上難以均衡.

圖1 用戶關(guān)系網(wǎng)絡(luò)示意圖Fig.1 Diagram of user relationship networks

本文在對已有方法進行分析和總結(jié)的基礎(chǔ)上,在考慮用戶間接結(jié)構(gòu)的基礎(chǔ)上,針對用戶互動行為分析,提出一種新的鏈接預(yù)測算法PWRALP,實現(xiàn)基于局部圖的綜合節(jié)點及路徑的加權(quán)網(wǎng)絡(luò)鏈接預(yù)測.

2 相關(guān)工作

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

2.1 無權(quán)網(wǎng)絡(luò)的鏈接預(yù)測方法

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

(1)

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

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

圖2 節(jié)點x和y及共同鄰居網(wǎng)絡(luò)Fig.2 Networks including x,y and their co-neighbors

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

(2)

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

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

(3)

其中,lx→y是從節(jié)x到y(tǒng)的長度為3的路徑,i和j是路徑lx→y的中間節(jié)點,ε為可調(diào)參數(shù).

2.2 加權(quán)網(wǎng)絡(luò)的鏈接預(yù)測方法

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

(4)

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

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

(5)

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

Zhao[11]提出了基于可信路徑權(quán)重相似性的加權(quán)網(wǎng)絡(luò)鏈接預(yù)測方法rWRA,在多數(shù)數(shù)據(jù)集上取得了最高的相似度預(yù)測準(zhǔn)確度,如式(6):

(6)

3 鏈接預(yù)測方法

3.1 相關(guān)定義

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

定義1.節(jié)點強度

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

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

(7)

定義2.邊權(quán)強度

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

(8)

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

3.2 一種加權(quán)圖鏈接預(yù)測算法PWRALP

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

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

(9)

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

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

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

(10)

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

(11)

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

4 實 驗

4.1 實驗數(shù)據(jù)

通過網(wǎng)絡(luò)爬蟲技術(shù)從新浪微博上采集從2013年5月到2013年9月的微博信息,用戶數(shù)總量為150728個.對數(shù)據(jù)集相關(guān)的信息做以統(tǒng)計,相關(guān)數(shù)據(jù)信息包括微博文本內(nèi)容及發(fā)布時間、戶關(guān)注列表、用戶轉(zhuǎn)發(fā)互動信息.對用戶互動關(guān)系信息進行分析,制作用戶轉(zhuǎn)發(fā)微博的統(tǒng)計圖,如圖3和圖4所示.

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

4.2 加權(quán)網(wǎng)絡(luò)鏈接預(yù)測實驗

根據(jù)式(11)計算用戶互動相似度(實驗中以轉(zhuǎn)發(fā)互動關(guān)系為代表),構(gòu)建用戶互動關(guān)系網(wǎng)絡(luò),根據(jù)式(9)進行基于互動關(guān)系的加權(quán)圖的鏈接預(yù)測.

圖4 每個用戶的轉(zhuǎn)發(fā)微博數(shù)分布Fig.4 Distribution of the number of forwarding micro-blog per user

4.2.1 評價指標(biāo)

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

表1 實驗數(shù)據(jù)統(tǒng)計結(jié)果
Table 1 Statistical results of experimental data

用戶數(shù)微博數(shù)用戶平均原創(chuàng)微博數(shù)7531864177114.7

4.2.2 實驗步驟及結(jié)果分析

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

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

表2 AUC結(jié)果
Table 2 AUC results

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

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

表3 Precision結(jié)果
Table 3 Precision results

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

5 結(jié)束語

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