基于優(yōu)先連接和用戶屬性的鏈路預(yù)測算法研究

初曉宇，高守瑋

(上海大學(xué) 機電工程與自動化學(xué)院，上海 200000)

1 概 述

鏈路預(yù)測作為一門典型的交叉學(xué)科，已經(jīng)成為網(wǎng)絡(luò)信息挖掘和預(yù)測領(lǐng)域最具活力的研究方向之一，其應(yīng)用場景生活中隨處可見(如圖1所示)。當(dāng)然，鏈路預(yù)測作為復(fù)雜網(wǎng)絡(luò)中的重要研究課題，其主要功能是根據(jù)已知的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點的相關(guān)信息來預(yù)測網(wǎng)絡(luò)中節(jié)點之間是否存在連接或發(fā)現(xiàn)已存在但尚未被發(fā)現(xiàn)的邊。在微博社交網(wǎng)絡(luò)中，用戶代表網(wǎng)絡(luò)節(jié)點，用戶之間的關(guān)系即代表節(jié)點之間的連邊，而鏈路預(yù)測就是預(yù)測用戶間關(guān)系的重要方式。

圖1 鏈路預(yù)測的應(yīng)用

基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的鏈路預(yù)測相似性算法是根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)特征衡量節(jié)點間相似性并預(yù)測節(jié)點間連接的可能性。在社交網(wǎng)絡(luò)(微博)中的表征為預(yù)測兩個陌生用戶成為好友的可能。Liben-Nowell和Kleinberg[1]是最早通過計算社會網(wǎng)絡(luò)中節(jié)點的拓?fù)浣Y(jié)構(gòu)的結(jié)構(gòu)接近性來分析社會網(wǎng)絡(luò)的；后來出現(xiàn)的基于節(jié)點度的共同鄰居(common neighbor，CN)[2]是指兩個節(jié)點擁有的共同鄰居越多，那么二者越傾向于構(gòu)成連邊。Adamic-Adar(AA)指標(biāo)[3]考慮兩節(jié)點共同鄰居的度信息，并為每個節(jié)點分配權(quán)重。20世紀(jì)末，Barabási和Albert通過對無標(biāo)度網(wǎng)絡(luò)的研究，提出了優(yōu)先連接[4](PA)。PA是指在網(wǎng)絡(luò)中兩個節(jié)點連邊與否取決于二者節(jié)點度的乘積，并將它應(yīng)用于解釋在自然、技術(shù)以及社會體系中普遍出現(xiàn)的無標(biāo)度網(wǎng)絡(luò)，研究成果頗豐。傅穎斌和陳羽中根據(jù)節(jié)點的特征向量和節(jié)點間相似性信息進(jìn)行微博用戶分析[5]，最終發(fā)現(xiàn)用戶的屬性特征對用戶關(guān)系的產(chǎn)生具有重要影響；李博等提出了JAFLink混合算法[6]來進(jìn)行好友推薦，結(jié)果顯著。

研究發(fā)現(xiàn)，社交網(wǎng)絡(luò)錯雜紛繁，僅僅通過節(jié)點屬性或者拓?fù)浣Y(jié)構(gòu)某一信息很難對節(jié)點對進(jìn)行刻畫和預(yù)測，節(jié)點屬性都缺乏一定的普適度。因此，文中基于社交網(wǎng)絡(luò)(新浪微博)提出了一種綜合考慮網(wǎng)絡(luò)結(jié)構(gòu)與用戶屬性的PAA算法。該算法兼顧社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和用戶屬性信息，更加全面地對整個網(wǎng)絡(luò)進(jìn)行剖析和考究，從而為用戶提供更加精準(zhǔn)的推薦服務(wù)。

2 社交網(wǎng)絡(luò)的模型構(gòu)建

網(wǎng)絡(luò)中最重要的兩個因子是節(jié)點和連邊。社交網(wǎng)絡(luò)是一個具象的復(fù)雜網(wǎng)絡(luò)[7]，在保留復(fù)雜網(wǎng)絡(luò)本身特征[8]的同時，也衍生了自己獨特的屬性。

社交平臺的核心是用戶，億萬級的在線用戶是一個社交平臺的價值所在。如果把整個社交網(wǎng)絡(luò)系統(tǒng)比作神經(jīng)系統(tǒng)，那么用戶之間的相互關(guān)系，即“關(guān)注”和“粉絲”，便是“神經(jīng)元”。一個用戶A關(guān)注了另一個用戶B，用戶A也可以查看用戶B的關(guān)注。從另一個方向考慮，用戶A成為了用戶B的粉絲，用戶B本身作為粉絲也給他的關(guān)注帶來了新的粉絲。當(dāng)一個用戶的粉絲數(shù)很多，即被關(guān)注度很高，那么他的一些言行舉止多會對整個社交網(wǎng)絡(luò)產(chǎn)生巨大的影響。從網(wǎng)絡(luò)知識的角度解釋，當(dāng)一個節(jié)點與很多節(jié)點產(chǎn)生了連邊關(guān)系，那么該節(jié)點在整個網(wǎng)絡(luò)中的影響是巨大的。

對于復(fù)雜網(wǎng)絡(luò)建模的研究[9]在近年來成為熱點，各種數(shù)學(xué)模型的涌現(xiàn)為復(fù)雜網(wǎng)絡(luò)建模提供了構(gòu)造器。目前比較成熟完善的網(wǎng)絡(luò)模型大致包括四種：規(guī)則網(wǎng)絡(luò)、隨機網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)。其中，無標(biāo)度網(wǎng)絡(luò)[10]的一個顯著特征是大多數(shù)節(jié)點只存在幾個鏈路，而一些節(jié)點與其他節(jié)點具有大量的連接，其度值完全符合冪律分布[11]。

盡管關(guān)鍵節(jié)點的存在使得無標(biāo)度網(wǎng)絡(luò)對突發(fā)故障具有較強容忍能力[12]，但同時也更容易受到協(xié)同攻擊?，F(xiàn)實中許多網(wǎng)絡(luò)都帶有無標(biāo)度的特性，而社交網(wǎng)絡(luò)恰恰位列其中。豆瓣網(wǎng)的網(wǎng)絡(luò)結(jié)構(gòu)度分布如圖2所示。

圖2 豆瓣網(wǎng)的網(wǎng)絡(luò)結(jié)構(gòu)度分布

豆瓣網(wǎng)的度分布如圖3所示。

圖3 豆瓣網(wǎng)的度分布

由圖3所示，隨度值增大，節(jié)點數(shù)呈指數(shù)型下跌。因此，可認(rèn)為豆瓣網(wǎng)的度分布為冪律分布，即可說明類似豆瓣網(wǎng)在線社交網(wǎng)絡(luò)[13-14]都屬于無標(biāo)度網(wǎng)絡(luò)的范疇。

3 鏈路預(yù)測算法描述

3.1 鏈路預(yù)測相似性算法

優(yōu)先連接指標(biāo)[15](professional attachment，PA)是一種基于節(jié)點度的相似性指標(biāo)，主要用于構(gòu)建無標(biāo)度網(wǎng)絡(luò)。文獻(xiàn)[2]中表明，在無標(biāo)度網(wǎng)絡(luò)中，一個新邊將被添加到節(jié)點x的概率與節(jié)點x的度值k(x)成正比。因此可以得出結(jié)論，當(dāng)一條新邊將要連接兩個節(jié)點x和y時，與兩個節(jié)點度的乘積成正比。該算法的復(fù)雜度較其他算法低，因為需要的信息量最少。

Sxy=k(x)×k(y)

(1)

對于網(wǎng)絡(luò)中的節(jié)點x，定義它的鄰居為τ(x)，k(x)=τ(x)為節(jié)點x的度。

3.2 社交網(wǎng)絡(luò)用戶個人屬性

社交網(wǎng)絡(luò)[10,13-14]除網(wǎng)絡(luò)結(jié)構(gòu)屬性外還具備較強的節(jié)點個性化屬性。日常生活中，在遠(yuǎn)離家鄉(xiāng)的地方，人們更愿意與同一家鄉(xiāng)、同一行業(yè)、同一學(xué)校、相似年齡的人成為好友，這就意味著用戶屬性的相似性對是否成為好友具有重要的意義，特別是在社交網(wǎng)絡(luò)[14]上，不能只考慮網(wǎng)絡(luò)結(jié)構(gòu)而忽視它的存在。因此，在鏈路預(yù)測中加入用戶屬性相似度信息將有利于提升好友推薦精確度。

3.3 精確度測量

文中選擇的測評鏈路預(yù)測精確度的方法是“ROC曲線下面積法”[1](area under curve，AUC)。AUC適用于從整體上衡量算法的精確度，是鏈路預(yù)測中對結(jié)果進(jìn)行精度評價的最普遍的量化方法。在實驗過程中，為了保證待測算法的精度和準(zhǔn)度，文中將數(shù)據(jù)全集E分為訓(xùn)練集ET和測試集EP兩組獨立的數(shù)據(jù)集。在數(shù)學(xué)上的表示[2]即E=ET∪EP，且ET∩EP=?。在此，將屬于U但不屬于E的邊定義為不存在的邊。

AUC可理解為在測試集中連邊的分?jǐn)?shù)值比隨機選擇一個不存在的邊的分?jǐn)?shù)值高的概率。每次隨機地從測試集中選一條邊與隨機選擇的不存在的邊進(jìn)行比較，如果測試集中邊的分?jǐn)?shù)值大于不存在邊的分?jǐn)?shù)值，就加1分；如果兩個分?jǐn)?shù)值相等，就加0.5分。獨立比較n次，如果測試集中有n的邊的分?jǐn)?shù)值大于不存在的邊的分?jǐn)?shù)，有n次兩邊的分?jǐn)?shù)值相等，則AUC定義為：

(2)

如果所有邊是隨機產(chǎn)生的，AUC=0.5。因此AUC的數(shù)值大小衡量了算法的精確程度。

4 算法選擇與構(gòu)建

4.1 鏈路預(yù)測的相似性指標(biāo)選擇

文中將用Python模擬無標(biāo)度網(wǎng)絡(luò)模型，并將基于相似性的鏈路預(yù)測方法應(yīng)用到無標(biāo)度網(wǎng)絡(luò)模型中，探究針對無標(biāo)度網(wǎng)絡(luò)精確度最高的指標(biāo)。模擬無標(biāo)度網(wǎng)絡(luò)共包含200個節(jié)點，18 078條邊，如圖4所示。

圖4 模擬無標(biāo)度網(wǎng)絡(luò)

模擬無標(biāo)度網(wǎng)絡(luò)的度分布如圖5所示。

圖5 模擬無標(biāo)度網(wǎng)絡(luò)的度分布

由圖5可知，模擬的無標(biāo)度網(wǎng)絡(luò)圖嚴(yán)格服從冪律分布。隨度值增大，節(jié)點數(shù)呈指數(shù)型下降。將鏈路預(yù)測相似性指標(biāo)應(yīng)用于該網(wǎng)絡(luò)，測評結(jié)果如表1所示。

表1 9種相似性指標(biāo)評測結(jié)果

實驗結(jié)果表明，PA指標(biāo)在考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的情況下，針對無標(biāo)度網(wǎng)絡(luò)是最優(yōu)的選擇。

此外，對于社交網(wǎng)絡(luò)而言，用戶的屬性特征具有不可忽視的存在意義。在社交網(wǎng)絡(luò)這一復(fù)雜網(wǎng)絡(luò)中，用戶個體作為網(wǎng)絡(luò)節(jié)點的具象存在，其自身所具備的用戶屬性因網(wǎng)絡(luò)的社交性成為一項重要算法指標(biāo)。因此，文中提出一種基于社交網(wǎng)絡(luò)關(guān)系推薦的混合鏈路預(yù)測算法，它是在考慮社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的同時兼顧節(jié)點自身特性，改進(jìn)原有算法，提升鏈路預(yù)測精確度。

4.2 用戶屬性相似度指標(biāo)構(gòu)建

混合算法考慮的社交網(wǎng)絡(luò)屬性包括用戶的地域、用戶粉絲數(shù)、用戶關(guān)注數(shù)、用戶的個人標(biāo)簽信息等屬性，這些屬性將被量化成計算相似度的矩陣，與基于網(wǎng)絡(luò)結(jié)構(gòu)測量用戶相似的PA指標(biāo)一起構(gòu)建混合相似性指標(biāo)，從而計算用戶之間的相似度，相似度高的將被推薦為好友。相似程度的衡量是通過計算矩陣之間的余弦相似度來表征的，如式3所示：

sim(x,y)=cos(x,y)+a

(3)

兩個向量由用戶的屬性來充當(dāng)。x,y分別為鄰居節(jié)點和目標(biāo)節(jié)點(表示向用戶x進(jìn)行好友推薦)，a為調(diào)節(jié)變量，通過調(diào)整該變量使所有節(jié)點都能在計算中發(fā)揮作用，避免出現(xiàn)無效狀態(tài)。

4.3 混合相似性指標(biāo)構(gòu)建

結(jié)合PA指標(biāo)、社交網(wǎng)絡(luò)用戶屬性特征相似度的混合鏈路預(yù)測公式如下：

PAA(x,y)=Sxy×sim(x,y)=k(x)×k(y)×[cos(x,y)+a]

(4)

其中，k(x)、k(y)為x,y節(jié)點的節(jié)點度。式中矩陣相乘，代表兩個矩陣中對應(yīng)元素相乘，其結(jié)果依然是一個N*N的矩陣(N代表用戶數(shù)量)。

5 實驗結(jié)果與分析

實驗數(shù)據(jù)采用的是新浪微博上的部分用戶關(guān)系數(shù)據(jù)，數(shù)據(jù)中包含用戶關(guān)系以及用戶的個人屬性信息，如性別、地域、粉絲數(shù)、關(guān)注度。數(shù)據(jù)集中共包含用戶數(shù)9 104人，用戶關(guān)系數(shù)61 297。微博數(shù)據(jù)集結(jié)構(gòu)如圖6所示。

圖6 微博數(shù)據(jù)集結(jié)構(gòu)

結(jié)合上文給出的混合相似性指標(biāo)，本節(jié)對微博數(shù)據(jù)集進(jìn)行實證分析。具體步驟如下：

步驟1：數(shù)據(jù)處理，去除無效數(shù)據(jù)(沒有關(guān)系連邊的用戶)；

步驟2：按7∶3的比例產(chǎn)生訓(xùn)練集和測試集；

步驟3：選擇PA指標(biāo)與用戶屬性值計算混合指標(biāo)；

步驟4：計算指標(biāo)精確度并進(jìn)行比較。

混合指標(biāo)與PA指標(biāo)/用戶屬性相似度對比的試驗測評效果如圖7所示。

圖7 對比試驗測評效果

由圖7所示，優(yōu)先連接指標(biāo)的測量精確度為0.82，用戶屬性測量的精確度為0.59，文中構(gòu)造的結(jié)合用戶屬性的優(yōu)先連接指標(biāo)的測量精確度為0.89，比原始指標(biāo)提升了0.07。效果提升較為明顯，說明加入用戶屬性相似度對掌握在線社交網(wǎng)絡(luò)的整體結(jié)構(gòu)具有一定的積極作用。

6 結(jié)束語

通過對復(fù)雜網(wǎng)絡(luò)和鏈路預(yù)測的學(xué)習(xí)，首先驗證了社交網(wǎng)絡(luò)呈冪律分布，滿足無標(biāo)度網(wǎng)絡(luò)的典型特性；同時，通過分析微博社交網(wǎng)絡(luò)數(shù)據(jù)，得出在鏈路預(yù)測中優(yōu)先連接指標(biāo)(PA)表現(xiàn)最優(yōu)；最后，考慮到社交網(wǎng)絡(luò)的社交性和用戶的個性，在算法中加入用戶屬性這一重要因子。最終提出了基于優(yōu)先連接和用戶屬性的鏈路預(yù)測算法PAA。實驗結(jié)果表明，PAA算法的AUC值明顯大于僅僅考慮優(yōu)先連接或者用戶屬性的數(shù)值結(jié)果，表明該算法可以更加精準(zhǔn)地為用戶提供好友推薦。