第6章利用社交网络数据

美国著名的第三方调查机构尼尔森调查了影响用户相信某个推荐的因素(参见“Global Advertising Consumers Trust Real Friends and Virtual Strangers the Most”，http://blog.nielsen.com/nielsen-wire/consumer/global-advertising-consumers-trust-real-friends-and-virtual-strangers-the-most/ )。书中这部分有关于这次调查的简略介绍。实验证明了好友的推荐对于增加用户对推荐结果的信任度非常重要，并且该实验也从侧面说明了社交网络在推荐系统中可能具有重要的作用。

本章详细讨论了如何利用社交网络数据给用户进行个性化推荐。本章不仅讨论如何利用社交网络给用户推荐物品，而且将讨论如何利用社交网络给用户推荐好友。

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

6.1.1 电子邮件

谷歌在2010年的KDD会议上发表了一篇文章(参见Maayan Roth、Assaf Ben-David、David Deutscher、Guy Flysher、Ilan Horn、Ari Leichtberg、Naty Leiser、Yossi Matias、Ron Merom的“Suggesting Friends Using the Implicit Social Graph”（ACM 2010 Article，2010）)，其中就研究了如何通过Gmail系统中、一些不违反隐私协议的数据预测用户之间的社交关系，以便给用户推荐好友的问题。

其次，如果能够获得用户的邮箱，也可以通过邮箱后缀得到一定的社交关系信息。

6.1.2 用户注册信息

用户注册时输入的信息也是一种隐性社交网络数据，可以用来分析。

6.1.3 用户的位置数据

可以通过得到的IP地址，GPS数据作为用户位置信息，进而分析出用户的同事、邻居等关系。

6.1.4 讨论和讨论组

类似于豆瓣上的小组。兴趣相近的人可能会加入一些相同的小组。

6.1.5 即时聊天工具

通过即时聊天工具上的联系人列表和分组信息，知道用户的社交网络关系，并且能够通过统计用户之间聊天的频繁程度，度量出用户之间的熟悉程度。但与电子邮件一样，存在隐私问题。

6.1.6 社交网络

上述各种获取用户社交关系的途径，要么就是因为隐私问题很难获取，要么就是虽然容易获取，但却都是隐性社交关系数据，很难推断出用户之间的显性社交关系。
但以Facebook和Twitter为代表的新一代社交网络突破了这个瓶颈。

社交网站的另一个好处是自然地减轻了信息过载问题。在社交网站中，我们可以通过好友给自己过滤信息。比如，我们只关注那些和我们兴趣相似的好友，只阅读他们分享的信息，因此可以避免阅读很多和自己无关的信息。个性化推荐系统可以利用社交网站公开的用户社交网络和行为数据，辅助用户更好地完成信息过滤的任务，更好地找到和自己兴趣相似的好友，更快地找到自己感兴趣的内容。

1.社会图谱和兴趣图谱

Facebook和Twitter作为社交网站中的两个代表，它们其实代表了不同的社交网络结构。在Facebook里，人们的好友一般都是自己在现实社会中认识的人(参见“Friends & Frenemies: Why We Add and Remove Facebook Friends”，地址为http://blog.nielsen.com/nielsenwire/online_mobile/friends-frenemies-why-we-add-and-remove-facebook-friends/ ，尼尔森的这个报告表明82%的用户会因为在现实社会中认识而在Facebook中加好友。)，并且Facebook中的好友关系是需要双方确认的。在Twitter里，人们的好友往往都是现实中自己不认识的，而只是出于对对方言论的兴趣而建立好友关系，好友关系也是单向的关注关系。以Facebook为代表的社交网络称为社交图谱(social graph)，而以Twitter为代表的社交网络称为兴趣图谱(interest graph)。

关于这两种社交网络的分类早在19世纪就被社会学家研究过。19世纪，德国社会学家斐迪南·滕尼斯（Ferdinand Tönnies）认为社会群体分为两种，一种是通过人们之间的共同兴趣和信念形成的，他将这种社会群体称为Gemeinschaft，而Gemeinschaft这个词后来被翻译成英语就是community，即汉语中的社区。另一种社会群体则是由于人们之间的亲属关系，工作关系而形成的，他称之为Gesellschaft，英文翻译为society，即汉语中的“社会”。因此，斐迪南·滕尼斯说的Gemeinschaft就是兴趣图谱，而Gesellschaft就是社会图谱。

但是，每个社会化网站都不是单纯的社交图谱或者兴趣图谱。

6.2 社交网络数据简介

可以用图定义社交网络并表示用户之间的关系。用图$G(V,E,w)$定义一个社交网络，其中$V$是顶点集合，每个顶点代表一个用户，$E$是边集合，如果用户$v_a$和$v_b$有社交网络关系，那么就有一条边$e(v_a , v_b)$连接这两个用户，而$w(v_a , v_b)$定义了边的权重。业界有两种著名的社交网络。一种以Facebook为代表，它的朋友关系是需要双向确认的，因此用无向边连接有社交网络关系的用户。另一种以Twitter为代表，它的朋友关系是单向的，因此用有向边代表这种社交网络上的用户关系。

此外，对图$G$中的用户顶点$u$，定义$out(u)$为顶点$u$指向的顶点集合（如果套用微博中的术语，$out(u)$就是用户$u$关注的用户集合），定义$in(u)$为指向顶点$u$的顶点集合（也就是关注用户$u$的用户集合）。那么，在Facebook这种无向社交网络中显然有$out(u)$=$in(u)$。

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

双向确认的社交网络数据 以Facebook为代表的社交网络。用户A和B之间形成好友关系需要通过双方的确认。此种社交网络一般可以通过无向图表示。
单向关注的社交网络数据 以Twitter为代表的社交网络。用户A可以关注用户B而不需要得到用户B的允许。此种社交网络一般可以通过有向图表示。
基于社区的社交网络数据 以豆瓣小组为代表的社交网络。用户之间没有明确的关系，但这种社交网络数据办函了用户属于不同社区的数据。

社交网络数据中的长尾分布

该节利用了Slashdot的社交网络数据集(数据集来自Stanford Large Network Dataset Collection，参见http://snap.stanford.edu/data/ )统计了用户入度(in degree)和出度(out degree)的分布，得到了两个结论：

用户的入度近似长尾分布，说明在一个社交网络中影响力大的用户总是占少数。
用户的出度同样近似长尾分布，说明在一个社交网络中，关注很多人的用户占少数，而绝大多数用户只关注很少的人。

6.3 基于社交网络的推荐

社会化推荐之所以受到很多网站的重视，是缘于如下优点。

好友推荐可以增加推荐的信任度 好友往往是用户最信任的。用户往往不一定信任计算机的智能，但会信任好朋友的推荐。
社交网络可以解决冷启动问题 当新用户使用社交网络账号登录网站时，网站可以从社交网站中获取用户的好友列表，然后给用户推荐好友在网站上喜欢的物品。

社会化推荐同样拥有缺点，其中最主要的就是很多时候并不一定能提高推荐算法的离线精度（准确率和召回率）。特别是在基于社交图谱数据的推荐系统中，因为用户的好友关系不是基于共同兴趣产生的，所以用户好友的兴趣往往和用户的兴趣并不一致。举个例子就是我们和父母在社交网络上虽然是好友，但兴趣差别很大。

2010年，ACM推荐系统大会的一个讨论组CAMRa曾经举办过一个关于社交网络的推荐系统比赛(参见http://www.dai-labor.de/camra2010/ )。该比赛希望参赛者能够利用用户之间的好友关系给用户推荐电影，并且利用准确率相关的指标评测参赛者的推荐算法。对社会化推荐感兴趣的读者可以关注一下该会议的相关论文。

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

如果给定一个社交网络和一份用户行为数据集。其中社交网络定义了用户之间的好友关系，而用户行为数据集定义了不同用户的历史行为和兴趣数据。那么最简单算法是给用户推荐好友喜欢的物品集合。即用户$u$对物品$i$的兴趣$p_{ui}$可以通过如下公式计算。
$$
p_{ui} = \sum_{v \in \text{out(u)}} r_{vi}
$$
$\text{out(u)}$是用户$u$的好友集合，如果用户$v$喜欢物品$i$，则$r_{vi} =1$，否则$r_{vi} = 0$。同时由于不同的好友和用户$u$的熟悉程度和兴趣相似度也是不同的。因此，应该在推荐算法中考虑好友和用户的熟悉程度以及兴趣相似度：
$$
p_{ui} = \sum_{v \in \text{out(u)}} w_{uv}r_{vi}
$$
$w_{uv}$由两部分相似度构成，一部分是用户$u$和用户$v$的熟悉程度，另一部分是用户$u$和用户$v$的兴趣相似度。用户$u$和用户$v$的熟悉程度(familiarity)描述了用户$u$和用户$v$在现实社会中的熟悉程度。一般来说，用户更加相信自己熟悉的好友的推荐，因此我们需要考虑用户之间的熟悉度。熟悉度可以用用户之间的共同好友比例来度量。也就是说如果用户$u$和用户$v$很熟悉，那么一般来说他们应该有很多共同的好友。
$$
familiarity(u,v) = \frac{\vert out(u) \cap out(v) \vert}{\vert out(u) \cup out(v) \vert}
$$
除了熟悉程度，还需要考虑用户之间的兴趣相似度，而兴趣相似度可以通过和UserCF类似的方法度量，即如果两个用户喜欢的物品集合重合度很高，两个用户的兴趣相似度很高。
$$
similarity(u,v) = \frac{N(u) \cap N(v)}{N(u) \cup N(v)}
$$
其中$N(u)$是用户$u$喜欢的物品集合。

下面的代码实现社会化推荐的逻辑。在代码中，familiarity存储了每个用户最熟悉的$K$个好友和他们的熟悉程度，similarity存储了和每个用户兴趣最相关的$K$好友和他们的兴趣相似度。train记录了每个用户的行为记录，其中train[u]记录了用户$u$喜欢的物品列表。

def Recommend(uid, familiarity, similarity, train):
    rank = dict() 
    interacted_items = train[uid] 
    for fid,fw in familiarity[uid]:
        for item,pw in train[fid]:
            # if user has already know the item 
            # do not recommend it 
            if item in interacted_items:
                continue 
            addToDict(rank, item, fw * pw)
    for vid,sw in similarity[uid]:
        for item,pw in train[vid]:
            if item in interacted_items: 
                continue 
            addToDict(rank, item, sw * pw)
    return rank

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

图模型的优点是可以将各种数据和关系都表示到图上去。在社交网站中存在两种关系，一种是用户对物品的兴趣关系，一种是用户之间的社交网络关系。本节主要讨论如何将这两种关系建立到图模型中，从而实现对用户的个性化推荐。

用户的社交网络可以表示为社交网络图，用户对物品的行为可以表示为用户物品二分图，而这两种图可以结合成一个图。该图上有用户顶点和物品顶点两种顶点。如果用户$u$对物品$i$产生过行为，那么两个节点之间就有边相连。如果用户$u$和用户$v$是好友，那么也会有一条边连接这两个用户。

在定义完图中的顶点和边后，需要定义边的权重。其中用户和用户之间边的权重可以定义为用户之间相似度的$\alpha$倍（包括熟悉程度和兴趣相似度），而用户和物品之间的权重可以定义为用户对物品喜欢程度的$\beta$倍。$\alpha$和$\beta$需要根据应用的需求确定。如果希望用户好友的行为对推荐结果产生比较大的影响，那么就可以选择比较大的$\alpha$。相反，如果希望用户的历史行为对推荐结果产生比较大的影响，就可以选择比较大的。

在定义完图中的顶点、边和边的权重后，就可以利用前面几章提到的PersonalRank图排序算法给每个用户生成推荐结果。

在社交网络中，除了常见的、用户和用户之间直接的社交网络关系，还有一种关系，即两个用户属于同一个社群。Quan Yuan等详细研究了这两种社交网络关系(参见Quan Yuan、Li Chen和Shiwan Zhao的“Factorization vs. regularization: fusing heterogeneous social relationships in top-n recommendation”（ACM 2011 Article，2011）)，他们将第一种社交网络关系称为friendship，而将第二种社交网络关系称为membership。如果要在前面提到的基于邻域的社会化推荐算法中考虑membership的社交关系，可以利用两个用户加入的社区重合度计算用户相似度，然后给用户推荐和他相似的用户喜欢的物品。但是，如果利用图模型则更为容易，可以加入一种节点表示社群，而如果用户属于某一社群，图中就有一条边联系用户对应的节点和社群对应的节点。建立图模型后，就可以通过前面提到的基于图的推荐算法(例如PersonalRank)给用户推荐物品。

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

6.3.1节提出的基于邻域的社会化推荐算法看似简单，但在实际系统中却是很难操作的，这主要是因为该算法需要拿到用户所有好友的历史行为数据，而这一操作在实际系统中是比较重的操作。因为大型网站中用户数目非常庞大，用户的历史行为记录也非常庞大，所以不太可能将用户的所有行为都缓存在内存中，只能在数据库前做一个热数据的缓存。

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

可以从几个方面改进基于邻域的社会化推荐算法，让它能够具有比较快的响应时间。改进的方向有两种，一种是治标不治本的方法。简单地说，就是可以做两处截断。第一处截断在拿用户好友集合时只拿出用户相似度最高的N个好友而非全部，从而给该用户做推荐时可以只查询N次用户历史行为接口。此外，在查询每个用户的历史行为时，只返回用户最近1个月的行为，这样就可以在用户行为缓存中缓存更多用户的历史行为数据，从而加快查询用户历史行为接口的速度。此外，还可以牺牲一定的实时性，降低缓存中用户行为列表过期的频率。

而第二种解决方案需要重新设计数据库。Twitter的解决方案是给每个用户维护一个消息队列(message queue)，当一个用户发表一条微博时，所有关注他的用户的消息队列中都会加入这条微博。这个实现的优点是用户获取信息墙时可以直接读消息队列，所以终端用户的读操作很快。不过这个实现也有缺点，当一个用户发表了一条微博，就会触发很多写操作，因为要更新所有关注他的用户的消息队列，特别是当一个人被很多人关注时，就会有大量的写操作。Twitter通过大量的缓存解决了这一问题。具体的细节可以参考InfoQ对Twitter架构的介绍(参见“Twitter, an Evolving Architecture”，地址为http://www.infoq.com/news/2009/06/Twitter-Architecture )。

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

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

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

关于社会化推荐系统的离线评测可以参考Georg Groh和Christian Ehmig的工作成果(参见“Recommendations in Taste Related Domains: Collaborative Filtering vs. Social Filtering”，2007年)。不过社会化推荐系统的效果往往很难通过离线实验评测，因为社会化推荐的优势不在于增加预测准确度，而是在于通过用户的好友增加用户对推荐结果的信任度，从而让用户单击那些很冷门的推荐结果。此外，很多社交网站（特别是基于社交图谱的社交网站）中具有好友关系的用户并不一定有相似的兴趣。因此，利用好友关系有时并不能增加离线评测的准确率和召回率。因此，很多研究人员利用用户调查和在线实验的方式评测社会化推荐系统。

对社会化推荐系统进行用户调查的代表性工作成果是Rashmi Sinha和Kirsten Swearingen对比社会化推荐系统和协同过滤推荐系统的论文(参见“Comparing Recommendations Made by Online Systems and Friends”，2001年 )。这一节简单介绍了他们的工作方法和结果，详细见书。

6.3.5 信息流推荐

信息墙已经是个性化的，但里面仍夹杂了很多垃圾信息。因此，信息流的个性化推荐要解决的问题就是如何进一步帮助用户从信息墙上挑选有用的信息。

目前最流行的信息流推荐算法是Facebook的EdgeRank，该算法综合考虑了信息流中每个会话的时间、长度与用户兴趣的相似度。EdgeRank算法比较神秘，没有相关的论文，不过TechCrunch曾经公开过它的主要思想(参见“EdgeRank: The Secret Sauce That Makes Facebook’s News Feed Tick”，地址为http://techcrunch.com/2010/04/22/facebook-edgerank/ )。Facebook将其他用户对当前用户信息流中的会话产生过行为的行为称为edge，而一条会话的权重定义为：

$$
\sum_{\text{edge} \ e}u_e w_e d_e
$$

$u_e$指产生行为的用户和当前用户的相似度，这里的相似度主要是在社交网络图中的熟悉度；
$w_e$指行为的权重，这里的行为包括创建、评论、like(喜欢)、打标签等，不同的行为有不同的权重。
$d_e$指时间衰减参数，越早的行为对权重的影响越低。

从上面的描述中可以得出如下结论：如果一个会话被你熟悉的好友最近产生过重要的行为，它就会有比较高的权重。

不过，EdgeRank算法的个性化因素仅仅是好友的熟悉度，它并没有考虑帖子内容和用户兴趣的相似度。所以EdgeRank仅仅考虑了“我”周围用户的社会化兴趣，而没有重视“我”个人的个性化兴趣。为此，GroupLens的研究人员Jilin Chen深入研究了信息流推荐中社会兴趣和个性化兴趣之间的关系。 (参见Jilin Chen、Rowan Nairn和Ed H. Chi的“Speak Little and Well: Recommending Conversations in Online Social Streams”（ACM 2011 Article, 2011）)他们的排名算法考虑了如下因素。

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

为了验证算法的性能，Jilin Chen同样也设计了一个用户调查。首先，他通过问卷将用户分成两种类型。第一种类型的用户使用Twitter的目的是寻找信息，也就是说他们将Twitter看做一种信息源和新闻媒体。而第二种用户使用Twitter的目的是了解好友的最新动态以及和好朋友聊天。然后，他让参试者对如下5种算法的推荐结果给出1~5分的评分，其中1分表示不喜欢，5分表示最喜欢。

Random 给用户随机推荐会话
Length 给用户推荐比较长的会话
Topic 给用户推荐和他兴趣相关的会话。
Tie 给用户推荐和他熟悉的好友参与的会话。
Topic+Tie 综合考虑会话和用户的兴趣相关度以及用户好友参与会话的程度。

通过收集用户反馈，Jilin Chen发现对于所有用户不同算法的平均得分是：
Topic+Tie > Tie > Topic > Length > Random
而对于主要目的是寻找信息的用户，不同算法的得分是：
Topic+Tie ≥ Topic > Length > Tie > Random
对于主要目的是交友的用户，不同算法的得分是：
Topic+Tie > Tie > Topic > Length > Random

实验结果说明，综合考虑用户的社会兴趣和个人兴趣对于提高用户满意度是有帮助的。因此，当我们在一个社交网站中设计推荐系统时，可以综合考虑这两个因素，找到最合适的融合参数来融合用户的社会兴趣和个人兴趣，从而给用户提供最令他们满意的推荐结果。

6.4 给用户推荐好友

好友推荐系统的目的是根据用户现有的好友、用户的行为记录给用户推荐新的好友，从而增加整个社交网络的稠密程度和社交网站用户的活跃度。

好友推荐算法在社交网络上被称为链接预测(link prediction)。关于链接预测算法研究的代表文章是Jon Kleinberg的“Link Prediction in Social Network”。该文对各种用户好友关系的预测方法进行了系统地研究和对比。本节介绍其中一些比较直观和简单的算法。

6.4.1 基于内容的匹配

给用户推荐和他们有相似内容属性的用户作为好友。

常用属性如下：

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

利用内容信息计算用户的相似度和前面介绍的利用内容信息计算物品的相似度类似。

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

在Twitter和微博为代表的以兴趣图谱为主的社交网络中，用户往往不关心对于一个人是否在现实社会中认识，而只关心是否和他们有共同的兴趣爱好。因此，在这种网站中需要给用户推荐和他有共同兴趣的其他用户作为好友。

在第3章介绍基于用户的协同过滤算法(UserCF)时已经详细介绍了如何计算用户之间的兴趣相似度，其主要思想就是如果用户喜欢相同的物品，则说明他们具有相似的兴趣。

此外，也可以根据用户在社交网络中的发言提取用户的兴趣标签，来计算用户的兴趣相似度。关于如何分析用户发言的内容、提取文本的关键词、计算文本的相似度，可以参考第4章。

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

最简单的好友推荐算法是给用户推荐好友的好友。

下面介绍3中基于社交网络的好友推荐算法。
对于用户$u$和用户$v$，可以用他们共同好友比例计算他们的相似度：
$$
w_{out}(u,v) = \frac{\vert out(u) \cap out(v) \vert}{\sqrt {\vert out(u) \vert \vert out(v) \vert}}
$$

下面的代码实现了这种相似度：

def FriendSuggestion(user, G, GT):
    suggestions = dict() 
    friends = G[user] 
    for fid in G[user]:
        for ffid in GT[fid]:
            if ffid in friends:
                continue 
            if ffid not in suggestions:
                suggestions[ffid] = 0 
            suggestions[ffid] += 1 
    suggestions = {x: y / math.sqrt(len(G[user]) * len(G[x]) for x,y in suggestions}

$w_{out}(u,v)$公式中$out(u)$是在社交网络图中用户$u$指向的其他好友的集合。同理$in(u)$是在社交网络图中指向用户$u$的用户的集合。在无向社交网络图中，$out(u)$和$in(u)$是相同的集合。但在有向社交网络中，两个集合就不同了，因此可以通过$in(u)$定义另一种相似度：
$$
w_{in}(u,v) = \frac{\vert in(u) \cap in(v) \vert}{\sqrt{\vert in(u) \vert \vert in(v) \vert}}
$$

def FriendSuggestion(user, G, GT):
    suggestions = dict() 
    for fid in GT[user]:
        for ffid in G[fid]:
            if ffid in friends:
                continue 
            if ffid not in suggestions:
                suggestions[ffid] = 0 
            suggestions[ffid] += 1 
    suggestions = {x: y / math.sqrt(len(GT[user]) * len(GT[x]) for x,y in suggestions}

这两种相似度的定义有着不同的含义，用微博中的关注来解释这两种相似度。如果用户$u$关注了用户$v$，那么$v$就属于$out(u)$，而$u$就属于$in(v)$。因此，$w_{out} (u , v )$越大表示用户$u$和$v$关注的用户集合重合度越大，而$w_{in }(u, v) $越大表示关注用户$u$和关注用户$v$的用户的集合重合度越大。

前面两种相似度都是对称的，也就是也就是$w_{in} (u, v) = w_{in} (v, u )$，$w_{out} (u , v ) = w_{out} (v, u ) $。同时，我们还可以定义第三种有向的相似度：
$$
w_{out,in}(u,v) = \frac{\vert out(u) \cap in(v) \vert}{out(u)}
$$
这个相似度的含义是用户$u$关注的用户中，有多大比例也关注了用户v。但是，这个相似度有一个缺点，就是在该相似度的定义下所有人都和名人有很大的相似度。这是因为这个相似度在分母的部分没有考虑$|in(v)|$的大小。因此，可以用如下公式改进上面的相似度：
$$
w_{out,in}’(u,v) = \frac{\vert out(u) \cap in(v) \vert}{\sqrt{\vert out(u) \vert \vert in(v) \vert}}
$$

def FriendSuggestion(user, G, GT):
    suggestions = dict() 
    for fid in GT[user]:
        for ffid in G[fid]:
            if ffid in friends:
                continue 
            if ffid not in suggestions:
                suggestions[ffid] = 0 
    suggestions[ffid] += 1 suggestions = {x: y / math.sqrt(len(GT[user]) * len(GT[x]) for x,y in suggestions}

前面讨论的这些相似度都是基于一些简单计算公式给出的。这些相似度的计算无论时间复杂度还是空间复杂度都不是很高，非常适合在线应用使用。

离线实验

本节通过一些离线实验评测本节提出的几种相似度，评测哪种相似度能更好地预测用户之间的好友关系。实验详情见书。最终的结论是在实际系统中没有哪一种相似度公式绝对合适，只有在自己的数据集上对不不同的算法，才能找到最适合自己数据集的好友推荐算法。

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

对于前面3节提出的几种不同的好友推荐算法，上一节提到的GroupLen的Jilin Chen也进行了研究。他通过用户调查对比了不同算法的用户满意度(参见Jilin Chen、Werner Geyer、Casey Dugan Michael Muller、Ido Guy的“‘Make New Friends, but Keep the Old’ ——Recommending People on Social Networking Site”（CHI 2009）)。实验介绍和结果见书。

6.5 扩展阅读

社交网络分析的研究已经有很悠久的历史了。其中关于社交网络最让人耳熟能详的结论就是六度原理。六度原理讲的是社会中任意两个人都可以通过不超过6个人的路径相互认识，如果转化为图的术语，就是社交网络图的直径为6。不过喜欢刨根问底的读者一定好奇六度原理的正确性。六度原理在均匀随机图上已经得到了完美证明，对此感兴趣的读者可以参考Random Graph一书。很多对社交网络的研究都是基于随机图理论的，因此深入研究社交网络必须掌握随机图理论的相关知识。

社交网络研究中有两个最著名的问题。第一个是如何度量人的重要性，也就是社交网络顶点的中心度(centrality)，第二个问题是如何度量社交网络中人和人之间的关系，也就是链接预测。这两个问题的研究都有着深刻的实际意义，因此得到了业界和学术界的广泛关注。对这两个问题感兴趣的读者可以参考社交网络分析方面的书(比如（Social Network Analysis: Methods and Applications）和（Social Network Analysis: A Handbook）)。

对于基于社交网络的推荐算法，因为数据集的限制，最早的研究都是基于Epinion的用户信任网络的。Ma Hao在Epinion数据集上提出了很多基于矩阵分解的社会化推荐算法用来解决评分预测问题(参见Hao Ma、Haixuan Yang、Michael R. Lyu和Irwin King的“SoRec: Social Recommendation Using Probabilistic Matrix Factorization”（ACM 2008 Article , 2008）)，其主要思想是在矩阵分解模型中加入正则化项，让具有社交关系的用户的隐语义向量具有比较高的相似度。

ACM推荐系统大会在2010年曾经举办过一个社会化推荐比赛(即CAMRa201: Challenge on Context-aware Movie Recommendation )，该比赛将社交网络看做一种上下文，希望参赛者能够利用社交网络信息提高推荐系统的性能。关注社交化推荐的读者可以关注一下该比赛最后发出的论文集。

第6章 利用社交网络数据