社交网络SNS的好友推荐算法
社交网络SNS的好友推荐算法
花了几天看了些做社交的好友推荐，现在很多App都有社交场景，本身就是做用户的场景，所以以后肯定要在这块有一些应用。像早期的论坛类的更偏重资讯类的信息，后来像优酷土豆这又是做视频类，网易云音乐做音乐类。豆瓣相对来说还比较全一些，有包含资讯、音乐电台等这些。也用了一些其他做社交场景的App，包括像脉脉、钉钉这些。感觉不是太好，具体原因就是都不是什么认识的人，活跃度也不高。很多App基本上就是属于少数意见领袖，这些人有大量的粉丝。而还有一帮大量用户，他们粉丝不多活跃也不高。本质上来说，还是没有找到他们感兴趣的内容。就跟昨天一样，突然腾讯视频给我推了下2007出的《远古入侵》，这推的太给力了！一部科幻、时空穿越、冒险题材的英剧就应该推给我这样tag的用户。
我们平时光计算用户的关系亲密度，比如两者的SNS互动次数、媒介场景关系度、地理位置相关度，这些缺陷都很依赖用户之间的活跃程度。后来又有人提出了好友的好友、圈子、共同兴趣、共同话题等方面角度进行研究。实际场景中我们也是会结合 “社交”+“兴趣”两点平衡，找到一个比较融合的权衡，推荐用户感兴趣的content。
计算共同好友比例
一般最简单推荐好友就是计算两者有哪些共同好友，如果共同好友很多自然就认识的概率很大。比如我和Jackie是同学，但是我们可能都因为用Facebook时间不长，可能都没相互添加，那就可以计算我和Jackie之间发现同学的占比是多少。包括像同事、家人、朋友等等都差不多。在社交网络中, 可以根据现有的社交网络图给用户推荐新的好友, 比如给用户推荐好友的好友。基于好友的好友推荐算法可以用来为用户推荐在现实社会中相互熟悉而在当前社交网络中没有联系的其他用户。例如使用人人网时, 经常看到一些久未联系的老同学出现在推荐好友列表中。
优点是简洁、易实现, 效果明显。但是其缺点也是显而易见的, 如果用户好友人数不够多, 那么无论是为其推荐其他好友或者将其推荐给其他人都会变得很难。其次是该算法只是关注“ 人” 的因素而忽略了其他因素, 可能影响所推荐好友的准确性。
最简单的好友推荐算法是为用户推荐共同好友数最多的用户。其基本思想是, 用户之间的共同好友越多, 则他们越可能是好友。由于这种方法受用户好友总数影响较大, 因此通常根据共同好友比例计算相似度来推荐好友。
在Twitter和新浪微博等有向社交网络中, 用户u关注的人out(u)和关注用户u的人in(u)是两个不同的集合, 因此使用共同好友比例计算相似度有三种不同形式, 本文采用出度的方法, 用户u和用户v的共同好友比例fuv表示为:
其中, out(u)表示用户u关注的用户集合, out(v)表示用户v关注的用户集合。out(u)∩ out(v)表示两个集合的交集。|out(u)|和|out(v)|分别表示集合out(u)和out(v)的元素个数。
互动次数
不管人们有多少共同好友, 都无法确定是否会一直与其保持联系。社交网站倾向于促使用户尽可能多地与别人产生互动, 这样他们就能看到并从中提取信息。如果两个人之间没有互动, 很难称得上朋友。
社交网络中用户之间的互动包括消息、评论、转发和收藏等形式, 转发和评论等行为在一定程度上代表着信息对于用户的吸引力, 评论与转发等通常有不同的权重, 为了简化计算, 这里对消息、评论和转发取相同权重。
用户u与用户v之间的互动情况iuv可以用两者之间互动次数占用户u和用户v全部互动行为的比例来表示, 本文提出的互动比例计算方法如下:
其中, interact(u, v)表示用户u对用户v的互动次数, interact(u)表示用户u对所有用户的总互动次数。两用户之间互动次数用单向互动次数的平均值表示。
社交兴趣度
本文对根据社交图谱计算用户相似度的传统方法进行改进, 从共同好友和互动情况两方面来表现用户之间的关系亲密程度, 从而计算出目标用户对待推荐用户的社交兴趣度, 以此描述目标用户和待推荐用户成为好友的可能性。
建立n个用户之间的关系矩阵A, A是一个n× n矩阵, 其中, 如果用户u和v是好友关系(或用户u关注了用户v), 则auv=1, 否则auv=0。矩阵A中第u行ua= (au1, au2, , aun)反映了用户u的好友关系。
。其中, fuv表示用户之间的共同好友比例, iuv表示用户之间的互动情况比例。α 是综合共同好友比例和互动比例的参数, 其取值范围为[0, 1], 不同数据集中α 可能有不同的最佳值, 可根据经验取值或者在特定数据集上逐步调整和比较以获得最佳值。本文中取α =0.5。矩阵C中元素cuv反映了用户u与用户v关系的亲密程度。
最近邻协同过滤技术中, 由于最近邻居与目标用户对项目的评分非常相似, 因此目标用户对未评分项目的评分可以通过最近邻居对该项目评分的加权平均值近似表示。类似地, 在好友推荐中, 可以把待推荐用户看作待评分项目, 把好友作为邻居, 把用户u与用户v的关系亲密程度看作用户u对用户v的评分或者邻居用户v的权重。
兴趣相似度
社交网络中用户留下的文字和行为可以反映用户兴趣和需求。通常用户可使用自然语言或者标签主动展示其喜好。这种方法可以获得一些关于用户兴趣爱好的信息, 但是其缺点也比较明显, 自然语言理解技术不能很好地理解用户的描述, 而且用户兴趣是动态变化的, 兴趣描述很容易过时, 况且很多时候用户并不知道或者很难用语言描述喜欢什么。因此, 需要通过算法自动发掘用户历史行为数据, 以推测用户兴趣, 从而推荐满足兴趣的项目。
计算用户之间的兴趣相似度, 主要思想是: 如果用户喜欢相同物品, 则说明具有相似的兴趣。微博内容可以看作物品, 如果两个用户曾经评论、转发或者收藏过同样的微博, 则说明他们具有相似的兴趣。此外, 也可以根据用户在社交网络中的发言提取用户的兴趣标签(关键词), 计算用户的兴趣相似度。基于标签的推荐中, 很多时候用户主动标记使用的标签很少, 这可能是由于用户没有使用标签的习惯或者用户新近加入或者用户活跃度较低。因此, 通常从用户的内容数据中抽取关键词作为标签或者是根据标签之间的相似度做一些关键词扩展。
本文运用现有知识计算兴趣相似度。用关键词向量描述兴趣, 用TF-IDF公式计算关键词权重, 用关键词向量之间的余弦相似度表示兴趣相似度。
一般来说, 用户兴趣可以通过向量空间模型表示为一个关键词向量。从微博内容中提取关键词的过程需要引入一些自然语言处理技术。关键词向量生成过程包括中文文本分词、命名实体(如人名、地名、组织名等)检测、关键词排名和关键词权重计算等。用户u兴趣特征向量可以表示为
,N为用户总数, ni为包含ei的用户数目。
向量空间模型的优点是简单, 缺点是丢失了一些信息, 比如关键词之间的关系信息。但是, 在绝大多数应用中, 向量空间模型对于文本的分类、聚类、相似度计算已经可以给出令人满意的结果。
用户之间的兴趣相似度可以通过兴趣特征向量之间的余弦相似度计算如下:
余弦值与相似度成正比, 余弦值越小表示相似度越低, 余弦值越大表示相似度越高, 其取值范围为[0, 1], 0表示完全不同, 1表示完全相同。
综合社交和兴趣的好友推荐
不同的社交网络中人们的目的和侧重点往往是存在差异的, 因此, 人们通常在不同的社交网站建立不同的关系网络。例如人人网中的好友通常以同学校友或者熟人为主, 而豆瓣网中的好友却大多因相似兴趣而聚集。因此本文先计算交际兴趣度和兴趣相似度, 然后将二者综合评分, 最终推荐得分最高的Top-k位用户。由于只需要计算存在好友关系的用户之间的共同好友比例和互动比例, 因此可以有效提高效率。
社交图谱是静态的, 没有时间变化概念, 认识10年的朋友和昨天才发生交集的朋友在社交关系图上没有明显差别; 而兴趣图谱是动态的, 其变化通常会反映在历史行为中。社交图谱反映了用户的交友倾向, 而兴趣图谱反映了用户的兴趣偏好, 将两者综合考虑很可能获得比单纯考虑社交关系或者兴趣爱好更好的推荐结果。为了便于控制以上两个因素对最终结果的影响, 可将社交兴趣度和兴趣相似度分别按最大值归一化。综合社交关系和兴趣偏好的最终评分可表示如下:
其中, β 是改进的好友推荐算法的可调参数, 表示最终评分中社交因素的权重, β 取值范围为[0, 1], 本文实验中β 取0.5。s(u, v)为社交兴趣度。w(u, v)为兴趣相似度。
本文好友推荐算法执行过程如图1所示:
图1 基于社交和兴趣的好友推荐方法实验与分析
从 2012 KDD 竞赛所提供的腾讯微博数据中提取部分作为实验数据, 对本文提出的算法进行实验分析。所采集数据包括用户社交网络(关注关系)、用户社交行为(通知、转发和评论行为)以及用户关键词(关键词及其权重)。
从用户社交网络中随机选取5个较活跃用户作为种子, 采用宽度优先策略收集用户好友关系, 过滤掉好友数目少于5个和大于150的用户, 最终得到3 237个用户, 以此模拟一个小型的社交网络。随后的实验中只考虑这些用户之间的好友关系。平均每个用户关注13.4个人, 为非常稀疏的好友网络, 网络稀疏度99.6%, 表现出明显的数据长尾性。根据以上获得用户列表, 分别从用户社交行为和用户关键词中提取出相关用户的社交行为和关键词。实验数据处理步骤如图1所示。根据关系网络计算共同好友比例, 根据行为信息计算交互比例, 综合共同好友比例和交互比例获得社交兴趣度。然后根据用户关键词建立兴趣向量, 从而计算兴趣相似度。最后综合社交和兴趣两方面因素获得最终评分, 将评分最高的k位用户推荐给目标用户。
Top-k推荐中常用的评价指标有准确率(Precision)、召回率(Recall)以及综合准确率和召回率的F1-measure。其定义如下:
实验比较了基于共同好友比例、基于兴趣相似度、基于共同好友比例和兴趣相似度以及基于社交和兴趣相似度4种好友推荐算法的性能。