基于用戶質量的關注關系預測

李旺龍，李川

（四川大學計算機學院，成都 610065）

基于用戶質量的關注關系預測

李旺龍，李川

（四川大學計算機學院，成都 610065）

鏈接預測是當前信息網絡研究中的熱點問題，旨在關注如何通過已知的網絡結構等信息預測網絡中尚未產生連邊的兩個節點之間產生鏈接的概率，鏈接關系包含好友關系、follow關系、@關系。提出基于用戶質量的關注關系鏈接預測的新方法LPR，基于真實數據的實驗表明，LPR方法較基于局部信息相似性和路徑相似性的方法，有較大的提升。

用戶質量；相似性；鏈接預測；微博

0 引言

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

常用的鏈接預測方法多是基于節點相似性進行鏈接預測，這些相似性包括用戶屬性相似性[3]、局部拓撲結構相似性[4]和路徑相似性[5]等。節點間的相似性越高，鏈接關系的產生概率越大。然而，在微博這類在線社交網絡中系統，僅憑借相似性很難刻畫用戶間鏈接關系產生的普遍規律。這主要因為：

（1）網絡中的信息傳播[6]會對鏈接關系的產生有巨大影響，微博中用戶鏈接關系的產生往往是基于微博的發出與轉發，微博被轉發的次數與該微博的發出者被其他用戶看到的概率成正比。

（2）社會學中的重要規律現象，如馬太效應[7]、二八定律[8]等，很難用相似性簡單表征。在社會網絡中占據較多資源或者處于較核心地位的人，會利用資源優勢擴充自己的資源。對微博中的鏈接關系而言，粉絲較多的用戶，會吸收更多的粉絲。

本文針對上述問題進行了研究，提出微博異構信息網絡中用戶鏈接關系的預測新算法LPR（Link Prediction Regression）。該算法利用邏輯回歸（Logistic regression）[10]方法計算鏈接關系產生的概率。

1 問題定義

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

針對微博異構信息網絡，可描述為：設G（V；E；P）為一個微博屬性圖，其中V為節點集合，包括微博和用戶這兩類；E為有向邊的集合，包括用戶與微博的鏈接關系（用戶發微博、用戶轉發微博）以及用戶與用戶的鏈接關系（關注）；P為各類節點與連邊的屬性。預測不存在的鏈接關系（用戶與微博，或者用戶與用戶）產生的概率。

2 預測算法LPR

2.1 數據處理

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

（1）過濾關注人數小于5或者關注人數大于800的用戶。

（2）過濾關注人數大于粉絲數20倍的用戶。

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

2.2 特征定義

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

通常用路徑相似性來衡量網絡中兩個節點之間關系的強弱。設網絡中的兩個節點x和y，要衡量x到y這條鏈接關系的強弱，可以通過計算網絡中從x經過任意一個中間節點z到達y的路徑的條數。

在信息傳播理論當中，網絡中的核心節點往往占有更多的資源，即二八定律。在微博網絡中，一些權威或影響力較高的用戶往往會擁有更多的粉絲。他們所發的微博會被更多其他用戶轉發。從而有了更多機會被其他用戶關注，即會產生馬太效應。因此，對于一條待預測的用戶鏈接關系，兩個用戶會具有不同的影響力和權威值，他們的影響力和權威值，對這條鏈接關系會產生一定的影響

定義（用戶質量）（User Quality）設T表示用戶發出的微博數，R表示用戶被轉發的微博數，L表示用戶發出的包含鏈接的微博數，PR為用戶在微博系統中的PR值，則用戶質量可表示為：

2.3 預測模型

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

決策邊界：

損失函數：

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

（1）按2.1節的方法過濾后網絡中邊的集合為E。

（2）隨機抽取若干網絡中的鏈接ET作為正例。

（3）隨機抽取若干不存在于網絡中的鏈接EF作為負例。

（4）在E-ET-EF的網絡中計算ET∪EF中所有節點的特征以及鏈接的特征，并將節點的特征轉換為鏈接關系的特征，最終鏈接關系的特征集為X。

（5）將EF∪ET分為訓練集、驗證集和測試集。

（6）在訓練集上訓練模型，在驗證集上選擇使預測結果最優的模型超參數（θ、λ、SGD百分比和SGD學習率），得到最終模型hθ（x）和閾值θ。

（7）將測試集中任意一條鏈接關系代入模型，即可得到該鏈接關系產生的概率P。當P＞θ時，預測該鏈接關系將會產生，否則，預測該鏈接關系不會產生。

3 實驗

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

在計算基于局部結構相似性時，定義兩個節點的局部結構相似性為他們入度和出度方向Jaccard系數的平均值。即：

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

圖1 LPR算法性能

可以發現，LPR較SS和TwoStep有明顯效果提升。其主要原因在于社交網絡具有高度稀疏性，絕大多數用戶間都沒有共同好友或好友間二步之內不可達，LPR綜合了結構相似性與路徑相似性作為特征并且額外加入起點和終點用戶質量作為特征，更細致地刻畫了用戶間鏈接關系的產生因素。

4 結語

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

圖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] 呂琳媛.復雜網絡鏈路預測[J].電子科技大學學報,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] 徐玉萍.網絡信息傳播規律研究[J].圖書館學研究,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] 李航.統計學習方法[M].北京：清華大學出版社,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-），男，湖北孝感人，碩士，研究方向為數據挖掘、分布式計算

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

2014-12-25

2015-01-10

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