一种社交网络下的好友推荐算法

1、中国科技论文在线一种社交网络下的好友推荐算法 张萌哲1，张成文2作者简介：张萌哲 女 硕士研究生，主要研究方向：社交网络和个性化推荐通信联系人：张成文，男，副教授，主要研究方向：云计算和个性化推荐. E-mail: zcwbuptSchool of computer science, Beijing University of Posts and Telecommunications, Beijing 100876;School of computer Beijing Key Laborary of Intelligent Telecommunications Softwar

2、e and Multimedia, Departmentof Computer, Beijing University of Posts and Telecommunications.北京邮电大学计算机学院 北京 100876;北京邮电大学计算机学院，北京市智能通信软件与多媒体重点实验室100876;10087613366036277;1860028128813366036277京邮电大学教三925;北京邮电大学教三mzzhang77;zcwbupt张萌哲 女 硕士研究生，主要研究方向：社交网络和个性化推荐;张成文，男，副教授，主要研究方向：云计算和个性化推荐.张萌哲

3、;张成文ZHANG Mengzhe;ZHANG Chengwen张成文1*|*期刊*|*Waleed Reafee, Naomie Salim. The Social Network Role in Improving Recommendation Performance of Collaborative FilteringJ. Lecture Notes in Electrical Engineering, 2014, 285:231-240.<CR>2*|*学位论文*|*Yin Z, Yu X, Zhang

4、 H. Commodity Recommendation Algorithm Based on Social NetworkM/ Advances in Computer Science and its Applications. Springer Berlin Heidelberg, 2014:27-33. <CR>3*|*论文集*|*Zhang Y, Lai G, Zhang M, et al. Explicit factor models for explainable recommendation based on phrase-level sentiment analys

5、isC/ International Conference on Research on Development in Information Retrieval. 2014.<CR>4*|*期刊*|*Jeong O R. SNS-based recommendation mechanisms for social mediaJ. Multimedia Tools & Applications, 2014, 74:2433-2447.<CR>5*|*期刊*|*Ronen I, Guy I, Kravi E, et al. Recommending social

6、media content to community ownersC/ Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval. ACM, 2014:243-252.<CR>6*|*期刊*|*Hasan M A, Zaki M J. A Survey of Link Prediction in Social NetworksJ. Social Network Data Analytics, 2011:243-27

7、5.<CR>7*|*专著*|* Symeonidis P, Perentis C. Link Prediction in Multi-modal Social NetworksM/ Machine Learning and Knowledge Discovery in Databases. Springer Berlin Heidelberg, 2014:147-162.<CR>8*|*专著*|*Zhang Y, Pang J. Distance and Friendship: A Distance-Based Model for Link Prediction in

8、Social NetworksM/ Web Technologies and Applications. Springer International Publishing, 2015:55-66.<CR>9*|*期刊*|*Chelmis C, Prasanna V K. Social Link Prediction in Online Social Tagging SystemsJ. Acm Transactions on Information Systems, 2013, 31(4):84-87.<CR>10*|*期刊*|*Schall D. Link predi

9、ction in directed social networksJ. Social Network Analysis & Mining, 2014, 4(1):1-14.<CR>11*|*期刊*|*Zhi-Ming X U, Dong L I, Liu T, et al. Measuring similarity between microblog users and its applicationJ. Chinese Journal of Computers, 2014, 37:207-218.<CR>12*|*期刊*|*陈克寒, 韩盼盼, 吴健. 基于用户

10、聚类的异构社交网络推荐算法J. 计算机学报, 2013, 36(2):349-359. <CR>13*|*期刊*|*Zhong L, Gao C, Zhang Z, et al. Identifying Influential Nodes in Complex Networks: A Multiple Attributes Fusion MethodM/ Active Media Technology. Springer International Publishing, 2014:11-22.<CR>14*|*期刊*|*Xiang R, Neville J, Roga

11、ti M. Modeling relationship strength in online social networks.J. Proc Www, 2010:981-990.<CR>15*|*论文集*|*Page, Lawrence, Brin, et al. The PageRank Citation Ranking: Bringing Order to the WebC/ Stanford InfoLab. 1999:1-14.<CR>16*|*期刊*|*Arasu A, Cho J, Garcia-Molina H, et al. Searching the

12、WebJ. Acm Transactions on Internet Technology, 2002, 1(2):2-43.|1|张萌哲|ZHANG Mengzhe|北京邮电大学计算机学院 北京 100876|School of computer science, Beijing University of Posts and Telecommunications, Beijing 100876|张萌哲 女 硕士研究生，主要研究方向：社交网络和个性化推荐|北京邮电大学教三925|100876|mzzhang7713366036277<CR>*|2|张成文

13、|ZHANG Chengwen|北京邮电大学计算机学院，北京市智能通信软件与多媒体重点实验室|School of computer Beijing Key Laborary of Intelligent Telecommunications Software and Multimedia, Departmentof Computer, Beijing University of Posts and Telecommunications.|张成文，男，副教授，主要研究方向：云计算和个性化推荐.|北京邮电大学教三|100876|zcwbupt18600281288一种社交

14、网络下的好友推荐算法|A New Link Prediction Algorithm Based on Social Network|- 8 -（1. 北京邮电大学计算机学院 北京 100876；2. 北京邮电大学计算机学院，北京市智能通信软件与多媒体重点实验室）摘要：基于社交关系的社交网络下的好友推荐算法的利用用户之间的共同好友或粉丝的重合度来计算用户相似性，忽略了用户与的现有好友中的个体之间的亲密程度。为了解决这个问题，本文利用了用户与已建立关注关系的用户的交互信息，计算用户与已有好友的亲密度，提出了一种基于PageRank的好友推荐算法，在推荐过程中融合了用户的交互信息和社交信息。并使用

15、腾讯微博的数据进行验证，结果表明，结合了用户交互信息的推荐算法要比只考虑社交关系的好友推荐算法有更高的召回率和准确率。关键词：社交网络；好友推荐；交互信息；随机游走中图分类号：TP391A New Link Prediction Algorithm Based on Social NetworkZHANG Mengzhe1, ZHANG Chengwen2(1. School of computer science, Beijing University of Posts and Telecommunications, Beijing 100876;2. School of computer

16、Beijing Key Laborary of Intelligent Telecommunications Software and Multimedia, Departmentof Computer, Beijing University of Posts and Telecommunications.)Abstract: The traditional social network friends recommendation algorithm based on relation information evaluates user similarity by the number o

17、f the common followers and followees between the two users, ignoring the closeness between the individuals of the followees and the user. To solve this problem , this paper focus on the users interaction information to compute the intimacy of the individuals and the user, and a new link prediction a

18、lgorithm based on PageRank is proposed, which integrates the interaction information and relation information. The experiments are performed on the Tencent microblog data, and the results show that the algorithm combines of the two kinds of information can achieve the higher recall rate and precisio

19、n rate.Key words: Social Network; Link Prediction; Interaction Information; Random Walk0 引言社交网络即社交网络服务,源自英文SNS(Social Network Service)的翻译,中文直译为社会性网络服务或社会化网络服务,意译为社交网络服务。以SNS模式为核心的社交网站“以人为本”,充分挖掘人的知识、信息和关系,能够更好地为用户提供自由与关系化服务,增强网站信息的数量、质量和用户粘性。在这种背景下,基于社交网络的个性化推荐通过融合用户在社会化网络中留下的个人信息,操作行为,浏览痕迹等数据进行信息推荐

20、,推荐的对象除了商品外,还可以是文档、朋友、广告和群组等。它已成为传统个性化推荐方法的补充或替代手段,基于社交网络的个性化推荐1,2,3,4,5已成为个性化推荐研究领域较为活跃的领域之一。社交网络的核心是人,组成社交网络的是人与人之间的联系。关注的人群是用户获取信息的主要来源,根据用户现有的好友、用户的行为记录给用户推荐新的好友,可以增加整个社交网络的稠密程度和社交网站用户的活跃度。所以好友推荐一直都是社交网络个性化推荐的重要课题6,7,8,9,10。Xu等人11在研究基于各种用户属性信息（背景信息、微博文本、社交信息）的用户相似度计算方法时发现,基于社交信息的用户相似度取得了最好的推荐效果。

21、基于社交信息的好友推荐是通过用户间的共同好友数和粉丝数来衡量用户之间的相似度,是Friend-of-friend算法12的进一步深化,这种方法简单有效,但是只考虑共同的好友数量,有一定的局限性,他忽略了已经与用户建立关系的不同个体对用户的不同意义,研究13,14表明交互更加频繁的用户之间通常具有更高的影响强度。针对这个问题，本文首先利用用户的交互信息计算用户之间的亲密度，基于PageRank算法随机游走的思想，提出了一个个性化的好友推荐算法，使算法可以融合用户的社交信息和交互信息，并通过实验对该算法与只考虑社交信息的好推荐算法进行比较和分析。1 随机游走的好友推荐算法的理论基础1.1 Page

22、Rank算法PageRank15是由谷歌创始人拉里佩奇和谢尔盖布林提出的一种链接分析算法,以使那些重要的网页在搜索结果中获得排名的提升,最终提高搜索结果的关联性和网页质量。PageRank算法的原理基于“随机行走模型”(Random Walk Model),随机行走模型有一个显著的特点,那就是每一次迭代的结果只与前一次有关,与更早的结果完全无关。这种过程又被称为马尔可夫过程(Markov Process)或马尔可夫链(Markov Chain)。算法中节点网页的重要性是由链接到该网页的页面数量与质量共同决定的，表示每个网页重要性的值称为PR值。其排序方法体现出了网络中丰富的拓扑特性，适用于社会

23、网络分析。PageRank算法的核心思想有两点：1) 如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是PR值会相对较高；2) 如果一个PR值很高的网页链接到一个其他的网页，那么被链接到的网页的PR值会相应地因此而提高。PageRank算法认为每个网页的PR值都被均匀的分配到它指向的网页，以此迭代，最终网络中的每个页面的PR值达到稳定、收敛状态。每个页面的PR值的计算公式如下： (1)其中，PR(v)是网页v的PR值；u是指向网页v的网页，U(v)是链接到网页v的网页集合；N(u)是网页u里的所有链接数；在PageRank算法的真正实现中，还会增加一个常系数c。所有的网页节点的P

24、R值分配向量在计算的时候是组合在一起的，这时得到了一个转移矩阵A。A是一个表示每一次点击链接概率的矩阵。A的第i列第j行Aij的含义是，如果当前访问的网页是网页i，那么下一次点击链接跳转到网页j的概率为Aij。这样设计矩阵A的好处是，通过矩阵A和向量Rn-1相乘，即可得出点击一次链接后每个网页可能的停留概率向量Rn。Rn就是第n次点击时每个网页节点的PR值。由上面描述的迭代过程可以得到： (2)对于如上幂运算得到的结果与初始值无关，是因为最终都会收敛到某个值。因此使用幂法之前，要确保能够收敛。但是，在互联网的超链接结构中，一旦出现封闭的情况，就会使得幂法不能收敛。所谓的封闭是指若干个网页互相指

25、向对方，但不指向别的网页。这种只有链入链接没有链出链接的网页，就会像一个“黑洞”一样，将同一个连通子图中其它网页流向它的PR值慢慢“吞掉”，这种网页我们称之为“悬挂网页”（Dangling Link）。为了解决这个问题，PageRank算法加入了一个新的向量E。它的作用是，按照其中所描述的比例来向全部网页分配悬挂网页每一次“吞掉”的PR值。这样，相当于为悬挂网页添加了链向网络上全部网页的链接，避免了悬挂链接的出现。向量E的取值一般直接使用平均分配的方式把悬挂网页的PageRank分配给所有网页，即得到如下表达式16： (3)其中，pi是被研究的页面，M(pi)是pi链入页面的集合，L(pj)是

26、pj链出页面的数量，而N是所有页面的数量，q为阻尼系数，表示用户在浏览某个页面之后以q概率继续浏览该页面中的某个链出的页面。1.2 用户交互信息分析微博采用“关注”机制建立用户之间的关系。“关注”的含义是如果一个用户对另外一个用户感兴趣，他可以关注这个用户而不用经过这个用户的允许。微博的用户每天会被推送他所关注的人产生的信息，用户在浏览信息流的过程会产生大量的交互信息，如转发，评论，点赞等等。用户与不同关注用户产生的交互信息的数量是不同的，交互越频繁的用户之间表明他们的亲密度越高。本文用用户的交互信息来度量用户之间的亲密度，用户的交互信息表示为Interaction(u) = Retweet

27、(u) ,Comment(u)具体方法是：将用户的关注列表里的用户编号0,1, 2, , n，Retweet (u)的第i个分量表示用户u转发用户i的微博次数；Comment(u)的第i个分量表示用户u评论用户i的微博次数。对于用户u, 用户i同他的亲密度表示为： (4)其中retweet_count为对关注列表里用户微博的转发总次数，comment_count为对用户列表里的用户评论总次数，wi是转发行为和评论行为的权值，w1 + w2 = 1。1.3 用户社交信息的分析用户社交信息是指用户的社交关系，包括用户关注列表和粉丝列表。对于两个用户（u, v），他们的社交信息分别表示为Relati

28、on(u) = Friend(u), Follower(u),Relatzon(v) = Friend(v), Follower(v)因此(u,v)之间的社交信息相似度的计算问题可以分解为两种属性信息（关注信息、粉丝信息）的相似度计算问题本文先采用了余弦相似度方法来计算(u,v)之间的两种属性信息相似度,(u,v)的关注信息相似度、粉丝信息相似度的计算公式分别为:(5)(6)上述为微博用户的关注信息相似度、粉丝信息相似度，将它们加权融合，得到用户之间的社交信息相似度： (7)wi是关注信息相似度、粉丝信息相似度的权值，w1 + w2 = 1。2 融合交互信息和社交信息的好友推荐算法PageRa

29、nk算法用于网页排名计算，在一个全局的网页里得到的结果是唯一的，这是因为在一个网页给链出网页分配PR值的时候是平均分配的，而对悬挂网页的PR值分配也是平均分配的，全局共有同一个转移矩阵和悬挂网页分配向量E。因为转移矩阵的中的概率转移是产生在一个网页的链出网页之间的，这种关系映射到社交网络上，网页之于其链出网页就是用户之于其关注用户，而每个被关注用户对于用户的差异性可以用PR值分配的差异来体现，因此根据用户与已关注用户之间的亲密度重新分配转移概率，得到跟用户交互频率相关的新转移矩阵A。对于新的转移矩阵A，有： (8)其中是用户i与用户j的亲密度，k是用户i关注的用户数量。解决了转移概率的分配问题

30、，依然不能解决排名结果唯一的问题，这是因为A是全局唯一的。要解决这个问题，就要为每一个用户定义一个不同的悬挂网页分配向量E，这里我们简称为悬挂向量E。那么悬挂向量E的分配在好友推荐中是与用户相似性相关的，这是因为PageRank中的悬挂向量E是分配给全部网页节点的，而用户相似性也是与一个网络中的全部用户做比较，他们同属与一种数学模型。因此，根据用户之间相似性的不同重新分配得到相似性向量E，对于E中元素ej，有： (9)其中，表示用户j同用户i的相似度，N为网络中用户节点的个数。综上所述，融合了交互信息和社交信息的好友推荐算法User-Link PageRank的PR值的表达式为： (10)其中

31、，pi是待研究的用户节点，u是推荐结果的目标用户，M(pi)是pi链入用户的集合，而N是所有用户的数量，q表示用户浏览该用户关注列表里用户的概率。融合交互信息和社交信息的好友推荐算法的具体流程为：1) 生成用户的社交信息数据库DR和交互信息数据库DI；2) 根据交互信息计算用户与关注列表中用户的亲密度Iij；3) 根据Iij计算每个用户的分配概率向量I，得到全局的转移矩阵A；4) 计算用户之间的相似性Sij，得到每个用户的相似向量E；5) 利用User-Link PageRank算法计算用户的PR值；6) 向目标用户U推荐PR值最高用户集的Utop-N。3 实验我们称只利用用户社交信息计算用户

32、相似性的好友推荐算法为ULS (User-Link Similarity)。为了对于ULS与ULPageRank (User-Link PageRank)算法的性能，我们选取了2012届KDD Cup比赛使用的腾讯微博的数据，该数据包含了算法所需的用户的社交信息和交互信息。为了使得用户关注列表里的用户数据尽可能完整，本文选择一组微博用户ID1,ID2,IDn作为种子节点，放入待爬行的节点队列Q，最终选用了732 650个用户的数据作为实验集，并选用好友推荐算法对比中两个最常用的评估指标，召回率(Recall Rate)和准确率(Precision Rate)对推荐结果进行评测。令已经具有关注关

33、系的关注列表中的用户作为实际采纳的用户集合，算法计算的top-N用户为算法推荐的用户集合，则召回率和准确率的定义为： (11) (12)在比较ULS和ULPageRank算法之前，先针对User-Link PageRank算法中q的取值进行比较，根据算法的介绍，q值的大小决定了用户社交信息和交互信息在算法中的比重，q越大，交互信息比重越大；反之，社交信息比重越大。分别取q = 0.6，0.5，0.4，0.3，0.2进行比较，对不同的推荐好友数量进行对比，取top-N = top-10，top-20，top-30，top-40，top-50。测试结果如图所示： (a) Recall Rate(b

34、) Precision Rate图1 算法对比，当q in 0.6,0.5,0.4,0.3,0.2Fig. 1 Comparison of algorithms when q = 0.6,0.5,0.4,0.3,0.2对图1中结果分析可见，在进行微博这种以兴趣关注为主导的社交网络下的好友推荐，社交信息对推荐结果的影响要高于交互信息，当q取得0.3时，推荐结果的准确率和召回率都要明显高于q的其他取值。因此，针对不同的推荐好友数量，取top-N = top-10，top-20，top-30，top-40，top-50，在q = 0.3时，对ULS和ULPageRank进行对比，测试结果如下： (a

35、) Recall Rate(b) Precision Rate图1 算法对比，当top-N in 10,20,30,40,50Fig. 1 Comparison of algorithms when top-N = 10,20,30,40,50通过图2的结果显示，在召回率和准确率评测标准上，考虑了社交信息和交互信息的ULPageRank算法的结果明显要优于只考虑了社交信息的ULS算法，这是因为ULPageRank在通过共同关注和粉丝的数量上，同时考虑了这两个集合中个体对用户的影响，就如现实生活中交友过程一样，我们不仅可能结交同一个社交圈中的好友，同时交互越频繁的朋友的引荐对我们的决策的影响越大

36、。而且基于PageRank算法的思想，这种影响不断地迭代，收敛，相比ULS只计算一次相似性得到的结果更加稳定和准确。因此在好友推荐中不仅要考虑用户间的相似性，还有考虑用户间的亲密度。4 结论基于社交网络的个性化推荐业务已经扩散到互联网的各个领域，社交网络下的好友推荐可以增加整个社交网络的稠密程度，提高社交网站用户的活跃度。简单有效的基于社交信息的好友推荐只考虑了共同关注和粉丝的数量，有一定的局限性。本文通过用户的交互信息计算用户间的亲密度，并以著名的网页排名算法PageRank为模型，融合了用户社交信息和交互信息，在好友推荐过程中同时考虑了用户的共同好友数量和不同个体对用户的意义，得到了一种全

37、新的好友推荐算法User-Link PageRank算法。并经过腾讯微博的数据验证，本文提出的User-Link PageRank算法要比只考虑社交信息的推荐算法具有更高的召回率和准确率。接下来会从个体的活跃度方向进一步研究个体在好友推荐中的影响和意义。参考文献 (References)1 Waleed Reafee, Naomie Salim. The Social Network Role in Improving Recommendation Performance of Collaborative FilteringJ. Lecture Notes in Electrical Engi

38、neering, 2014, 285:231-240.2 Yin Z, Yu X, Zhang H. Commodity Recommendation Algorithm Based on Social NetworkM/ Advances in Computer Science and its Applications. Springer Berlin Heidelberg, 2014:27-33. 3 Zhang Y, Lai G, Zhang M, et al. Explicit factor models for explainable recommendation based on

39、phrase-level sentiment analysisC/ International Conference on Research on Development in Information Retrieval. 2014.4 Jeong O R. SNS-based recommendation mechanisms for social mediaJ. Multimedia Tools & Applications, 2014, 74:2433-2447.5 Ronen I, Guy I, Kravi E, et al. Recommending social media

40、 content to community ownersC/ Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval. ACM, 2014:243-252.6 Hasan M A, Zaki M J. A Survey of Link Prediction in Social NetworksJ. Social Network Data Analytics, 2011:243-275.7 Symeonidis P, Perentis C. Link Prediction in Multi-