李旺龍，李川

（四川大學(xué)計算機(jī)學(xué)院，成都 610065）

基于用戶質(zhì)量的關(guān)注關(guān)系預(yù)測

李旺龍，李川

（四川大學(xué)計算機(jī)學(xué)院，成都 610065）

鏈接預(yù)測是當(dāng)前信息網(wǎng)絡(luò)研究中的熱點問題，旨在關(guān)注如何通過已知的網(wǎng)絡(luò)結(jié)構(gòu)等信息預(yù)測網(wǎng)絡(luò)中尚未產(chǎn)生連邊的兩個節(jié)點之間產(chǎn)生鏈接的概率，鏈接關(guān)系包含好友關(guān)系、follow關(guān)系、@關(guān)系。提出基于用戶質(zhì)量的關(guān)注關(guān)系鏈接預(yù)測的新方法LPR，基于真實數(shù)據(jù)的實驗表明，LPR方法較基于局部信息相似性和路徑相似性的方法，有較大的提升。

用戶質(zhì)量；相似性；鏈接預(yù)測；微博

0 引言

微博中的鏈接關(guān)系包含好友關(guān)系、follow關(guān)系、@關(guān)系等。這些關(guān)系均為有向關(guān)系，可表示為一個有向圖。微博是一種典型的異構(gòu)信息網(wǎng)絡(luò)[1]。用戶和微博可看作網(wǎng)絡(luò)中的節(jié)點，用戶間、用戶與微博間可有不同類型的鏈接關(guān)系。鏈接預(yù)測是當(dāng)前信息網(wǎng)絡(luò)研究中的熱點問題，旨在關(guān)注如何通過已知的網(wǎng)絡(luò)結(jié)構(gòu)等信息預(yù)測網(wǎng)絡(luò)中尚未產(chǎn)生連邊的兩個節(jié)點之間產(chǎn)生鏈接的概率[2]。鏈接預(yù)測在不同的場景中有不同的應(yīng)用和價值。例如，在犯罪分子網(wǎng)絡(luò)中，鏈接預(yù)測可用來發(fā)現(xiàn)潛在的犯罪分子；在社交網(wǎng)絡(luò)中，鏈接預(yù)測可指示用戶間建立好友關(guān)系的可能性，為用戶提供好友推薦。另外，鏈接的產(chǎn)生隱含著網(wǎng)絡(luò)結(jié)構(gòu)的演化，抓住鏈接關(guān)系產(chǎn)生規(guī)律往往能揭示網(wǎng)絡(luò)的演化趨勢。

常用的鏈接預(yù)測方法多是基于節(jié)點相似性進(jìn)行鏈接預(yù)測，這些相似性包括用戶屬性相似性[3]、局部拓?fù)浣Y(jié)構(gòu)相似性[4]和路徑相似性[5]等。節(jié)點間的相似性越高，鏈接關(guān)系的產(chǎn)生概率越大。然而，在微博這類在線社交網(wǎng)絡(luò)中系統(tǒng)，僅憑借相似性很難刻畫用戶間鏈接關(guān)系產(chǎn)生的普遍規(guī)律。這主要因為：

（1）網(wǎng)絡(luò)中的信息傳播[6]會對鏈接關(guān)系的產(chǎn)生有巨大影響，微博中用戶鏈接關(guān)系的產(chǎn)生往往是基于微博的發(fā)出與轉(zhuǎn)發(fā)，微博被轉(zhuǎn)發(fā)的次數(shù)與該微博的發(fā)出者被其他用戶看到的概率成正比。

（2）社會學(xué)中的重要規(guī)律現(xiàn)象，如馬太效應(yīng)[7]、二八定律[8]等，很難用相似性簡單表征。在社會網(wǎng)絡(luò)中占據(jù)較多資源或者處于較核心地位的人，會利用資源優(yōu)勢擴(kuò)充自己的資源。對微博中的鏈接關(guān)系而言，粉絲較多的用戶，會吸收更多的粉絲。

本文針對上述問題進(jìn)行了研究，提出微博異構(gòu)信息網(wǎng)絡(luò)中用戶鏈接關(guān)系的預(yù)測新算法LPR（Link Prediction Regression）。該算法利用邏輯回歸（Logistic regression）[10]方法計算鏈接關(guān)系產(chǎn)生的概率。

1 問題定義

定義G（V；E；P）為一個屬性圖，其中V為節(jié)點集合，E為有向邊集合，P為節(jié)點和邊的屬性集合。網(wǎng)絡(luò)總節(jié)點數(shù)為N，邊數(shù)為M。網(wǎng)絡(luò)共有N*（N-1）條有向邊，即全集U。通過一種鏈路預(yù)測的方法，對節(jié)點對（x,y）∈（UE）所表示的有向邊賦予一個分?jǐn)?shù)值Sxy，分值越大表示有向邊產(chǎn)生的概率越大。

針對微博異構(gòu)信息網(wǎng)絡(luò)，可描述為：設(shè)G（V；E；P）為一個微博屬性圖，其中V為節(jié)點集合，包括微博和用戶這兩類；E為有向邊的集合，包括用戶與微博的鏈接關(guān)系（用戶發(fā)微博、用戶轉(zhuǎn)發(fā)微博）以及用戶與用戶的鏈接關(guān)系（關(guān)注）；P為各類節(jié)點與連邊的屬性。預(yù)測不存在的鏈接關(guān)系（用戶與微博，或者用戶與用戶）產(chǎn)生的概率。

2 預(yù)測算法LPR

2.1 數(shù)據(jù)處理

King-wa Fu[11]的研究表明在微博系統(tǒng)中存在大量的“僵尸用戶”。這些“僵尸用戶”多為營銷公司注冊，用來操縱關(guān)注人數(shù)獲取利益。這類用戶通常會關(guān)注大量用戶或者關(guān)注用戶數(shù)遠(yuǎn)大于其粉絲數(shù)。另一類是活躍度較低的用戶，這類用戶很少使用微博，通常關(guān)注的用戶很少。本文將這兩類用戶看作噪聲用戶。為減少噪聲用戶對鏈接預(yù)測方法的影響，對用戶進(jìn)行過濾顯得十分必要。過濾條件如下：

（1）過濾關(guān)注人數(shù)小于5或者關(guān)注人數(shù)大于800的用戶。

（2）過濾關(guān)注人數(shù)大于粉絲數(shù)20倍的用戶。

（3）過濾前兩步處理后PR值較小的1%的用戶。

2.2 特征定義

在微博這種弱關(guān)系網(wǎng)絡(luò)中，用戶間以相同的興趣聚合在一起，兩個用戶間共同關(guān)注的用戶數(shù)，可表征這兩個用戶興趣的相似性；而兩用戶共同粉絲數(shù)，則可表征在其他用戶眼中他們的相似性。Jaccard[4]系數(shù)，在考慮共同鄰居的同時也考慮了這兩個用戶的所有鄰居，能較合理地刻畫兩個用戶的結(jié)構(gòu)相似性。

通常用路徑相似性來衡量網(wǎng)絡(luò)中兩個節(jié)點之間關(guān)系的強(qiáng)弱。設(shè)網(wǎng)絡(luò)中的兩個節(jié)點x和y，要衡量x到y(tǒng)這條鏈接關(guān)系的強(qiáng)弱，可以通過計算網(wǎng)絡(luò)中從x經(jīng)過任意一個中間節(jié)點z到達(dá)y的路徑的條數(shù)。

在信息傳播理論當(dāng)中，網(wǎng)絡(luò)中的核心節(jié)點往往占有更多的資源，即二八定律。在微博網(wǎng)絡(luò)中，一些權(quán)威或影響力較高的用戶往往會擁有更多的粉絲。他們所發(fā)的微博會被更多其他用戶轉(zhuǎn)發(fā)。從而有了更多機(jī)會被其他用戶關(guān)注，即會產(chǎn)生馬太效應(yīng)。因此，對于一條待預(yù)測的用戶鏈接關(guān)系，兩個用戶會具有不同的影響力和權(quán)威值，他們的影響力和權(quán)威值，對這條鏈接關(guān)系會產(chǎn)生一定的影響

定義（用戶質(zhì)量）（User Quality）設(shè)T表示用戶發(fā)出的微博數(shù)，R表示用戶被轉(zhuǎn)發(fā)的微博數(shù)，L表示用戶發(fā)出的包含鏈接的微博數(shù)，PR為用戶在微博系統(tǒng)中的PR值，則用戶質(zhì)量可表示為：

2.3 預(yù)測模型

在LPR中，利用邏輯回歸可以計算出一條鏈接關(guān)系產(chǎn)生的概率P。將概率大于閾值θ的鏈接關(guān)系預(yù)測為將會產(chǎn)生，否則預(yù)測為不會產(chǎn)生。邏輯回歸的一般性表示如下：

決策邊界：

損失函數(shù)：

其中m為訓(xùn)練集的大小，n為回歸參數(shù)的數(shù)量，x（i）為第i個訓(xùn)練數(shù)據(jù)，θj為第j個回歸參數(shù)，λ為正則化參數(shù)。優(yōu)化求解時，采用隨機(jī)梯度下降法（SGD，Stochastic Gradient Descent）。由此，得到LPR算法具體過程為：

（1）按2.1節(jié)的方法過濾后網(wǎng)絡(luò)中邊的集合為E。

（2）隨機(jī)抽取若干網(wǎng)絡(luò)中的鏈接ET作為正例。

（3）隨機(jī)抽取若干不存在于網(wǎng)絡(luò)中的鏈接EF作為負(fù)例。

（4）在E-ET-EF的網(wǎng)絡(luò)中計算ET∪EF中所有節(jié)點的特征以及鏈接的特征，并將節(jié)點的特征轉(zhuǎn)換為鏈接關(guān)系的特征，最終鏈接關(guān)系的特征集為X。

（5）將EF∪ET分為訓(xùn)練集、驗證集和測試集。

（6）在訓(xùn)練集上訓(xùn)練模型，在驗證集上選擇使預(yù)測結(jié)果最優(yōu)的模型超參數(shù)（θ、λ、SGD百分比和SGD學(xué)習(xí)率），得到最終模型hθ（x）和閾值θ。

（7）將測試集中任意一條鏈接關(guān)系代入模型，即可得到該鏈接關(guān)系產(chǎn)生的概率P。當(dāng)P＞θ時，預(yù)測該鏈接關(guān)系將會產(chǎn)生，否則，預(yù)測該鏈接關(guān)系不會產(chǎn)生。

3 實驗

為衡量LPR算法的有效性，本文選取了真實的微博數(shù)據(jù)，主要包括關(guān)注關(guān)系和微博信息數(shù)據(jù)，并與基于局部結(jié)構(gòu)相似性和路徑相似性的鏈接預(yù)測方法進(jìn)行比較。在LPR中模型的訓(xùn)練與驗證階段，先按在驗證集上F-Score最大的得到2.3節(jié)提到的超參數(shù)，再將學(xué)習(xí)率縮小為原來的一半，迭代不同的次數(shù)得到驗證集上不同的F-Score，如圖1所示。

在計算基于局部結(jié)構(gòu)相似性時，定義兩個節(jié)點的局部結(jié)構(gòu)相似性為他們?nèi)攵群统龆确较騄accard系數(shù)的平均值。即：

在計算基于路徑的相似性時，直接選取2.2節(jié)計算節(jié)點關(guān)系強(qiáng)度的特征，定義為TwoStep。在測試集上，LPR、SS與TwoStep的準(zhǔn)確率，召回率以及F-Score比較如圖2所示。

圖1 LPR算法性能

可以發(fā)現(xiàn)，LPR較SS和TwoStep有明顯效果提升。其主要原因在于社交網(wǎng)絡(luò)具有高度稀疏性，絕大多數(shù)用戶間都沒有共同好友或好友間二步之內(nèi)不可達(dá)，LPR綜合了結(jié)構(gòu)相似性與路徑相似性作為特征并且額外加入起點和終點用戶質(zhì)量作為特征，更細(xì)致地刻畫了用戶間鏈接關(guān)系的產(chǎn)生因素。

4 結(jié)語

本文基于信息傳播的理論，提出在微博這種異構(gòu)信息網(wǎng)絡(luò)中的用戶質(zhì)量度量，且提出了預(yù)測微博中用戶間鏈接關(guān)系產(chǎn)生的方法——LPR。鏈接預(yù)測是一個有廣泛應(yīng)用場景的研究問題，不同的場景對應(yīng)不同的異構(gòu)信息網(wǎng)絡(luò)。在不同的異構(gòu)信息網(wǎng)絡(luò)中，節(jié)點和邊的特征會有很大不同。傳統(tǒng)基于相似性的方法，在解決鏈接預(yù)測問題時，存在較大的局限性和主觀性。而LPR方法，綜合基于相似性的特征和用戶質(zhì)量。實驗結(jié)果證實了該方法的可行性與有效性。

圖2 SS、TwoStep與LPR效果比較

[1] Han J.Mining Heterogeneous Information Networks:the Next Frontier[C].Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2012:2～3

[2] 呂琳媛.復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測[J].電子科技大學(xué)學(xué)報,2010,39（5）:652

[3] Lin D.An Information-Theoretic Definition of Similarity[C].ICML.1998,98:296～304

[4] Jaccard.http://en.wikipedia.org/wiki/Jaccard_index#References

[5] Zhou T,Lü L,Zhang Y C.Predicting Missing Links Via Local Information[J].The European Physical Journal B,2009,71（4）:623～630

[6] 徐玉萍.網(wǎng)絡(luò)信息傳播規(guī)律研究[J].圖書館學(xué)研究,2010（6）:14-17.

[7] Merton R K.The Matthew Effect in Science[J].Science,1968,159（3810）:56～63

[8] Pareto_principle http://en.wikipedia.org/wiki/Pareto_principle

[9] Brin S,Page L.The Anatomy of a Large-Scale Hypertextual Web Search Engine[J].Computer Networks and ISDN Systems,1998,30（1）:107～117

[10] 李航.統(tǒng)計學(xué)習(xí)方法[M].北京：清華大學(xué)出版社,2012

[11] Fu K,Chau M.Reality Check for the Chinese Microblog Space:a Random Sampling Approach[J].PLoS ONE,2013,8（3）:e58356

Attention Link Prediction Based on User Data Quality

LI Wang-long，LI Chuan
（College of Computer Science,Sichuan University,Chengdu 610065）

Link prediction is one of the most heated topics in information network research,which mainly concerns how to predict the probability of new links between different pairs of nodes,including friends,follow,@relationship,etc.Proposes a new method LPR for links prediction in the micro-blog information networks.Experiments of the real data show that the LPR method is far better than methods which are based on local information similarity and path similarity.

User Data Quality;Similarity;Link Prediction;Micro-Blog

1007-1423（2015）03-0003-04

10.3969/j.issn.1007-1423.2015.03.001

李旺龍（1990-），男，湖北孝感人，碩士，研究方向為數(shù)據(jù)挖掘、分布式計算

李川（1977-），男，河南鄭州人，博士，副教授，碩士生導(dǎo)師，研究方向為數(shù)據(jù)庫、數(shù)據(jù)挖掘

2014-12-25

2015-01-10

國家自然科學(xué)基金（No.61103043）、國家“十二五”科技支撐計劃項目（No.2012BAG04B02）、武漢大學(xué)軟件工程國家重點實驗室開放基金項目（No.SKLSE2012-09-26）