推荐系统（项亮）第六章

第六章 利用社交网络数据

基于社交网络的推荐可以很好的模拟现实社会。本章讨论如何利用社交网络数据给用户进行个性化推荐，一方面是给用户推荐物品，另一方面是给用户推荐好友。

6.1 获取社交网络数据的途径

互联网有很多带有社交性质的网站，如下：

6.1.1 电子邮件

电子邮件是一个比较封闭的系统，一般很难获得用户的联系人列表和用户之间的来往信件。因此对电子邮件中社交关系的研究集中在一些有大型电子邮件系统的公司。如果获得了用户的邮箱，可以通过邮箱后缀得到一定的社交关系，例如同一个公司等等，这是一种隐性的社交关系。

由于电子邮件系统包含了大量社交信息，很多社交网站在用户注册时提供了让用户从电子邮件联系人中导入好友关系的功能，以解决社交网络的冷启动问题。

6.1.2 用户注册信息

通过用户注册时的信息，可以知道哪些用户在一个机构共事过，这也是一种隐性的社交网络数据。

6.1.3 用户的位置数据

通过IP和GPS等，可以知道用户访问时的地址，这种地址可能只是精确到城市，但有时可以精确到楼栋，公司等。显然可以假设他们可能有好友关系。

6.1.4 论坛和讨论组

如果两个用户同时加入了很多不同的小组，可以假设他们互相了解或者具有相似的兴趣，如果两个用户在讨论组就某个帖子共同讨论，就更可以这样认为。

6.1.5 即时聊天工具

在即时聊天工具中，用户往往会有一个联系人列表，并且会对其进行分组，通过列表和分组信息，就可以知道用户的社交网络关系，通过统计用户之间聊天的频繁程度，可以度量他们之间的熟悉程度。当然，这也有很多隐私问题，几乎没有人会公开自己的联系人列表和聊天记录。

6.1.6 社交网站

上面介绍的各种途径，要么难以获取，要么是隐性的，很难推断出用户之间的显性社交关系。实际上，无论是电子邮件系统还是即时聊天工具，都比较封闭。

Facebook、Twitter等社交网站的出现突破瓶颈，它允许用户设置一个公开的页面，默认公开用户的好友列表，讨论的话题也较少涉及个人隐私，大都是社会热点、图片、笑话等等。社交网站的另一个好处是自然的减轻了信息过载的问题。比如只阅读关注的人，个性化推荐系统可以利用社交网站公开的用户社交网络和行为数据，辅助用户更好的完成信息过滤，寻找和自己兴趣相似的好友，找到自己感兴趣的内容等等。

社会图谱和兴趣图谱

Facebook、Twitter代表了不同的社交网络结构，前者人们的好友一般都是自己在现实中认识的人，并且好友关系需要双方确认，后者人们的好友往往在现实中没有交集，只是因为三观符合，好友关系也是单向的。人们将Facebook为代表的社交网络称为社交图谱（social graph），另一个则叫做兴趣图谱（interest graph）。

当然每个社会化网站都不是单纯的社交/兴趣图谱。

6.2 社交网络数据简介

可以用图$G(V,E,w)$定义一个社交网络，$V$是顶点集合，每个顶点代表一个用户，$E$是边集合，对于需要双向确认的关系，可以使用无向边连接，单向的朋友关系则采用有向边。对于用户顶点$u$,$out(u)$为其指向的定点集合（e.g., 用户$u$关注的用户集合），$in(u)$为指向顶点$u$的集合（关注用户$u$的用户集合）。对于Facebook这种无向社交网络，显然有$in(u)=out(u)$。

一般来说，有三种不同的社交网络数据：

  • 双向确认的社交网络数据
  • 单项关注的社交网络数据
  • 基于社区的社交网络数据：用户之间并无明确关系，但可能属于不同的社区，例如豆瓣小组、同一篇文章的不同作者，同一个公司工作的人等等。

社交网络中用户的入度（in degree）和出度（out degree）的分布也是满足长尾分布的。无论是粉丝很多的用户还是关注人数很多的用户都很少。

6.3 基于社交网络的推荐

e.g., Amazon利用Facebook的好友信息给用户推荐好友喜欢的物品

社会化推荐的优点：

  • 好友推荐可以增加推荐的信任度 同样是给用户推荐《天龙八部》，ItemCF——因为用户之前看过《射雕英雄传》，而好友推荐——因为用户有8个好友都非常喜欢《天龙八部》。第二种解释一般能让用户更加心动。
  • 社交网络可以解决冷启动问题 当一个新用户通过微博或者Facebook账号登录网站时，我们可以从社交网站中获取用户的好友列表，然后给用户推荐好友在网站上喜欢的物品。从而在没有用户行为记录时就给用户提供较高质量的推荐结果，部分解决了推荐系统的冷启动问题。

缺点：

  • 很多时候并不一定能提高推荐算法的离线精度（准确率和召回率）。特别是在基于社交图谱数据的推荐系统中，因为用户的好友关系不是基于共同兴趣产生的，所以用户好友的兴趣往往和用户的兴趣并不一致。比如，我们和自己父母的兴趣往往就差别很大。

6.3.1 基于邻域的社会化推荐算法

给定一个社交网络数据集（定义了用户间的好友关系）和一份用户行为数据集（定义了用户的历史行为和兴趣数据）。最简单的算法就是给用户推荐其好友喜欢的物品集合：
$$
p_{ui}=\sum_{v\in out(u)}r_{vi}
$$
如果用户$v$喜欢物品$i$，$r_{ui}=1$，否则为0。考虑到用户相似度的不同，有：
$$
p_{ui}=\sum_{v\in out(u)}w_{uv}r_{vi}
$$
用户相似度$w_{uv}$由两部分构成，好友熟悉程度和兴趣相似度：

  • 用户间的熟悉程度 熟悉度可以用用户之间的共同好友比例衡量，即若用户$u$和$v$很熟悉，他们应该有很多共同好友。

$$
familiarity(u,v)=\frac{|out(u)\cap out(v)|}{|out(u)\cup out(v)|}
$$

  • 用户间的兴趣相似度 如果两个用户喜欢的物品集合重合度很高，则他们的兴趣相似度也应该很高（类似于UserCF）

$$
similiarity(u,v)=\frac{|N(u)\cap N(v)|}{|N(u)\cup N(v)|}
$$

6.3.2 基于图的社会化推荐算法

从前几章知道，图模型可以将各种数据和关系都表示到图上去，社交网络中存在用户对物品的兴趣关系和用户间的社交网络关系。前者可表示为用户物品二分图，后者为社交网络图。

image-20220414120300960

其中用户间的权重可定义为用户相似度的$\alpha$倍（包括熟悉程度和兴趣相似度）；而用户和物品间的权重可定义为用户对物品喜欢程度的$\beta$倍。如果希望用户好友的行为对推荐结果有较大影响，可增加$\alpha$；若希望用户的历史行为更重要，增加$\beta$。

之后便可使用PersonalRank图排序算法给每个用户生成推荐结果。

添加社群关系的社会化推荐算法

社交网络关系：

friendship：用户和用户之间直接的社交网络关系（如上图的左半部分）

membership：两个用户同属于一个社群的社交网络关系

若要在上面介绍的基于邻域的社会化推荐算法中考虑membership的社交关系，可以利用两个用户加入的社区重合度计算用户相似度，然后再给用户推荐和他相似的用户喜欢的物品。这种算法的图模型如下图所示：

image-20220414120312949

6.3.3 实际系统中的社会化推荐算法

考虑6.3.1节中的$familiarity(u,v)=\frac{|out(u)\cap out(v)|}{|out(u)\cup out(v)|}\qquad similiarity(u,v)=\frac{|N(u)\cap N(v)|}{|N(u)\cup N(v)|}$的计算需要拿到用户所有好友的用户行为数据，目前大型网站用用户数目极大，因此不能将用户的所有行为都缓存在内存中，只能在数据库前做一个热数据的缓存。而如果我们需要比较实时的数据，这个缓存中的数据就要比较频繁地更新，因而避免不了数据库的查询。数据库查询一般是很慢的，特别是针对行为很多的用户更是如此。所以，如果一个算法再给一个用户做推荐时，需要他所有好友的历史行为数据，这在实际环境中是比较困难的。

ItemCF算法只需要当前用户的历史行为数据和物品的相关表就可以生成推荐结果。对于物品数不是特别多的网站，可以很容易地将物品相关表缓存在内存中，因此查询相关物品的代价很低，所以ltemCF算法很容易在实际环境下实现。

当然，我们可以从两个方面改进基于邻域的社会化推荐算法，让它能够具有比较快的响应时间：

  • 一种是治标不治本的方法。简单地说，就是可以做两处截断。第一处截断就是在拿用户好友集合时并不拿出用户所有的好友，而是只拿出和用户相似度最高的N个好友。此外，在查询每个用户的历史行为时，可以只返回用户最近1个月的行为，这样就可以在用户行为缓存中缓存更多用户的历史行为数据，从而加快查询用户历史行为接口的速度。此外，还可以牺牲一定的实时性，降低缓存中用户行为列表过期的频率。
  • 重新设计数据库。社会化推荐中关键的操作就是拿到用户所有好友的行为数据，然后通过一定的聚合展示给用户。如果对照微博，可以发现微博中每个用户都有一个信息墙，实时展示着用户关注的所有好友的动态。因此，如果能够实现这个信息墙，就能够实现社会化推荐算法。Twitter的解决方案是给每个用户维护一个消息队列（message queue），当一个用户发表一条微博时，所有关注他的用户的消息队列中都会加入这条微博。优点：用户获取信息墙时可以直接读消息队列，所以终端用户的读操作很快。缺点：当一个用户发表了一条微博，就会触发很多写操作，因为要更新所有关注他的用户的消息队列，特别是当一个人被很多人关注时，就会有大量的写操作。Twitter通过大量的缓存解决了这一问题。具体的细节可以参考InfoQ对Twitter架构的介绍。

如果将Twitter的架构搬到社会化推荐系统中，我们就可以按照如下方式设计系统：

  • 首先，为每个用户维护一个消息队列，用于存储他的推荐列表；
  • 当一个用户喜欢一个物品时，就将（物品ID、用户ID和时间）这条记录写入关注该用户的推荐列表消息队列中；
  • 当用户访问推荐系统时，读出他的推荐列表消息队列，对于这个消息队列中的每个物品，重新计算该物品的权重。计算权重时需要考虑物品在队列中出现的次数，物品对应的用户和当前用户的熟悉程度、物品的时间戳。同时，计算出每个物品被哪些好友喜欢过，用这些好友作为物品的推荐解释。

6.3.4 社会化推荐系统和协同过滤推荐系统

社会化推荐系统的效果往往很难通过离线实验评测，因为社会化推荐的优势不在于增加预测准确度，而是在于通过用户的好友增加用户对推荐结果的信任度，从而让用户单击那些很冷门的推荐结果。此外，很多社交网站（特别是基于社交图谱的社交网站）中具有好友关系的用户并不一定有相似的兴趣。因此，利用好友关系有时并不能增加离线评测的准确率和召回率。因此，很多研究人员利用用户调查和在线实验的方式评测社会化推荐系统。

6.3.5 信息流推荐

信息流的个性化推荐要解决的问题就是如何进一步帮助用户从信息墙上挑选有用的信息。Facebook的EdgeRank算法综合考虑了信息流中每个会话的时间、长度与用户兴趣的相似度。EdgeRank算法比较神秘，没有相关的论文，不过TechCrunch曾经公开过它的主要思想。Facebook将其他用户对当前用户信息流中的会话产生过行为的行为称为edge，而一条会话的权重定义为：
$$
\sum_{edge\ e}u_ew_ed_e\u_e指产生行为的用户和当前用户的相似度，这里的相似度主要是在社交网络图中的熟悉度\

w_e指行为的权重，这里的行为包括创建、评论、like（喜欢）、打标签等，不同的行为有不同的权重\

d_e指时间衰减参数，越早的行为对权重的影响越低
$$
从上面的描述中可以得出如下结论：如果一个会话被你熟悉的好友最近产生过重要的行为，它就会有比较高的权重。

不过，EdgeRank算法的个性化因素仅仅是好友的熟悉度，它并没有考虑帖子内容和用户兴趣的相似度。所以EdgeRank仅仅考虑了“我”周围用户的社会化兴趣，而没有重视“我”个人的个性化兴趣。为此人们深入研究了信息流推荐中社会兴趣和个性化兴趣之间的关系。他们的排名算法考虑了如下因素：

  • 会话的长度 越长的会话包括越多的信息。
  • 话题相关性 度量了会话中主要话题和用户兴趣之间的相关性。这里用了简单的TF-IDF建立用户历史兴趣的关键词向量和当前会话的关键词向量，然后用这两个向量的相似度度量话题相关性。
  • 用户熟悉程度 主要度量了会话中涉及的用户（比如会话的创建者、讨论者等）和当前用户的熟悉程度。对于如何度量用户的熟悉程度下一节将详细介绍。计算熟悉度的主要思想是考虑用户之间的共同好友数等。

6.4 给用户推荐好友

如果用户的好友很稀少，就不能体验到社会化的好处。因此好友推荐是社会化网站的重要应用之一。好友推荐系统的目的是根据用户现有的好友、用户的行为记录给用户推荐新的好友，从而增加整个社交网络的稠密程度和社交网站用户的活跃度。

6.4.1 基于内容的匹配

给用户推荐和他们有相似内容属性的用户做为好友，常见的内容属性有：

  • 用户人口统计学属性 包括年龄、性别、职业、毕业学校、工作单位等
  • 用户的兴趣 如用户喜欢的物品和发布过的言论等
  • 用户的位置信息 包括用户的住址、IP地址和邮编等

6.4.2 基于共同兴趣的的好友推荐(InterestBased)

在Twitter和微博为代表的以兴趣图谱为主的社交网络中，用户往往不关心对于一个人是否在现实社会中认识，而只关心是否和他们有共同的兴趣爱好。因此，在这种网站中需要给用户推荐和他有共同兴趣的其他用户作为好友。
基于用户的协同过滤算法（UserCF）介绍了如何计算用户之间的兴趣相似度，其主要思想就是如果用户喜欢相同的物品，则说明他们具有相似的兴趣。在新浪微博中，可以将微博看做物品，如果两个用户曾经评论或者转发同样的微博，说明他们具有相似的兴趣。在Facebook中，因为有大量用户Like（喜欢）的数据，所以更容易用UserCF算法计算用户的兴趣相似度。关于这方面的算法可以参考第3章。
此外，也可以根据用户在社交网络中的发言提取用户的兴趣标签，来计算用户的兴趣相似度。关于如何分析用户发言的内容、提取文本的关键词、计算文本的相似度，可以参考第4章。

6.4.3 基于社交网络图的好友推荐(SocialBased)

在社交网站中，我们会获得用户之间现有的社交网络图，然后可以基于现有的社交网络给用户推荐新的好友，比如可以给用户推荐好友的好友。

对于用户$u$和用户$v$，介绍三种基于社交网络的好友推荐算法：

  • 用共同好友比例计算它们的相似度：

$$
w_{out}(u,v)=\frac{|out(u)\cap out(v)|}{\sqrt{|out(u)|| out(v)|}}
$$
表示用户$u$和$v$关注的用户集合重合度

  • 在微博这种有向社交网络中，$out(v)$和$in(v)$是不同的集合:

$$
w_{in}(u,v)=\frac{|in(u)\cap in(v)|}{\sqrt{|in(u)|| in(v)|}}
$$
表示关注用户$u$的用户和关注用户$v$的用户的集合重合度

以上两种相似度都是对称的，即$w(u,v)=w(v,u)$

  • 还可定义第三种有向的相似度：

$$
w_{out,in}(u,v)=\frac{|out(u)\cap in(v)| }{|out(u)|}
$$
在用户$u$关注的用户中，有多大比例也关注了用户$v$

考虑到$v$是名人时，任何用户都和他的相似度很大，因此：
$$
w_{out,in}’(u,v)=\frac{|out(u)\cap in(v)| }{\sqrt{|out(u)||in(v)|}}
$$
这三种相似度计算的时间/空间复杂度都不高，适合在线应用使用。

离线实验

代码

数据集Slashdot

数据集Epinion

6.4.4 基于用户调查的好友推荐算法对比

对比了新颖性、设计了一些问卷进行对比，略

6.5 总结

(实在不想写这些冗余的东西，架不住强迫症)

社交网络分析的研究已经有很悠久的历史了。其中关于社交网络最让人耳熟能详的结论就是六度原理。如果转化为图的术语，就是社交网络图的直径为6。六度原理在均匀随机图上已经得到了完美证明，可以参考RandomGraph一书。很多对社交网络的研究都是基于随机图理论的，因此深入研究社交网络必须掌握随机图理论的相关知识。
社交网络研究中有两个最著名的问题。第一个是如何度量人的重要性，也就是社交网络顶点的中心度（centrality），第二个问题是如何度量社交网络中人和人之间的关系，也就是链接预测。可以参考社交网络分析方面的书。e.g.,《Social Nework Analysis: Methods and Applicaions》《Social Nework Anaysis: A Handook》
对于基于社交网络的推荐算法，因为数据集的限制，最早的研究都是基于Epinion的用户信任网络的。MaHao在Epinion数据集上提出了很多基于矩阵分解的社会化推荐算法用来解决评分预测问题，其主要思想是在矩阵分解模型中加入正则化项，让具有社交关系的用户的隐语义向量具有比较高的相似度。

ACM推荐系统大会在2010年曾经举办过一个社会化推荐比赛”，该比赛将社交网络看做一种上下文，希望参赛者能够利用社交网络信息提高推荐系统的性能。关注社交化推荐的读者可以关注一下该比赛最后发出的论文集（可能比较老了，是书中推荐的）。