- 1 -
基于图衰减的社交网络推荐算法
赵威，徐鹏**
（北京邮电大学网络技术研究院）
5 摘要：本文面向当今时代非常流行的社交网络应用，提出了针对推荐系统面对数据的稀疏性
而无法正常向用户进行推荐的问题没提出了一个有效的解决方案。通过调研个大面向社交网
络的应用，总结用户与用户直接的特殊关系，最后确定了社交网络中的推荐系统与其他 web
应用推荐系统相比的特殊性。根据调研提出了基于图衰减的推荐算法，来解决用户推荐问题。
通过研究与测试表明，该解决方案可以在很大程度上解决数据稀疏性问题。 10
关键词：推荐系统；社交网络；数据稀疏性；图衰减
中图分类号：TP311
Graph Attenuation Based Social Network Recommendation
ZHAO Wei, XU Peng 15
(Beijing University of Posts and Telecommunications)
Abstract: In this pape, it proposes a an effective solution for the modern era very popular social
networking applications can not normally recommend to the user when encounter with data
sparsity. Through major research-oriented social networking applications, summarize the special
relationship between users of the social network to finalize the recommendation system and other 20
web applications compared to the particularity of the recommendation system. According to
research presented depth map based search method to solve the problem of user recommendations.
Through research and testing showed that the solution can solve the data sparseness problem.
Key words: recommend system;social network;spare data;graph attenuation
0 引言 25
随着互联网的发展， 时期的到来，人类正式进入了信息爆炸与网络社交时代。
海量的信息与人们可以接受的信息量不成正比，导致了人们难以发现自己有效信息与大量信
息无法被人们发现的悖论的出现。推荐系统的出现在根本上解决了用户无法发现兴趣与大量
信息不被人阅读就被掩盖的问题。在当今，推荐系统大多是采用的协同过滤推荐算法[1]，通
过分析用户过去的行为记录，计算得出和用户兴趣比较相似的邻居，通过分析和其相似的邻30
居的曾经看过的内容来推荐给用户可能感兴趣的内容。但是，协同过滤推荐算法在一些场景
也会有一定的缺陷，因为协同过滤算法需要分析用户的行为数据，当一个新用户没有行为数
据的时候，推荐系统的工作效率与推荐结果则会出现异常[2]。本文就针对在社交网络中，利
用改进的协同过滤推荐算法来解决用户冷启动与数据稀疏性问题。
1 传统的协同过滤算法介绍 35
推荐系统是根据用户的以往行为记录，通过分析计算用户的行为数据，发现和挖掘用户
的兴趣偏好或者在电子商务中的购买趋向，向网络用户进行有个性化的推荐信息和物品。在
推荐系统中比较流行的算法是使用协同过滤推荐算法。协同过滤推荐算法主要包括
User-Based、Item-Based 与 Model-Based 等推荐算法。算法主要思想是通过对用户过去的行
为进行抽象与计算，寻找最相似的邻居，根据最近邻居的浏览记录对用户进行推荐。 40
算法的实现过程一般分为三步：
- 2 -
1. 日志处理：通过对用户的行为日志进行去重、归一化和属性的抽取，获取能反映用
户兴趣偏好的有效数据。对有这些效数据进行数学处理与与建模，抽象出用户模型。
这一步的处理结果一般是一个 M*N 的矩阵。
2. 相似邻居计算：这一步是推荐算法的核心，代表了算法的优劣和最终推荐效果是否45
能满足需求。输入是一个向量矩阵，每一个向量就代表了一个用户或者物品。我们
通过计算不同用户或者物品之间的相似度，来决定不同用户或者物品之间是否相
似。我们可以利用余弦值来计算两个用户向量之间的相似度，当计算出两两向量之
间的余弦相似度，一般是采用按照所有用户中相似度进行排序而不是随机抽取，这
时候效果最好。 50
3. 生成推荐结果。根据已经生成的最近邻居来对当前用户对某个物品的兴趣偏好进行
预估计。
2 基于社交关系的应用分析
随着互联网的发展，丰富多彩的互联网应用出现，给我们的网络用户提供了多种多样的
网络服务和工作上的支持。在各种互联网应用中，基于社交网络的应用的出现是具有非常重55
要的意义，这标志着人类实际生活中最重要的一个组成部分社交圈子也开始变得互联网化。
在社交化应用中，最大的应用特色就是社交圈子的界定和组建。
在基于社交的互联网应用中，随着网络用户的呈现出高速发展的趋势，不仅社交网络中
的用户数量呈现出爆炸性地增长，而且基于社交网络的服务形态也在发生了各种各样的变化
和升级。一般会分为基于强弱关系和面向圈子的不同的社会应用。强关系应用指的是用户双60
方必须相互关注而弱关系应用则是参与双方可以一方进行关注，基于圈子的应用一般是一在
一个闭环的范围内，用户共处在一个圈子内进行用户交流和信息共享。
如基于弱关系的国内微博服务，还有基于强关系的人人网和 QQ 等。除此之外，基于圈
子的社交应用也变得越来越多，比如 Google+还有朋友圈，这些应用中一个显明的特点就是
用户可以拥有并维护自己的社交或者兴趣圈子，可以构建自己的圈子，邀请有相同爱好的人65
进入某个圈子。对于这些强关系的应用中，推荐是比较容易进行的[3]。
虽然互联网上社交网络的发展已经让网络用户普遍参与进去，但是互联网中的社交网络
呈现出一种无尺度网络的特点，极少量的用户拥有较多的关系连接，而大量的用户仅具有少
量的关系连接。这就导致了用户与其他用户之间的交集比较少，在单纯通过用户过去的行为
记录进行推荐，数据的稀疏性问题就会突显出来。除此之外，社交网络中还会有新的用户在70
不断加入，新用户不能快速与其他用户建立社交圈子与人际关系网络，这就加重了用户之间
的数据稀疏性，导致推荐的准确率下降。
3 基于图衰减的推荐算法
算法介绍
社交化应用中，推荐算法和普通电子商务或者电影网站中不同的是，在对用户进行结果75
推荐的时候需要考虑用户的社交圈子与真实世界中的人家关系。根据六度空间理论可以得
出，世界上任何两个人都可以通过六个人的交互建立人际关系，在一定程度上发展出共同的
兴趣爱好。通过最新的 Facebook[4]研究发现，现在的社交网络已经可以通过不超过 5 个中间
人就可以对任意两个人建立人际关系。此理论也说明了，通过研究与用户 A 没有直接关系
的用户，可以在一定程度上对研究用户 A 的行为习惯起到促进作用[5]。 80
根据此理论的调研与研究[6][7]，提出了基于人际关系图衰减的广度搜索和协同过滤相结
合的推荐算法。对用户 U 的关系网络图，获取用户 U 的直接邻节点集合 SR(u)，并以 SR(u)
- 3 -
中的节点为初始节点对图继续进行广度搜索，并计算一个节点与其子节点的相似度。最后按
照一定的衰减理论[8]使不同层次中相似度占据不同的权重。改进后的推荐算法主要流程如
下： 85
1) 预处理阶段，在此阶段抽离出与用户 U 具有强关系的一部分用户，并计算其相似
度数据集，根据相似度数据集计算出一个阀值 S 作为后续处理的一个标准
2) 对用户的关系图进行广度搜索。对于用户 u，其强关系用户集为 SR(u)。那么继续
搜索 SR（u）中所有用户的强关系用户集合 SR(SR(u))，并计算 SR(u)中用户集合
与他们的强关系用户集合 SR(SR(u))之间的相似度，在计算过程中参考上述数据标90
准阀值 S 与衰减理论，对计算结果做不同处理
3) 根据用户 U 与其强关系用户集之间的相似度和通过对用户 U 进行图广度搜索计算
相似度之后的结果进行最终的过滤排序，生成推荐结果
主要算法
1) 问题建模。对 M 个用户和 N 个主题建立兴趣矩阵 I=M×N。每个用户 ui对主题95
tj对应的元素 aij=1 表示 ui对主题 tj有兴趣爱好，而当 aij=1 表示用户 ui对主题 tj之间没
有兴趣。对 M 个用户之间建立用户关系矩阵 U= M×M。对于每个 mij=1 表示用户 ui 与
用户 uj之间是相关关注的强关系。
2) 计算相似度阀值。根据用户关系矩阵 U,获取与用户有强关系的用户，并计算
拥有强关系用户之间的相似度 S，以此相似度作为一个相似标准的阀值，为下面的基于100
图的深度搜索计算相似度提供参考标准。
算法 1. 通过用户关系图矩阵 U，获取强关系数据集。
输入：用户关系图矩阵 U
输出：相似度阀值
1. for mi in Ui 105
2. for mij in Uj
3. if mij != 0
4. SR(ui).add(uj)
5. S=1
6. for u in SR(ui) 110
7. TS(ui).add(similarity(ui,u))//与用户 ui具有强关系的用户相似度数据集
8. if similarity(ui,u) < S
9. S= similarity(ui,u)
10. Return
这里就得出了我们算法第三步需要的相似度阀值 S 与强关系数据集 SR(u)。 115
3) 用户关系图的广度搜索[9]。根据六度理论和 Facebook 的最新研究，我们限定
了广度搜索的最大深度为 5，以此避免了深度过大导致额外的无效计算和其它不可预料
问题的出现。
算法 2. 根据强关系数据集，广度搜索并计算相似度
输入：相似度阀值 S 与强关系数据集 SR 120
输出：最终用户 u 的相似度集合
1. for u in SR(ui)
2. 获取用户 u 的强关系数据集，并计算 u 与其强关系用户之间相似度 SV(u)
- 4 -
中国科技论文在线
3. for s in SV
4. if s > β *S //大于阀值乘以某个权值，则放入用户 u 的强关系数据集 125
5. TS(ui).add(s)
6. Return TS
对于标识各个层次所占权值的β 以 1/2α 递减。算法最终得出具有强关系的用户相
似度与通过广度搜索用户关系图计算得到的用户相似度的合集。
4) 推荐阶段。根据最终的相似度数据集 TS 排序筛选得到最终的推荐结果。 130
实验分析
我们通过抓取新浪微博用户数据进行算法的验证。由于新浪微博用户的数量是非常大，
可能很多数据都是没有代表性的。为了解决抓取数据可能会出现的问题，我们参考了推荐系
统进行聚类分析所抓取的数据方式[10]，在抓取数据的时候就 1)对预抓取对象进行预处理，
2)在抓取过程中也采用深度优先的策略,3)随机择取抓取到的用户的好友关系和分组关系进135
行计算来决定是否要保留该用户。通过以上策略，避免了最后的数据集中于某些固定特性，
让测试结果更具有一般性和说服力。
实验参考算法为：1）基于 Top-10 的 User-Based 的协同过滤推荐算法；2）基于 Top-10
的 Item-Based 的协同过滤算法；3）基于图的广度搜索 Depth Based Graph 改进的推荐算法。
表 推荐结果对比(为了计算数据一致取整) 140
稀疏度/% 预推荐数量 实际推荐：User-Based Item-Based Depth Based Graph
5 700 260 275 600
7 650 240 250 640
10 200 100 105 200
通过表格中测试数据可以看出，此算法可以有效解决当一个新用户没有足够的行为数据145
导致不能正常推荐或者推荐数量稀少的问题。除此之外，还可以避免当无法计算出最终推荐
结果的时候，推荐系统只推荐最热的物品或者随机物品。因为最热物品可能无效点击占据了
很大部分。最重要的是，如果只推荐最热门的话，这会让最热的物品变得更加热门，让其他
物品没有被浏览的机会，让所有新用户都被推荐出相同的最热的物品。而通过算法计算，获
取圈子中绝大部分人都会看而且都给出正面评分的物品，然后再推荐给用户，这会很大程度150
提高算法的正确率，和用户的满意度。
4 结论
本文给出了在社交网络中协同过滤推荐算法的一个改进方案。在基于社交的应用中协同
过滤推荐算法，因为用户之间的数据稀疏性问题无法正常进行推荐。考虑社交网络本身的特
性，对推荐算法进行了改进。根据六度空间理论，提出了基于图的广度搜索推荐算法，将社155
交圈子中用户与用户圈子之间的相似特性纳入算法中，解决了在稀疏的数据集上推荐算法无
法进行正常推荐问题。最后通过一定的实验验证，针对真实的数据集验证了算法的有效性与
正确性。
[参考文献] (References)
[1] 马宏伟，张光卫，李鹏.协同过滤推荐算法综述[J].小型微型计算机系统，2009，30(7)，1282-1288. 160
[2] Ioannis Konstas,Vassilios,Joemon M.
On social networks and collaborative recommendation[J]. of the 32nd international ACM SIGIR
conference on Research and development in information retrieval,2009,195-202
[3] Chen J，Geyer W，DuganC，MullerM，Guy I. Make new friends，but keep the old：Recommending people
- 5 -
中国科技论文在线
on social networking. Proceedings of the27th International Conference on Human Factors in Computing 165
York,USA,2009:201-202
[4] Johan U, Brian K, Lars B, Cameron Anatomy of the Facebook Social Graph[OL].
[2011-11-18].
[5] 罗大飞.SNS 打造你的六度空间[J].《网友世界》，2007，22：77-78.
[6] 林韶娟，陶晓鹏.基于二值信任网络的推荐算法改进[J].计算机应用与软件，2012，29（12）：157-160. 170
[7] 陈晓城.基于信任传播模型的协同过滤算法研究[D].珠海：中山大学，2010.
[8] 陈克寒，韩盼盼，吴健. 基于用户聚类的异构社交网络推荐算法[J].计算机学报，2013，36(02)：349-359.
[9] 赵茹，王华军.基于广度优先搜索的空间搜索算法[J]. 福建电脑，2012, 28(3)：76-77.
[10] 路紫，王文婷.社会性网络服务社区中人际节点空间分布特征及地缘因素分析[J].《地理科学》2011，
11：1293-1300. 175
