一种基于社区发现的社交网络好友推荐方法

摘要

本发明公开了一种基于社区发现的社交网络好友推荐方法，属于数据挖掘、社交网络、等领域，解决现有个性化推荐中没有考虑社交网络特性的问题。本发明采集社交网络中用户历史数据，对用户的兴趣爱好建模，得到所有用户的偏好向量集合；根据用户偏好向量集合中表示用户的兴趣爱好偏好向量和表示用户的朋友关系偏好向量对用户聚类，找出社交网络中用户所在的兴趣爱好和朋友关系重叠社区；根据用户的兴趣爱好和用户的朋友关系重叠社区，得到目标用户的初始待推荐好友列表，并对得到的初始待推荐好友列表进行过滤和排序，得到最终的待推荐好友列表。本发明利用了用户的兴趣爱好和朋友关系进行好友推荐，更加适合社交网络。

说明书

技术领域

一种基于社区发现的社交网络好友推荐方法，利用社交网络具有的典型复杂 网络特性，找到社交网络中用户的兴趣爱好社区，利用用户的兴趣爱好和朋友关 系进行好友推荐，提高个性化推荐的准确度和社交服务的用户体验，涉及数据挖 掘、社交网络、个性化推荐等领域。

背景技术

社交网络是典型的复杂网络，具有复杂网络的小世界特性(small-world)、 无标度(scale-free)特性和社团结构特性。

小世界特性指的是在网络规模很大的情况下，任意两个网络节点之间可以通 过相对较小的步骤建立联系。社交网络不仅完全符合“六度分离”理论，而且具 有较小的特征路径长度，符合复杂网络的小世界特性。

无标度特性是指网络中的少数节点拥有大量的连接，而大部分节点只与很少 的节点连接，无标度特性反应了用户聚集的集中性。在社交网络中新加入的用户 更倾向于和活跃用户建立连接，比如用户加入Twitter时，首先关注自己喜欢的 明星，随着网络规模的增加，类似明星这样的节点得到的连接越来越多。

社团结构是指网络中所有的节点的联系是有规律的，一些节点的边连接非常 紧密，成为规模网络中的一个密集子网。在社团内部，节点之间的联系非常紧密， 而社团与社团之间的节点联系非常稀疏。

个性化推荐技术主要包括：协同过滤、基于内容的过滤、基于知识的过滤和 混合推荐。其中，应用最广泛的协同过滤又分为基于用户的协同过滤、基于项目 的协同过滤，基于隐语义模型的协同过滤和基于图模型的协同过滤等。

协同过滤的基本思想是通过用户的历史行为来预测目标用户最可能喜欢哪 些物品或对哪些物品感兴趣。通过分析得到用户的兴趣爱好，在所有用户中找到 与目标用户有相似兴趣的用户，综合这些相似用户对某一物品的行为(点击、评 分等)，预测目标用户对物品的喜好程度。不同的推荐算法根据不同的推荐策略 进行推荐，每种算法都有自己的优势和缺点，适用于不同的应用场景。

好友推荐是SNS社交网络的基础服务，现有的好友推荐大致可以分为两类： 一类是基于用户的社交关系，包括“朋友的朋友”和共同好友的数量来进行推荐， 比如Facebook上“People you may know”，就是通过推荐和自己没有朋友关系但 是和自己的朋友有朋友关系的用户；还有基于共同朋友的数量，共同朋友越多， 说明用户在现实生活中也可能认识，比如国内社交网站人人网，在推荐朋友时把 共同好友数量越多的用户认为可能是同学。另外一类是基于用户的兴趣爱好，比 如在Twitter上，会根据你关注的人找到和这些用户类型相同的用户，当登陆首 页时，页面上的“Who to Follow”就会出现用户推荐列表，认为用户也会对他们 感兴趣。

现有的社区发现算法通常仅仅利用社交网络的用户朋友关系网络拓扑图，而 且找到的社区是非重叠社区。另外，现有的好友推荐方法常常只利用了用户的朋 友关系，没有考虑用户的兴趣爱好或者没有考虑用户兴趣爱好的动态变化。

发明内容

本发明针对现有技术的不足之处提供一种基于社区发现的社交网络好友推 荐方法，结合社交网络的社团结构特性，基于用户的兴趣爱好和用户的朋友关系 寻找社交网络中的重叠社区，提高个性化推荐的准确度和社交服务的用户体验。

为实现上述目的，本发明采用的技术方案为：

一种基于社区发现的社交网络好友推荐方法，其特征在于，如下步骤：

(1)采集社交网络中用户历史数据，对用户的兴趣爱好建模，得到每个用 户的偏好向量集合，从而得到所有用户的偏好向量集合；

(2)根据每个用户的偏好向量集合中表示用户的兴趣爱好偏好向量和表示 用户的朋友关系偏好向量对用户聚类，找出社交网络中每个用户所在的兴趣爱好 重叠社区和朋友关系重叠社区；

(3)根据每个用户所在的兴趣爱好重叠社区和朋友关系重叠社区，得到目 标用户的初始待推荐好友列表，并对得到的初始待推荐好友列表进行过滤和排序， 得到最终的待推荐好友列表。

作为优选，所述步骤(1)中，对用户的兴趣爱好建模的具体步骤如下：

(11)对用户历史数据去噪，将不能明确表示用户的兴趣爱好的数据过滤掉， 即删除用户共同行为量最大的数据部分；

(12)对过滤后的数据进行归一化处理，并用布尔类型表示；

(13)通过布尔类型量化用户对项目的喜欢程度，获得社交网络中每个用户 的偏好向量集合。

作为优选，所述步骤(2)中，找出社交网络中每个用户所在的兴趣爱好重 叠社区和朋友关系重叠社区的具体步骤如下：

(21)生成第一个社区，加入社区集合，从用户集合中随机选取一个用户， 将选取的用户加入第一个社区，并删除用户集合中的该用户；

(22)从用户集合中选择一个用户u，与社区集合C＝{c₁,L,c_m}中的每个 社区进行计算，得到u和已存在的社区c_i的凝聚度co，计算公式如下：

$\mathrm{co}(u,c_i)=\frac{1}{x}\underset{v\in c_i}{\Sigma }\mathrm{Tani}(u,v),$

其中，u为待判定用户，v为已存在社区中的用户，v∈c_i，c_i∈C，x为社区c_i的 用户数量，Tani(u,v)为用户u和用户v的Tanimoto相似度，Tani(u,v)计算公式如 下：

$\mathrm{Tani}(u,v)=\frac{|p_u\cap p_v|}{|p_u\cup p_v|},$

其中，p_u代表用户u的兴趣爱好偏好向量或朋友关系偏好向量，p_v代表用户v 的兴趣爱好偏好向量或朋友关系偏好向量，p_u∩p_v、p_u∪p_v为用户u的偏好向 量(兴趣爱好偏好向量或朋友关系偏好向量)和用户v的偏好向量(兴趣爱好偏 好向量或朋友关系偏好向量)的与、或运算；

(23)如果满足(为预先设定的阈值)，则加入社区c_i，即可 以加入满足条件的多个社区,并从用户集合U中删除u_i，如果不能加入任何一个 已存在的社区，则生成新的社区C_m+1，C＝{c₁,c₂,L,c_m,c_m+1}，并且u∈C_m+1，同 时从用户集合U中删除u；

(24)重复(22)、(23)，直到用户集合为空时结束，得到最终的每个用户 所在的兴趣爱好重叠社区和朋友关系重叠社区。

作为优选，所述步骤(3)中，得到目标用户的初始待推荐好友列表，并对 得到的初始待推荐好友列表进行过滤和排序的步骤如下：

(31)根据CUPC算法，利用表示用户的兴趣爱好偏好向量找到社交网络 中的用户的兴趣爱好社区C_P，如果用户的兴趣爱好为重叠社区，则

$C_P=C_{P_1}\cup C_{P_2}\cup L\cup C_{P_n};$

(32)根据CUPC算法，利用表示用户的朋友关系偏好向量找到社交网络 中的朋友关系社区C_F，如果用户的朋友关系为重叠社区，则

$C_F=C_{F_1}\cup C_{F_2}\cup L\cup C_{F_n};$

(33)求目标用户v的待推荐好友列表，计算公式如下：

N_v＝C_P(v)∩C_F(v)；

(34)对待推荐好友列表中的用户排序，计算N_v中所有用户和目标用户v 的距离。

与现有技术相比，本发明的优点在于：

A.在用户的兴趣爱好建模方法中，能够把社交网络中不同对象(音乐、文 章、微博、用户等)的操作抽象为用户的兴趣爱好向量，不管是具体数值(电影 评分)，还是隐式的喜好程度(听歌次数)，通过归一化都转化为布尔值来表示， 能够适应不同操作对象和多样的数据类型。

B.社交网络具有非常明显的社团结构特性，不管是用户的社交关系，还是 用户的兴趣爱好，都呈现出高聚集性，基于用户的兴趣爱好的社区发现算法可以 找到用户的朋友关系社区和兴趣爱好社区，考虑了用户的朋友关系社区和兴趣爱 好社区为重叠社区。

基于用户的兴趣爱好的社区发现算法中，阈值可以根据本领域人员的经验值，也可 以通过模拟实验中的最优经验值设定初始值，然后根据得到的社区结果反馈调节， 对零散的社区重新设定阈值，从而可将它们重新聚合。

C.获得待推荐好友列表时，将同时属于朋友关系社区和兴趣爱好社区里的 节点作为待选集，同时考虑了目标用户的好友关系和兴趣爱好，更加个性化。

D.对待推荐好友进行排序的方法中，计算他们和目标用户的最短距离，即 和目标用户距离越近，提高了他们认识的可能性。

附图说明

图1为本发明个性化推荐系统整体流程图；

图2为本发明基于社区发现的个性化推荐整体流程图；

图3为本发明用户的兴趣爱好建模流程图；

图4为本发明基于用户的兴趣爱好的社区发现算法流程图；

图5为本发明基于社区发现的好友推荐流程图。

具体实施方式

下面将结合附图及具体实施例对本发明作进一步说明。

一种基于社区发现的社交网络好友推荐方法，如下步骤：

(1)采集社交网络中用户历史数据，对用户的兴趣爱好建模，得到每个用 户的多个偏好向量集合，每个用户的多个偏好向量包括该用户的兴趣爱好偏好向 量和朋友关系偏好向量，从而得到所有用户的偏好向量集合，对用户的兴趣爱好 建模的具体步骤如下：

(11)对用户历史数据去噪，将不能明确表示用户的兴趣爱好的数据过滤 掉，即删除用户共同行为量最大的数据部分，如对明星的关注、对热门电影的观 看等；

(12)对过滤后的数据进行归一化处理，并用布尔类型表示；

(13)通过布尔类型量化用户对项目的喜欢程度，获得社交网络中每个用 户的偏好向量集合，每个用户的偏好向量集合包括该用户的兴趣爱好偏好向量和 朋友关系偏好向量，当项目为社交网络中具体物品，如电影、书籍、文章等时， 偏好向量代表用户的具体兴趣爱好，当项目为用户时，偏好向量代表用户的朋友 关系。

(2)根据每个用户的偏好向量集合中表示用户的兴趣爱好偏好向量和表示 用户的朋友关系偏好向量对用户聚类，找出社交网络中每个用户所在的兴趣爱好 重叠社区和朋友关系重叠社区，找出社交网络中每个用户所在的兴趣爱好重叠社 区和朋友关系的重叠社区的具体步骤如下：

(21)生成第一个社区，加入社区集合，从用户集合中随机选取一个用 户，将选取的用户加入第一个社区，并删除用户集合中的该用户；

(22)从用户集合中选择一个用户u，与社区集合C＝{c₁,L,c_m}中的每 个社区进行计算，得到u和已存在的社区c_i的凝聚度co，计算公式如下：

$\mathrm{co}(u,c_i)=\frac{1}{x}\underset{v\in c_i}{\Sigma }\mathrm{Tani}(u,v),$

其中，u为待判定用户，v为已存在社区中的用户，v∈c_i，c_i∈C，x为社区c_i的 用户数量，Tani(u,v)为用户u和用户v的Tanimoto相似度，Tani(u,v)计算公式如 下：

$\mathrm{Tani}(u,v)=\frac{|p_u\cap p_v|}{|p_u\cup p_v|},$

其中，p_u代表用户u的兴趣爱好偏好向量或朋友关系偏好向量，p_v代表用户v 的兴趣爱好偏好向量或朋友关系偏好向量，p_u∩p_v、p_u∪p_v为用户u的偏好向 量(兴趣爱好偏好向量或朋友关系偏好向量)和用户v的偏好向量(兴趣爱好偏 好向量或朋友关系偏好向量)的与、或运算；

(23)如果满足(为预先设定的阈值)，则加入社区ci，即 可以加入满足条件的多个社区,并从用户集合U中删除u_i，如果不能加入任何一 个已存在的社区，则生成新的社区C_m+1，C＝{c₁,c₂,L,c_m,c_m+1}，并且u∈C_m+1， 同时从用户集合U中删除u；

(24)重复(22)、(23)，直到用户集合为空时结束，得到最终的每个用 户所在的兴趣爱好重叠社区和朋友关系重叠社区。

(3)根据每个用户所在的兴趣爱好重叠社区和朋友关系重叠社区，得到目 标用户的初始待推荐好友列表，并对得到的初始待推荐好友列表进行过滤和排序， 得到最终的待推荐好友列表，得到目标用户的初始待推荐好友列表，并对得到的 初始待推荐好友列表进行过滤和排序的步骤如下：

(31)根据CUPC算法，利用表示用户的兴趣爱好偏好向量找到社交网 络中的用户的兴趣爱好社区C_P，如果用户的兴趣爱好为重叠社区，则

$C_P=C_{P_1}\cup C_{P_2}\cup L\cup C_{P_n};$

(32)根据CUPC算法，利用表示用户的朋友关系偏好向量找到社交网 络中的朋友关系社区C_F，如果用户的朋友关系为重叠社区，则

$C_F=C_{F_1}\cup C_{F_2}\cup L\cup C_{F_n};$

(33)求目标用户v的待推荐好友列表，计算公式如下：

N_v＝C_P(v)∩C_F(v)；

(34)对待推荐好友列表中的用户排序，计算N_v中所有用户和目标用户 v的距离。

参见图1，一种基于社区发现的社交网络好友推荐方法，首先从社交网络中 提取用户历史数据，包括用户历史行为数据和项目特征属性；用户历史行为数据 是指用户的行为数据，比如在豆瓣网站上对文章的“喜欢”，在新浪微博的转发 等；项目特征属性是指社交网络中操作对象的属性，比如豆瓣音乐上歌曲的类型、 时长、歌手，电影的导演、地区、语言等。从这些数据中提取出用户的兴趣爱好， 建立用户-项目的用户爱好矩阵。对于不同类型的社交网络，选择与之符合的相 似性计算方式和推荐算法，得到初始待推荐好友列表。再对初始待推荐好友列表 进行过滤，删除不符合朋友关系条件的部分。最好通过相应的排序策略进行排序， 得到最终的好友推荐列表。

参阅图2，一种基于社区发现的社交网络好友推荐方法，整个流程分为三个 步，一、首先从社交网络采集用户历史行为数据提取能表示用户兴趣爱好的数据， 然后进行去噪和归一化等预处理，对用户的兴趣爱好建模，得到每个用户的偏好 向量集合(表示用户的兴趣爱好偏好向量和表示用户的朋友关系偏好向量)，从 而得到所有用户的偏好向量集合；二、通过基于用户偏好的社区发现算法，找出 社交网络的社团结构，对于目标用户，找出他所在的重叠社区，作为初始待推荐 列表；三、通过过滤、删除和目标用户有朋友关系的节点，求待推荐集合中用户 和目标用户的排序最短距离，作为最终的待推荐好友列表。

参阅图3，描述对用户的兴趣爱好建模的具体流程。提取用户的兴趣爱好的 历史数据大致分为两种方式：一、用户的显示信息(explicit info)，显示信息包 括社交网络中用户在注册时提供的人口统计信息、对项目的评分等显示操作，比 如对Netflix网站上的电影的评分，对新浪微博的点赞和转发等；二、用户的隐 式操作(implicit behavior)，隐式操作包括对豆瓣网站上文章的阅读、对音乐电 台Pandora的听歌次数等隐式行为记录。在各种不同类型的社交网络中，都可以 通过这样的显示信息或隐式操作数据来提取用户的行为爱好。通过社交网站开放 平台提供的API接口或网络爬虫等技术，可以收集和提取用户的行为数据。

在获得用户历史数据后对其进行去噪和归一化处理。去噪是指获得的用户历 史数据中可能存在着用户的误操作，或者不能代表用户兴趣爱好的项目。比如用 户在豆瓣网上查看关于“数据挖掘”的文章和查看关于“英语四级”的文章，后 者则更能表明用户的兴趣爱好，因为大多数大学生必须参加英语四级考试，而少 部分人因为对数据挖掘感兴趣才查看相关文章。在计算用户的不同兴趣爱好时， 也需要对不同的行为数据进行处理。比如用户在在线音乐网站上的听歌记录，不 同的用户会选择不同的歌手，对非常喜欢的歌手的歌曲的重复次数比一般喜欢的 歌手多，但仅仅使用听歌次数来说明不同用户对歌手的喜好程度存在偏差，还需 要考虑每个用户听歌的总次数和对每首歌曲的听歌次数。如何将这些行为数据统 一在一个相同的取值范围中，从而使得加权求和得到的总体喜好更加精确，就需 要进行归一化处理。最简单的归一化处理，就是将各类数据除以此类中的最大值， 以保证归一化后的数据取值在{0,1}范围内。

通过去噪和归一化处理后，类似用户的兴趣，用户对电影评分、用户对微博 的点赞和转发、对用户的关注等都可以用具体的数值来表示用户的喜好程度。比 如在豆瓣电台上，对一首歌可以选择“喜好”、“不喜欢”和“跳过”等操作，则 可以用布尔类型表示，比如对文章的浏览、对微博的转发等，直接用0和1表示； 对于由具体数值表示的数据，比如对电影的评分、音乐社交网站上的听歌次数等， 首先进行归一化，然后再转化为用-1、0和1表示。可用1表示“喜好”、0表示 “跳过”，-1表示“不喜欢”。通过量化用户对项目的喜欢程度，从而获得动态 的用户的偏好向量，得到每个用户的偏好向量集合(表示的用户兴趣爱好偏好向 量和表示用户的朋友关系偏好向量)，从而得到所有用户的偏好向量集合。

参阅图4，是基于用户偏好的社区发现算法流程。初始化社交网络社区集 用户集合U＝{u₁,u₂,u₃,L,u_n}，每个用户的兴趣爱好p＝{1,1,0,L,1}，用 户之间的兴趣爱好向量维数可以相同也可以不同。首先从用户集合U中随机选 取一个用户u₁，生成一个社区c₁，将c₁加入社区集合C，然后再从用户集合U中 选取下一个用户，通过计算判断它是加入已经存在的社区，还是成为新社区里的 用户，当选取的用户已加入社区或成为新社区的用户，都需要删除用户集合中的 用户。重复以上过程，直到每个用户都加入了对应的社区，即用户集合为空时， 社区集合C＝{c₁,c₂,c₃,L,c_m}就是CUPC算法得到的社区结果。在判断用户是否 能够加入一个社区时，定义用户的社区凝聚度为co，计算公式如下：

$\mathrm{co}=\frac{1}{m}\underset{v\in c_i}{\Sigma }\mathrm{Tani}(u,v);$

而判断用户能否加入一个社区的条件是他的凝聚度是否大于预先设置的阈 值，即满足：

其中，u为待判定用户，v为已存在社区中的用户，v∈c_i，c_i∈C，x为社区 c_i的用户数量，Tani(u,v)为用户u和用户v的Tanimoto相似度，为判断一个用 户能否加入一个社区的阈值，在这个步骤中，目标用户需要和社区里的每一个用 户计算相似度，再求得它与这个社区所有用户相似度的平均值(凝聚度)，通过 与比较来判断是否可以加入这个社区。

具体步骤为：

步骤1：初始化，生成一个社区c₁，从用户集合U中随机选取u₁，使u₁∈c₁， 并将c₁加入社区集合C，并删除用户集合中的该用户，此时U＝{u₂,u₃,L,u_n}， C＝{c₁}，c₁＝{u₁}；

步骤2：从用户集合U中选择下一个用户u_i，与社区集合C＝{c₁,L,c_m}中的 每个社区的用户进行比较，判断能否加入与用户u_i进行比较的社区，如果能够加 入某个社区c_x，则u_i∈c_x，并从用户集合U中删除u_i，进入步骤4，否则直接 进入步骤3；

步骤3：生成新的社区C_m+1，u_i∈C_m+1，C＝{c₁,c₂,L,c_m+1}，并从用户集合U 中删除u_i，进入步骤4；

步骤4：如果则算法结束，否则进入步骤2。

当一个节点加入某个社区，并从用户集合中删除此用户节点后，按流程图进 入下一步判断用户集合是否为空，这样得到的社区没有重叠部分。但是在社交网 络中，用户很可能属于多个社区，比如当用户的偏好向量代表用户的兴趣时，把 拥有多个相同兴趣的用户聚类时，用户很可能属于多个社区，要得到社交网络的 重叠社区结构，必需在删除后，继续判断是否能加入社区集合中还没有进行判断 的社区。按照此方法，则CUPC最后得到的社区将是重叠社区。在判断一个用户 是否能够加入一个社区时，需要和这个社区的所有用户进行相似度计算，对它和 每个用户的相似度累加求平均，这样得到的聚类的凝聚性高。阈值的设置将会影 响CUPC(社区发现算法)的最终结果，如果阈值设置得较小，那么得到的社区 数量会相对较少，而社区内的用户数量相对较多，这样得到的社区区分度不高， 而如果阈值设置得较大，那么得到的社区数量会相对教多，而社区内的用户数量 相对较少，还可能产生很多只有几个用户的社区，阈值的设置需要考虑到上述情 况。

一种基于社区发现的社交网络好友推荐方法，具体的实施过程是通过基于用 户的兴趣爱好的社区发现算法，找到用户所在的朋友关系社区和兴趣爱好社区， 选择同时属于这两个社区的节点作为初始待推荐好友列表，再通过过滤和排序， 得到最终推荐列表。

图5为基于社区发现的好友推荐流程，具体步骤为：

①初始化社交网络G＝(U,E,P)，U是用户集合，U＝(u₁,u₂,L,u_n)，E是用 户的朋友关系集合，P为用户的兴趣爱好集合。

②根据用户兴趣爱好对用户聚类，利用用户的兴趣爱好向量，比如对视频的 观看、对文章的浏览或对歌曲的收听等，找出社交网络中的用户的兴趣爱好社区 C_P(v)，如果用户属于重叠社区，这些兴趣社区里的用户都和目标用户有相同的兴 趣爱好，需要将这些社区并起来，结果为

③根据用户的朋友关系，基于共同好友数量对用户进行聚类，找出社交网络 中用户朋友关系社区C_F(v)，如Facebook中的朋友关系(双向关系)、Twitter中 的关注关系(单向关系)等，如果用户属于重叠社区，这些朋友社区里的用户都 和目标用户有相当数量的共同好友，需要将这些社区并起来，结果为 $C_F=C_{F_1}\cup C_{F_2}\cup L\cup C_{F_n}.$

④根据②和③得到兴趣爱好社区和朋友关系社区，将同时属于两个社区的用 户作为初始待推荐好友集合N_v＝C_P(v)∩C_F(v)，这些用户和目标用户不仅有相 同的兴趣爱好，在现实生活中认识的可能性也比较大，成为朋友的可能性也比不 属于初始待推荐好友集合的用户可能性大。

⑤对④中得到初始待推荐好友列表进行排序，计算和目标用户没有边连接的 节点到目标用户的距离，距离越近，权重越高，最终得到待推荐好友列表。

根据用户历史数据提取用户的兴趣爱好向量，既可以表示用户朋友关系(社 交网络拓扑图)，也可以表示用户的兴趣爱好。通过基于用户偏好的社区发现算 法得到的是重叠社区，更适合于社交网络，并同时考虑用户的兴趣爱好和朋友关 系进行好友推荐，提高了用户体验和个性化推荐的准确度。

本发明已经通过上述实施例进行了说明，但应当理解的是，上述实施例只是 用于举例和说明的目的，而非意在将本发明限制于所描述的实施例范围内。此外 本领域技术人员可以理解的是，本发明并不局限于上述实施例，根据本发明的教 导还可以做出更多种的变型和修改，这些变型和修改均落在本发明所要求保护的 范围以内。本发明的保护范围由附属的权利要求书及其等效范围所界定。