基于社交圈发现与用户信任度传播的微博朋友推荐方法

朱明玮 唐莫鸣

摘 要：微博的普及导致微博平台数据量日益增长，因此从海量微博中快速准确地为微博用户推荐好友成为了巨大挑战。用户的社交网络和微博文本在一定程度上体现了用户的价值观和兴趣爱好，有相似兴趣的微博用户更有可能成为朋友。基于上述事实，以用户微博文本相似度为似然函数，使用K-means聚类对微博用户聚类，得到微博用户社交圈；在社交圈内部迭代计算用户之间的相似度，同时计算用户对其所在社交圈中其余用户的信任度；最后，根据用户之间的相似度和信任度完成微博好友推荐。实验结果表明，该算法优于传统的基于社交网络拓扑图的好友推荐方法。

关键词：社交圈；信任度；朋友推荐；微博

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 引言

新浪微博逐漸成为人们获得资讯和传播信息的主要媒介之一。随着新浪微博的普及，微博用户数量呈井喷式增长。据统计，2012-2016年间微博用户数量增长了335%，因此从海量用户中快速准确地为微博用户推荐好友成为巨大挑战。当前针对社交网络好友推荐有两个主要研究方向：基于用户兴趣的主题推荐，以及基于社交网络拓扑结构的推荐。第一个方向通过分析用户在社交平台上的行为（发送的博文、点赞、转发、评论）提取用户兴趣爱好，获得高相似度的用户群，在此基础上推荐好友给目标用户。基于用户特征的推荐领域通常划分成以下3种：基于内容、基于共同兴趣、基于标签的推荐。Jeckmans A[1]通过用户博文的文本相似度进行好友推荐；Piao S等[2]利用LDA模型挖掘用户Tweet内容的主题词及主题在主题词上的概率分布，找出用户兴趣倾向的主题，推荐关注相似主题的用户；胡闻江等[3]综合考虑了关联规则和用户之间的标签相似度，利用标签中蕴含的语义信息，向目标用户推荐好友；Guy等[4]搭建Lotus社交网络进行实验，最后得出结论：基于社交网络拓扑图的好友推荐算法比基于用户特征相似度的好友推荐算法效果更好；Yin等[5]对Tweet中怎样形成用户关注关系作了充分研究。最终实验结果证明：目标用户关注关系中超过90%是通过已有好友建立的。基于用户间拓扑关系的好友推荐算法使用基于社交圈的算法为用户推荐好友。Davison等[6]提出一种预测链接的方法，该方法主要基于用户网络拓扑关系的相似性，推测Twitter用户可能关注的好友。有些学者通过用户关注列表以及关注该用户的用户，计算微博用户相似度，从而进行推荐[7-8]。Chen等[9]得出结论：基于社交网络用户间关注关系以及链接分析的好友推荐对于彼此熟悉以及同属一个社交圈的用户推荐有着很强的指导意义。一些专家学者考虑了融合基于用户内容相似性和基于社交网络拓扑结构及链接分析的好友推荐方法。例如，Rosen等[10]构建了Author-Topic模型，对用户的潜在主题进行挖掘，并对用户主题倾向性分布进行统计分析，但该模型没有提出清晰的用户社交圈概念。还有一些学者将用户的微博文本、用户关注列表中的微博以及关注该用户的用户微博文本结合起来构建模型，并使用TF-IDF挖掘微博关键词，找到微博用户的兴趣爱好，通过融合社交网络的拓扑结构和微博文本的协同过滤算法进行推荐[11-12]。用户的社交网络拓扑结构很大程度上反映了用户交友倾向，彼此信任度越高的用户越有可能成为朋友，而现有方法未充分利用这些因素。因此，本文利用微博用户相似度和信任度进行微博好友推荐。

1 用户相似度计算

如果两个用户发布的微博文本相似，则说明这两个用户可能拥有相同的兴趣爱好和相似的价值取向，因而有共同话题，彼此更容易成为朋友。因此，微博用户发布的微博文本相似性是进行微博好友推荐的基础。由于微博文本是短文本，使用文本主题可以很好地表征短文本，因此本文使用微博文本主题表征微博文本。通过香农提出的“相对熵”计算两微博文本主题词的词频分布，以衡量微博文本相似度。新浪微博用户的关注焦点和关注兴趣会随着时间推移而发生变化，所以在计算文本主题时考虑时间因素可以获得更具时效性的结果。计算微博文本主题的步骤如下：首先，将微博文本按发布时间不同进行划分，得到不同时间片的微博文本集合；然后通过LDA挖掘每个时间片文本集合的“T”个文本主题；再通过增量Gibbs算法计算该时间片内微博文本主题在主题词上的概率分布，其中W=V-tW-uV-t-1，V-t表示时间片t内文本集合中的單词总数，W-u为用户自定义权重，最终得到动态LDA模型[13]。具体算法如下：

2 社交圈发现

人以群分，有着相同兴趣爱好的人，彼此之间更容易成为朋友。本文将候选用户进行聚类，从而得到目标用户的社交圈。由于本文推荐范围来自目标用户的社交网络，目标用户出于兴趣爱好而关注某些用户，因此聚类出的每一个社交圈都代表目标用户的某个兴趣爱好。同一社交圈内的用户有着密切关系，不同社交圈内的用户关联较少。可以根据目标用户的兴趣，在社交圈基础上进行推荐。在构建社交圈时，首先选择初始化聚类中心，然后根据聚类中心对待推荐的用户进行聚类，最后调整社交圈的结构。选择聚类中心时遵循代表性（聚类中心连接较多的节点）和分散性（聚类中心之间的散度高）原则，并采用最大—最小距离方式[14]。初始化集群中心的选定过程如下：

K-Means聚类算法对初始聚类中心的选择十分敏感，而且个别坏样本将导致聚类效果极差。聚类得到的社交圈之间有一些共同的边界节点，也即社交圈重叠。所以定义两个社交圈重叠度为社交圈之间共同拥有的节点数量占总节点数量的百分比，如公式（6）所示：

3 好友推荐

在用户微博文本相似度的基础上，通过用户在社交网中的距离衡量用户之间相似度。每一个社交圈都代表目标用户某方面的兴趣爱好，社交圈的中心即是社交圈核心，社交圈聚类中心某一方面的爱好与目标用户相同。因此，给目标用户推荐好友时，应考虑该用户与其所在社交圈中心用户的距离。距离社交圈中心越近的用户，则越有可能成为目标用户的好友，使用公式（7）计算目标用户对推荐用户的偏好：

4 实验与结果分析

4.1 实验数据采集与预处理

选择刚入驻微博平台的新用户作为目标用户，使用新浪微博的API获取这些用户的微博文本。将每20条微博放入一个文档中，使用中国科学院设计的ICTCLAS分割这些微博，并删除所有停止词。经过文本预处理后，在1 085位用户中获得了51 797个博主和9 376个连接。

4.2 评估

本文采用识别结果的准确率P（Precision）、召回率R（Recall）以及F值作为评价指标。F值越高，效果越好。具体计算方式如下[16]：

实验一：评估本文推荐算法的准确度。实验中将基于主题相似性的推荐算法作为对比算法，将本文提出的基于社交圈发现和信任度传播的推荐算法与对照算法不同TOP-K推荐的Precision、Recall和F值进行对比。实验结果如表1、图1所示。

实验结果表明，本文提出的基于社交圈发现和信任度传播的推荐算法在Precision、Recall与F值上都比对比算法效果好，这是因为本文提出方法考虑到同一社交圈中的用户更容易成为朋友，以及目标用户信任度高的用户更容易成为目标用户的朋友。

实验二：衡量用户信任度对用户推荐的影响。实验目的是检测微博用户信任度对推荐精度的影响，利用提出的基于社交圈发现和信任度传播的微博朋友推荐算法与基于主题相似性的推荐算法进行比较。由于两种算法都考虑了社交圈的影响，因此排除了社交圈对推荐结果的影响。将用户相似度作为评价标准，计算目标用户与推荐用户的相似度。用户间相似度的求解采用公式（5），实验结果如图2所示。

从图中可以看出，本文提出的基于主题分析和社交圈发现的微博朋友推荐算法在融合用户信任度指标后，效果优于不考虑用户信任度的推荐算法，证明用户信任度可以在一定程度上提高推荐精度。

5 结语

本文在微博好友推荐过程中考虑了社交圈和用户信任度对推荐结果的影响，并将微博文本主题与用户关系相结合。实验结果表明，本文提出的基于社交圈发现与用户信任度的微博朋友推荐算法能够对微博用户实现有效的朋友推荐。然而本文存在的问题是没有考虑到微博文本主题演变过程中链接特征的作用，所以下一步工作是将该特征融入到推荐模型中。

参考文献：

[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] 胡文江，胡大伟，高永兵，等.基于关联规则与标签的好友推荐算法[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.微博社区中基于拓扑的用户推荐[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] 李傳扬.微博分析系统的设计与实现[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] 林巍.段落检索系统及其应用的研究[D].哈尔滨：哈尔滨工业大学，2010.

（责任编辑：黄 健）