朱明瑋 唐莫鳴

摘 要：微博的普及導致微博平臺數據量日益增長，因此從海量微博中快速準確地為微博用戶推薦好友成為了巨大挑戰(zhàn)。用戶的社交網絡和微博文本在一定程度上體現了用戶的價值觀和興趣愛好，有相似興趣的微博用戶更有可能成為朋友?；谏鲜鍪聦?，以用戶微博文本相似度為似然函數，使用K-means聚類對微博用戶聚類，得到微博用戶社交圈；在社交圈內部迭代計算用戶之間的相似度，同時計算用戶對其所在社交圈中其余用戶的信任度；最后，根據用戶之間的相似度和信任度完成微博好友推薦。實驗結果表明，該算法優(yōu)于傳統(tǒng)的基于社交網絡拓撲圖的好友推薦方法。

關鍵詞：社交圈；信任度；朋友推薦；微博

DOI：10.11907/rjdk.173069

中圖分類號：TP301

文獻標識碼：A 文章編號：1672-7800（2018）006-0062-05

Abstract：The popularity of micro-blog has caused an increasing amount of data on micro-blog platforms. Therefore， recommending friends quickly and accurately for micro-blog users has become a great challenge from the massive micro-blog.The users′ micro-blog behavior and social network largely reflect the users′ values and interests. Micro-blog users who have similar interests are more likely to be friends. In view of the above facts， the topic similarity of user micro-blog text is used as a likelihood function， and K-means clustering is used to cluster the micro-blog users， then the micro-blog users′ social circles are obtained. In social circles， iterative computation of the similarity between users is done， while trustworthiness of the users to the rest of the users in the social circle. Finally， according to the similarity and trust between users， the recommendation of micro-blog friends is completed. The experimental results show that the algorithm proposed in this paper is superior to the traditional recommendation method based on social network topology.

Key Words：social circle； trust degree； friends recommended； Micro-blog

0 引言

新浪微博逐漸成為人們獲得資訊和傳播信息的主要媒介之一。隨著新浪微博的普及，微博用戶數量呈井噴式增長。據統(tǒng)計，2012-2016年間微博用戶數量增長了335%，因此從海量用戶中快速準確地為微博用戶推薦好友成為巨大挑戰(zhàn)。當前針對社交網絡好友推薦有兩個主要研究方向：基于用戶興趣的主題推薦，以及基于社交網絡拓撲結構的推薦。第一個方向通過分析用戶在社交平臺上的行為（發(fā)送的博文、點贊、轉發(fā)、評論）提取用戶興趣愛好，獲得高相似度的用戶群，在此基礎上推薦好友給目標用戶?；谟脩籼卣鞯耐扑]領域通常劃分成以下3種：基于內容、基于共同興趣、基于標簽的推薦。Jeckmans A[1]通過用戶博文的文本相似度進行好友推薦；Piao S等[2]利用LDA模型挖掘用戶Tweet內容的主題詞及主題在主題詞上的概率分布，找出用戶興趣傾向的主題，推薦關注相似主題的用戶；胡聞江等[3]綜合考慮了關聯規(guī)則和用戶之間的標簽相似度，利用標簽中蘊含的語義信息，向目標用戶推薦好友；Guy等[4]搭建Lotus社交網絡進行實驗，最后得出結論：基于社交網絡拓撲圖的好友推薦算法比基于用戶特征相似度的好友推薦算法效果更好；Yin等[5]對Tweet中怎樣形成用戶關注關系作了充分研究。最終實驗結果證明：目標用戶關注關系中超過90%是通過已有好友建立的。基于用戶間拓撲關系的好友推薦算法使用基于社交圈的算法為用戶推薦好友。Davison等[6]提出一種預測鏈接的方法，該方法主要基于用戶網絡拓撲關系的相似性，推測Twitter用戶可能關注的好友。有些學者通過用戶關注列表以及關注該用戶的用戶，計算微博用戶相似度，從而進行推薦[7-8]。Chen等[9]得出結論：基于社交網絡用戶間關注關系以及鏈接分析的好友推薦對于彼此熟悉以及同屬一個社交圈的用戶推薦有著很強的指導意義。一些專家學者考慮了融合基于用戶內容相似性和基于社交網絡拓撲結構及鏈接分析的好友推薦方法。例如，Rosen等[10]構建了Author-Topic模型，對用戶的潛在主題進行挖掘，并對用戶主題傾向性分布進行統(tǒng)計分析，但該模型沒有提出清晰的用戶社交圈概念。還有一些學者將用戶的微博文本、用戶關注列表中的微博以及關注該用戶的用戶微博文本結合起來構建模型，并使用TF-IDF挖掘微博關鍵詞，找到微博用戶的興趣愛好，通過融合社交網絡的拓撲結構和微博文本的協同過濾算法進行推薦[11-12]。用戶的社交網絡拓撲結構很大程度上反映了用戶交友傾向，彼此信任度越高的用戶越有可能成為朋友，而現有方法未充分利用這些因素。因此，本文利用微博用戶相似度和信任度進行微博好友推薦。

1 用戶相似度計算

如果兩個用戶發(fā)布的微博文本相似，則說明這兩個用戶可能擁有相同的興趣愛好和相似的價值取向，因而有共同話題，彼此更容易成為朋友。因此，微博用戶發(fā)布的微博文本相似性是進行微博好友推薦的基礎。由于微博文本是短文本，使用文本主題可以很好地表征短文本，因此本文使用微博文本主題表征微博文本。通過香農提出的“相對熵”計算兩微博文本主題詞的詞頻分布，以衡量微博文本相似度。新浪微博用戶的關注焦點和關注興趣會隨著時間推移而發(fā)生變化，所以在計算文本主題時考慮時間因素可以獲得更具時效性的結果。計算微博文本主題的步驟如下：首先，將微博文本按發(fā)布時間不同進行劃分，得到不同時間片的微博文本集合；然后通過LDA挖掘每個時間片文本集合的“T”個文本主題；再通過增量Gibbs算法計算該時間片內微博文本主題在主題詞上的概率分布，其中W=V-tW-uV-t-1，V-t表示時間片t內文本集合中的單詞總數，W-u為用戶自定義權重，最終得到動態(tài)LDA模型[13]。具體算法如下：

2 社交圈發(fā)現

人以群分，有著相同興趣愛好的人，彼此之間更容易成為朋友。本文將候選用戶進行聚類，從而得到目標用戶的社交圈。由于本文推薦范圍來自目標用戶的社交網絡，目標用戶出于興趣愛好而關注某些用戶，因此聚類出的每一個社交圈都代表目標用戶的某個興趣愛好。同一社交圈內的用戶有著密切關系，不同社交圈內的用戶關聯較少?？梢愿鶕繕擞脩舻呐d趣，在社交圈基礎上進行推薦。在構建社交圈時，首先選擇初始化聚類中心，然后根據聚類中心對待推薦的用戶進行聚類，最后調整社交圈的結構。選擇聚類中心時遵循代表性（聚類中心連接較多的節(jié)點）和分散性（聚類中心之間的散度高）原則，并采用最大—最小距離方式[14]。初始化集群中心的選定過程如下：

K-Means聚類算法對初始聚類中心的選擇十分敏感，而且個別壞樣本將導致聚類效果極差。聚類得到的社交圈之間有一些共同的邊界節(jié)點，也即社交圈重疊。所以定義兩個社交圈重疊度為社交圈之間共同擁有的節(jié)點數量占總節(jié)點數量的百分比，如公式（6）所示：

3 好友推薦

在用戶微博文本相似度的基礎上，通過用戶在社交網中的距離衡量用戶之間相似度。每一個社交圈都代表目標用戶某方面的興趣愛好，社交圈的中心即是社交圈核心，社交圈聚類中心某一方面的愛好與目標用戶相同。因此，給目標用戶推薦好友時，應考慮該用戶與其所在社交圈中心用戶的距離。距離社交圈中心越近的用戶，則越有可能成為目標用戶的好友，使用公式（7）計算目標用戶對推薦用戶的偏好：

4 實驗與結果分析

4.1 實驗數據采集與預處理

選擇剛入駐微博平臺的新用戶作為目標用戶，使用新浪微博的API獲取這些用戶的微博文本。將每20條微博放入一個文檔中，使用中國科學院設計的ICTCLAS分割這些微博，并刪除所有停止詞。經過文本預處理后，在1 085位用戶中獲得了51 797個博主和9 376個連接。

4.2 評估

本文采用識別結果的準確率P（Precision）、召回率R（Recall）以及F值作為評價指標。F值越高，效果越好。具體計算方式如下[16]：

實驗一：評估本文推薦算法的準確度。實驗中將基于主題相似性的推薦算法作為對比算法，將本文提出的基于社交圈發(fā)現和信任度傳播的推薦算法與對照算法不同TOP-K推薦的Precision、Recall和F值進行對比。實驗結果如表1、圖1所示。

實驗結果表明，本文提出的基于社交圈發(fā)現和信任度傳播的推薦算法在Precision、Recall與F值上都比對比算法效果好，這是因為本文提出方法考慮到同一社交圈中的用戶更容易成為朋友，以及目標用戶信任度高的用戶更容易成為目標用戶的朋友。

實驗二：衡量用戶信任度對用戶推薦的影響。實驗目的是檢測微博用戶信任度對推薦精度的影響，利用提出的基于社交圈發(fā)現和信任度傳播的微博朋友推薦算法與基于主題相似性的推薦算法進行比較。由于兩種算法都考慮了社交圈的影響，因此排除了社交圈對推薦結果的影響。將用戶相似度作為評價標準，計算目標用戶與推薦用戶的相似度。用戶間相似度的求解采用公式（5），實驗結果如圖2所示。

從圖中可以看出，本文提出的基于主題分析和社交圈發(fā)現的微博朋友推薦算法在融合用戶信任度指標后，效果優(yōu)于不考慮用戶信任度的推薦算法，證明用戶信任度可以在一定程度上提高推薦精度。

5 結語

本文在微博好友推薦過程中考慮了社交圈和用戶信任度對推薦結果的影響，并將微博文本主題與用戶關系相結合。實驗結果表明，本文提出的基于社交圈發(fā)現與用戶信任度的微博朋友推薦算法能夠對微博用戶實現有效的朋友推薦。然而本文存在的問題是沒有考慮到微博文本主題演變過程中鏈接特征的作用，所以下一步工作是將該特征融入到推薦模型中。

參考文獻：

[1] JECKMANS A， TANG Q， HARTEL P.Poster：privacy-preserving profile similarity computation in online social networks[C]. Proceedings of the 18th ACM Conference on Computer and Communications Security， Chicago， Illinois， 2011：793-796.

[2] PIAO S， WHITTLE J.A feasibility study on extracting twitter users' interests using NLP tools for serendipitous connections[C].IEEE Third International Conference on Privacy， Security， Risk & Trust & IEEE Third Inernational Conference on Social Computing，2011：910-915.

[3] 胡文江，胡大偉，高永兵，等.基于關聯規(guī)則與標簽的好友推薦算法[J].計算機工程與科學，2013，35（2）：109-113.

[4] GUY I， ZWERDLING N， CARMEL D， et al.Personalized recommendation of social software items based on social relations[C]. Acm Conference on Recommender Systems ，2009：53-60.

[5] YIN D， HONG L， et al. Link formation analysis in Microblogs[C]. Proceedings of the 34th international ACM SIGIR Conference on Research and Development in Information Retrieval. ACM， 2011：1235-1236.

[6] DAVISON B D.StructuralLink analysis and prediction in Microblogs[C]. Proceedings of the 20th ACM Conference on Information and Knowledge Management， CIKM 2011， Glasgow， United Kingdom， 2011：1163-1168.

[7] ARMENTANO M G， GODOY D， AMANDI A.微博社區(qū)中基于拓撲的用戶推薦[J]. Journal of Computer Science & Technology， 2012，27（3）：624-634.

[8] 劉金龍，吳斌，陳震，等.基于領域劃分的微博用戶影響力分析[J].計算機科學，2015，42（5）：42-46.

[9] CHEN J， GEYER W， DUGAN C， et al. Make new friends， but keep the old： recommending people on social networking sites[C]. Proceedings of the SIGCHI Conference on Human Factors in Computing Systems，ACM， 2009：201-210.

[10] ROSEN ZVI M， GRIFFITHS T， STEYVERS M， et al. The author-topic model for authors and documents[C]. Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence. AUAI Press， 2004：487-494.

[11] HANNON J， BENNETT M， SMYTH B. Recommending twitter users to follow using content and collaborative filtering approaches[C]. Proceedings of the 2010 ACM Conference on Recommender Systems， Barcelona， Spain， 2010：199-206.

[12] 李傳揚.微博分析系統(tǒng)的設計與實現[D].北京：北京郵電大學，2015.

[13] 王立人，余正濤，王炎冰，等.基于有指導LDA用戶興趣模型的微博主題挖掘[J].山東大學學報：理學版，2015，50（9）：36-41.

[14] 周涓，熊忠陽，張玉芳，等.基于最大最小距離法的多中心聚類算法[J].計算機應用，2006，26（6）：1425-1427.

[15] 張中峰，李秋丹.社交網站中潛在好友推薦模型研究[J].情報學報，2011，30（12）：1319-1325.

[16] 林巍.段落檢索系統(tǒng)及其應用的研究[D].哈爾濱：哈爾濱工業(yè)大學，2010.

（責任編輯：黃 健）