朱明瑋 唐莫鳴

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

關(guān)鍵詞：社交圈；信任度；朋友推薦；微博

DOI：10.11907/rjdk.173069

中圖分類號(hào)：TP301

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

1 用戶相似度計(jì)算

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

2 社交圈發(fā)現(xiàn)

人以群分，有著相同興趣愛好的人，彼此之間更容易成為朋友。本文將候選用戶進(jìn)行聚類，從而得到目標(biāo)用戶的社交圈。由于本文推薦范圍來(lái)自目標(biāo)用戶的社交網(wǎng)絡(luò)，目標(biāo)用戶出于興趣愛好而關(guān)注某些用戶，因此聚類出的每一個(gè)社交圈都代表目標(biāo)用戶的某個(gè)興趣愛好。同一社交圈內(nèi)的用戶有著密切關(guān)系，不同社交圈內(nèi)的用戶關(guān)聯(lián)較少。可以根據(jù)目標(biāo)用戶的興趣，在社交圈基礎(chǔ)上進(jìn)行推薦。在構(gòu)建社交圈時(shí)，首先選擇初始化聚類中心，然后根據(jù)聚類中心對(duì)待推薦的用戶進(jìn)行聚類，最后調(diào)整社交圈的結(jié)構(gòu)。選擇聚類中心時(shí)遵循代表性（聚類中心連接較多的節(jié)點(diǎn)）和分散性（聚類中心之間的散度高）原則，并采用最大—最小距離方式[14]。初始化集群中心的選定過(guò)程如下：

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

3 好友推薦

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

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

4.1 實(shí)驗(yàn)數(shù)據(jù)采集與預(yù)處理

選擇剛?cè)腭v微博平臺(tái)的新用戶作為目標(biāo)用戶，使用新浪微博的API獲取這些用戶的微博文本。將每20條微博放入一個(gè)文檔中，使用中國(guó)科學(xué)院設(shè)計(jì)的ICTCLAS分割這些微博，并刪除所有停止詞。經(jīng)過(guò)文本預(yù)處理后，在1 085位用戶中獲得了51 797個(gè)博主和9 376個(gè)連接。

4.2 評(píng)估

本文采用識(shí)別結(jié)果的準(zhǔn)確率P（Precision）、召回率R（Recall）以及F值作為評(píng)價(jià)指標(biāo)。F值越高，效果越好。具體計(jì)算方式如下[16]：

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

實(shí)驗(yàn)結(jié)果表明，本文提出的基于社交圈發(fā)現(xiàn)和信任度傳播的推薦算法在Precision、Recall與F值上都比對(duì)比算法效果好，這是因?yàn)楸疚奶岢龇椒紤]到同一社交圈中的用戶更容易成為朋友，以及目標(biāo)用戶信任度高的用戶更容易成為目標(biāo)用戶的朋友。

實(shí)驗(yàn)二：衡量用戶信任度對(duì)用戶推薦的影響。實(shí)驗(yàn)?zāi)康氖菣z測(cè)微博用戶信任度對(duì)推薦精度的影響，利用提出的基于社交圈發(fā)現(xiàn)和信任度傳播的微博朋友推薦算法與基于主題相似性的推薦算法進(jìn)行比較。由于兩種算法都考慮了社交圈的影響，因此排除了社交圈對(duì)推薦結(jié)果的影響。將用戶相似度作為評(píng)價(jià)標(biāo)準(zhǔn)，計(jì)算目標(biāo)用戶與推薦用戶的相似度。用戶間相似度的求解采用公式（5），實(shí)驗(yàn)結(jié)果如圖2所示。

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

5 結(jié)語(yǔ)

本文在微博好友推薦過(guò)程中考慮了社交圈和用戶信任度對(duì)推薦結(jié)果的影響，并將微博文本主題與用戶關(guān)系相結(jié)合。實(shí)驗(yàn)結(jié)果表明，本文提出的基于社交圈發(fā)現(xiàn)與用戶信任度的微博朋友推薦算法能夠?qū)ξ⒉┯脩魧?shí)現(xiàn)有效的朋友推薦。然而本文存在的問(wèn)題是沒有考慮到微博文本主題演變過(guò)程中鏈接特征的作用，所以下一步工作是將該特征融入到推薦模型中。

參考文獻(xiàn)：

[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ān)聯(lián)規(guī)則與標(biāo)簽的好友推薦算法[J].計(jì)算機(jī)工程與科學(xué)，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ū)中基于拓?fù)涞挠脩敉扑][J]. Journal of Computer Science & Technology， 2012，27（3）：624-634.

[8] 劉金龍，吳斌，陳震，等.基于領(lǐng)域劃分的微博用戶影響力分析[J].計(jì)算機(jī)科學(xué)，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] 李傳揚(yáng).微博分析系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].北京：北京郵電大學(xué)，2015.

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

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

[15] 張中峰，李秋丹.社交網(wǎng)站中潛在好友推薦模型研究[J].情報(bào)學(xué)報(bào)，2011，30（12）：1319-1325.

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

（責(zé)任編輯：黃 ?。?/p>