初曉宇，高守瑋

(上海大學(xué) 機(jī)電工程與自動(dòng)化學(xué)院，上海 200000)

1 概 述

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

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

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

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

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

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

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

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

盡管關(guān)鍵節(jié)點(diǎn)的存在使得無(wú)標(biāo)度網(wǎng)絡(luò)對(duì)突發(fā)故障具有較強(qiáng)容忍能力[12]，但同時(shí)也更容易受到協(xié)同攻擊?，F(xiàn)實(shí)中許多網(wǎng)絡(luò)都帶有無(wú)標(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é)點(diǎn)數(shù)呈指數(shù)型下跌。因此，可認(rèn)為豆瓣網(wǎng)的度分布為冪律分布，即可說(shuō)明類似豆瓣網(wǎng)在線社交網(wǎng)絡(luò)[13-14]都屬于無(wú)標(biāo)度網(wǎng)絡(luò)的范疇。

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

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

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

Sxy=k(x)×k(y)

(1)

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

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

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

3.3 精確度測(cè)量

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

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

(2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(3)

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

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

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

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

(4)

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

5 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)數(shù)據(jù)采用的是新浪微博上的部分用戶關(guān)系數(shù)據(jù)，數(shù)據(jù)中包含用戶關(guān)系以及用戶的個(gè)人屬性信息，如性別、地域、粉絲數(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é)對(duì)微博數(shù)據(jù)集進(jìn)行實(shí)證分析。具體步驟如下：

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

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

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

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

混合指標(biāo)與PA指標(biāo)/用戶屬性相似度對(duì)比的試驗(yàn)測(cè)評(píng)效果如圖7所示。

圖7 對(duì)比試驗(yàn)測(cè)評(píng)效果

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

6 結(jié)束語(yǔ)

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