引用本文
俞琰, 邱广华, 陈爱萍. 基于混合图的在线社交网络朋友推荐算法. 现代图书情报技术, 2011, 27(11): 54-59
Yu Yan, Qiu Guanghua, Chen Aiping. Friend Recommendation Algorithm Based on Mixed Graph in Online Social Networks. 现代图书情报技术, 2011, 27(11): 54-59  
Permissions
Copyright©2011, 《现代图书情报技术》编辑部
《现代图书情报技术》编辑部
基于混合图的在线社交网络朋友推荐算法
俞琰1,2, 邱广华1,3, 陈爱萍4
1南京航空航天大学经济管理学院 南京 210016
2东南大学成贤学院计算机系 南京 210088
3美国宾州州立大学信息科学系 马尔文 19355
4金陵科技学院信息技术学院 南京 210069
摘要

针对在线社交网络朋友推荐问题,尝试融合多个社会网络为一个混合图模型,采用基于混合图模型的重启动随机游走算法,为用户提供个性化的朋友推荐,并通过参数调节多个网络的权重。实验表明,该算法提高了在线社交网络朋友推荐的准确性。

关键词: 在线社交网络; 朋友推荐; 重启动随机游走
中图分类号:TP393
Friend Recommendation Algorithm Based on Mixed Graph in Online Social Networks
Yu Yan1,2, Qiu Guanghua1,3, Chen Aiping4
1College of Economics and Management, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
2Computer Science Department, Southeast University Chenxian College, Nanjing 210088, China
3Information Science Department, Pennsylvania State University, Malvern 19355, USA
4School of Information Technology, Jinling Institute of Technology, Nanjing 210069, China
Abstract

Aiming at the friend recommendation in online social networks, this paper tries to fuse multiple social networks into one mixed graph on which the random walk with restart is implemented to provide personalized friend recomendation for users． The different roles of these networks are adjusted by parameters． Experiment demonstrates that this algorithm can improve the accuracy of friend recommendation in online social networks．

Keyword: Online social networks; Friend recommendation; Random walk with restart
1 引 言

近年来,在线社交网络（Online Social Networks, OSNs）逐渐流行,如Facebook、MySpace等吸引了成千上万的用户,已经成为当今构建朋友关系和分享信息的主要平台之一。在OSNs中,朋友推荐是一个关键性的任务,在提高用户体验和促进网络增长等方面起着重要的作用[ 1]。

（1）OSNs已经成为一个巨大的信息源,并以非常迅猛的速度扩展。在这样不断变化并且增长的信息源中寻找和用户具有相同兴趣的用户,也就找到了用户想要的信息源。

（2）朋友推荐满足了用户的心理需求。研究显示,用户使用OSNs不仅可以联系已经认识的人,在特定的背景下也希望发现他们所不知道的有价值的联系[ 2],表达思想,分享经历和观点。

（3）寻找相同兴趣的用户是商业项目推荐的关键。利用兴趣相同的朋友,推荐用户潜在有趣的服务项目（如新闻、游戏、广告和产品等）,能够提高用户参与的满意度,增加社交网站的收入。

（4）对于学术型OSNs,推荐系统能够促进科学研究,鼓励领域传播合作,以更有效地利用资源[ 3]。

（5）在企业环境中,推荐也是知识交换的关键。

推荐系统正逐渐被知识集中的大型组织的OSNs所采用,帮助组织中的用户彼此联系,交换知识。

针对这一问题,本文尝试融合多个社会网络为一个混合图模型,采用基于混合图模型的重启动随机游走算法为用户推荐朋友。

2 相关工作

对于OSNs设计者来说,面对大量在线用户、稀疏的用户关系以及他们的多样性,如何帮助用户发现新的有趣的朋友是一个大的挑战,而目前相关的研究还较少[ 4]。Twitter的“Find Friends”标签提供了发现已经存在的朋友的机制,不同于此,本文关注人们彼此之间可能不知道但具有类似兴趣的人的推荐。Twitter的“Suggestions”标签显示流行的Twitter用户列表。但是,这些推荐可能对于特定的个体没有用,因为个体需要的信息可能不同于这些流行用户所提供的信息[ 5]。本文针对的是为每一位用户提供个性化的推荐。

目前的推荐方法基于一个假设：两个用户越相似,则他们越有可能成为朋友。有三种主要的方法刻画用户的相似度：基于用户的属性特征、基于网络结构的局部特性和基于网络结构的全局特性。

（1）基于用户属性的方法进行朋友推荐的思想是如果两个用户具有相同的年龄、性别、学校或者地点等,则他们更加相似,也就更加可能成为朋友。如WhoShouldFollow通过用户的地点进行过滤,发现类似的用户;人人网的一种好友推荐根据用户学校、专业或者相近地点进行推荐。

（2）基于网络结构局部特征的方法利用用户朋友网络结构的局部结构信息。有很多局部相似性测量指标,如共同邻居（Common Neighbor,CN）、Jaccard和Adamic/Adar等。CN也叫FOAF算法,被很多流行的OSNs所采用,如Facebook、Hi5。它考虑两个顶点的共同邻居的数量,如果两个用户的共同朋友越多,则他们越可能形成链接。设Γ（x）表示顶点x的邻居的集合,|Γ（x）|表示x的度,则使用CN描述顶点x和顶点y的相似性为：sxy=|Γ（x）∩Γ（y）|。Jaccard方法不仅考虑了共同邻居的数量,还考虑到两个用户共同拥有的邻居的数目,即sxy=|Γ（x）∩Γ（y）|/|Γ（x）∪Γ（y）|。Adamic/Adar也考虑两顶点共同邻居的度信息,并且认为度小的共同邻居节点的贡献大于度大的共同邻居节点,根据共同邻居顶点的度为每个顶点赋予一个权重值,该权重等于该顶点的度的对数的倒数, sxy= 。一些研究表明, Adamic/Adar在局部特性指标中具有最好的性能[ 6]。

（3）基于网络全局特征方法侦测朋友网络的所有路径的结构,其中Google网页排序算法PageRank的拓展应用重启动随机游走算法（Random Walk with Restart,RWR）吸引了很多研究领域学者的兴趣[ 1, 7, 8]。相比于其他的相似性度量方法, RWR方法具有捕捉图形全局结构以及顶点之间多侧面关系等优点[ 9]。RWR算法是一个基于图的随机游走马尔科夫链模型。Yin等提出LINKREC框架,集成网络和属性信息,使用RWR算法推荐朋友[ 1]。

上述方法仅利用OSNs中用户朋友网络信息。而在OSNs中常常包含多种对象和网络关系。例如,在一个典型的学术类型的OSNs中有5位用户u1至u5,如图1所示：

图1 OSNs中多种对象、多种关系示例

其中, u1,u5是朋友,形成朋友关系。u2在u3的个人空间留言,构成用户留言关系。u5访问u2的个人空间,形成用户访问关系。u4引用u3博客构成用户博客引用关系。u1和u5参加科学史兴趣圈, u2和u3参加摄影圈,构成用户圈子关系。u1、u2、u5为信息科学专业, u3、u4为材料科学专业,形成用户专业关系。根据同质性原则,类似的背景和行动促进包括朋友关系在内的各种关系的形成[ 5]。OSNs中的这些丰富信息能够形成一个关于用户兴趣和用户所从事活动的更加准确的描述,从而提高朋友推荐的质量[ 10]。

一些研究已开始利用多个网络信息进行朋友推荐,如IBM的SONAR[ 10]以及MITREverse上的推荐服务[ 11]。这些研究的推荐方法是根据每个数据来源,分别计算每对用户的相似性,再使用平均或Bayesian Noisy-MAX函数等方法合成这些相似性,形成最终的每对用户的相似值。

相比于上述方法,本文扩展了单个朋友网络关系形成的图,自然地融合多种对象和关系为一个混合图,在此基础上使用RWR算法,并讨论了多个关系的权重。最后使用真实数据验证了算法的有效性。

3 基于混合图的朋友推荐算法

算法首先构建混合图模型,然后使用基于图模型的重启动随机游走算法计算用户的相似程度。由于各个网络在朋友推荐中的作用不同,所以还讨论了网络权重的调节。最后给出算法流程。

3.1 混合图模型构建

算法的第一个关键问题是构建一个有意义的图,使得结果能够真实反映用户间的相似性。本文定义一个混合图,融合多种对象和多种关系。具体地,混合图G=（V,E）, 其中V为顶点集合。顶点包含三种类型顶点：VU、VC和VA。VU为用户顶点集合, VC为用户参加的圈子顶点集合, VA表示专业顶点集合。即V=VU∪VC∪VA。E为边的集合,包含6种类型的边： EUUF、EUUV、EUUW、EUUC、EUA、EUC,即E=EUUF∪EUUV∪EUUW∪EUUC∪EUA∪EUC。EUUF为OSNs中用户之间的朋友关系集合,如果用户u1和用户u2是朋友关系,则在u1和u2之间存在一条朋友关系边。EUUV是用户互访问关系集合,若u1访问u2的OSNs空间,则产生一条从u1到u2的弧。EUUW表示用户留言关系集合,当u1在u2的留言墙上留言,则有一条从u1 指向u2的弧。EUUC表示用户之间博客的引用关系,若u1引用u2博客,则有一条从u1指向u2的弧。EUA则为用户专业边集合,若u1为计算机专业a1,则在u1和a1之间建立一条边。EUC代表用户圈子关系集合,若用户u1参加了摄影圈c1, u1和c1之间有一条边。由于有的关系是有向的,有的是无向的,因此统一为一个有向图,无向边表示为两条有向弧。图1对应的混合图如图2所示：

图2 图1对应的混合图示例

3.2 算法设计

得到混合图模型后,采用RWR算法计算用户之间的相似性。RWR的思想是从图中某个顶点出发,沿着图中的边随机游走。在任何点上,算法以一定的概率随机选择与该顶点相邻的边,沿这条边到下一个顶点,或者以一定的概率返回到出发顶点。经过有限次随机游走过程,达到图中每个顶点的概率值到达平稳分布,再次迭代不会改变图中的概率分布值。直观地,对于个性化的朋友推荐,从需要得到推荐的用户顶点（目标顶点）出发,离目标顶点越“近”的顶点越容易到达,稳定概率越大。因此可以用稳定概率衡量用户相似程度。RWR的数学表达式[ 7]如下：

p（t+1）=（1-α）Sp（t）+αq （1）

其中, p（t）、p（t+1）和q是列向量。p（t）表示第t步图中的概率分布, 表示第t步到达顶点i的概率。列向量q为重启动向量,表示初始状态, qi表示出发顶点为顶点i的概率。列向量q中取目标用户顶点值为1,其余为0。S是转移概率矩阵,它的元素si,j表示当前在顶点i,下一步到达顶点j的转移概率,α为直接回到出发顶点的概率。概率分布使用式（1）计算。它在图的随机游走过程中被执行。重复迭代,直到p收敛,得到目标用户顶点到图中其他各个顶点的稳定顶点概率分布。

3.3 权重调节

在决定朋友推荐的时候,多种网络的作用可能是不同的,因此权重也不同。本文定义不同种类网络之间的转移概率调节各种网络关系的权重。具体地,当随机游走到用户顶点的时候,用户进入用户专业关系、用户朋友关系、用户留言关系、用户访问关系、用户博客引用关系、用户圈子关系的概率分别为λUA、λUUF、λUUW、λUUV、λUUB、λUC。

根据转移概率理论,需要满足如下条件：

λUA+λUUF+λUUW+λUUV+λUUB+λUC=1 （2）

在混合图中,整个网络转换为转移矩阵S,元素si,j表示从顶点i到顶点j的转移概率。当在用户顶点的时候,对于下一步跳跃,有三种选择：用户顶点、专业顶点或者圈子顶点。当从用户顶点转移到用户顶点的时候,由于用户顶点之间有4种关系：用户朋友关系、用户留言关系、用户访问关系和用户博客引用关系,所以转移概率计算公式如下：

si,j=λUUF/ （i）+λUUW/ （i）+λUUV/ （i）+

λUUB/ （i） i,j∈VU （3）

其中, （i）、 （i）、 （i）、 （i）分别表示顶点i在用户朋友关系、用户留言关系、用户访问关系、用户博客引用关系的出度。

当从用户顶点转移到专业顶点时,转移概率计算公式如下：

si,j=λUA/ （i） i∈VU,j∈VA （4）

其中, （i）表示顶点i在用户专业关系中的出度。

当从用户顶点转移到圈子顶点时,转移概率计算公式如下：

si,j=λUC/ （i） i∈VU,j∈VC （5）

其中, （i）表示顶点i在用户圈子关系中的出度。

当处于专业顶点或者圈子顶点的的时候,只能转移到用户顶点,所以转移概率分别如下所示：

si,j=1/d+（i） i∈VA,j∈VU （6）

si,j=1/d+（i） i∈VC,j∈VU （7）

其中,d+（i）表示专业顶点或圈子顶点i的出度。

3.4 算法设计

OSNs朋友推荐算法如下：

输入：混合图G（V= VU∪VC∪VA,E=EUUF∪EUUV∪EUUW∪EUUC∪EUA∪EUC）,目标用户u, 重启动概率参数α,网络权重调解参数λUA、λUUF、λUUW、λUUV、λUUB、λUC。

输出：按降序排名的用户u的候选朋友列表。

构造重启动向量q,用户顶点u对应元素设置为1,其余元素为0。

初始化用户u在图中的初始概率分布p（0）=q。

根据式（3）-（7）建立转移概率矩阵S。

根据式（1）迭代更新p（t）和p（t+1）,直到收敛为止。

计算得到稳定状态向量,移走已经和用户u是朋友的用户顶点,按照降序排序稳定状态向量中的用户顶点。

End

算法分别构造了式（1）中的q,p（0）和S,利用式（1）迭代计算p（t）,直到p（t）的变化小于某个阈值。得到的向量为用户u到其他用户顶点的概率,即相似性。从稳定状态向量中排除已经和u是朋友的用户顶点,并按照降序输出用户顶点。

4 实 验
4．1 数据集和评估方法

为了测试提出算法的有效性,从科学网抽取数据,进行评价。科学网是综合性科学网站,为用户提供快捷权威的科学新闻报道、丰富实用的科学信息服务以及交流互动的网络平台,是具有一定影响力的全球华人科学社区。本文编写爬虫程序收集了2011年6月2日前的所有用户以及各种关系的信息。数据集包含8 182位注册用户,8个专业,66个圈子,58 116个朋友关系,5 513个引用关系,30 396个最近访问,13 330条最近留言。根据4折交叉验证,数据分为4个不同的集合,每次实验中,3/4的数据作为训练集,剩下的为测试集。

评估指标采用P@K和MRR。查准率Precision表示推荐的项目中正确的推荐所占的比例。P@K表示前K个推荐的Precision值,计算公式如下：

P@K=

（8）

实际中用户不注意低排名的推荐结果,而是更加关心高排名结果的相关性,高排名结果的性能应该更加重要。因此,重点测试排序在前面的2、5、10推荐的准确性,即P@2、P@5和P@10。平均倒数排名（Mean Reciprocal Rank,MRR）表示用户真实的朋友在推荐列表中的位置倒数的平均值, MRR越高说明算法的准确率越高。计算公式如下：

MRR=

（9）

4．2 实验与实验结果

（1）测试重启动概率α对算法性能的影响

设置第一组λUC=0．1、λUA=0．1、λUUF=0．5、λUUW=0.1、λUUB=0．1、λUUV=0．1;第二组λUC=0．1、λUA=0．1、λUUF=0．4、λUUW=0．1、λUUB=0．1、λUUV=0．2;第三组λUC=0．1、λUA=0．1、λUUF=0．3、λUUW=0．2、λUUB=0．1、λUUV=0．1。在三组λ的组合下,α对MRR的影响如图3所示：

图3 α对MRR的影响

可以看出,随着α的逐渐增大,性能总体均呈现缓慢的下降。当α=0．1的时候,朋友推荐的质量最佳。此处仅显示了三组λ参数组合的结果,其他参数组合结果类似。α为重启动概率,表示在每一次的随机游走的过程中,游走重新返回到初始顶点的概率。一些类似的研究发现,大的重启动概率意味着局部性而非整体性,用于朋友推荐是合适的[ 1];小概率的重启动概率在其他一些应用领域性能更佳,如个人搜索和查询建议等。这同随机游走的图本身的结构有关系。在实验中使用的是科学网,用户更加倾向于和一些有名的科学家链接成为朋友,使得用户的个性化被削弱,而更加体现整体全局性。

（2）朋友关系权重λUUF对算法质量的影响

α设定为0．1, λUC、λUA、λUUF、λUUW、λUUB、λUUV平分剩下的权重。λUUF对性能MRR的影响如图4所示：

图4 λUUF对MRR的影响

可以看出,随着λUUF的增加, MRR也随着逐渐增加,当λUUF到达0．5时, MRR到达最大值。之后,随着λUUF的增加, MRR逐渐减少。当朋友关系权重λUUF=0．5的时候, MRR的性能最佳,此时其他几个网络关系的权重为0．1。这说明朋友关系对于朋友推荐起着最为重要的作用,但是,加入其他一些信息,能够提高推荐的性能。

（3）对提出的算法和其他一些方法进行性能比较

使用NMRWR表示本文提出的没有考虑网络权重的混合图随机游走算法,即认为每个网络的重要性是一样的, MRWR表示考虑了权重的混合图随机游走算法。实验将NMRWR,MRWR分别和基于单一用户朋友网络的方法CN、Jaccard、Adamic/Adar、RWR和LINKREC[ 1]方法以及基于多个网络关系的SONAR[ 10]进行比较。其中, CN为基于网络结构的局部特性指标,根据两个用户的共同朋友的数目测量用户间的相似性。Jaccard不仅考虑了共同朋友的数量,还考虑到两个用户拥有的邻居的数目对相似性的影响。Adamic/Adar也考虑两个顶点共同邻居的度信息,并认为度小的共同邻居顶点的贡献大于度大的共同邻居顶点。RWR为单一朋友关系构成的重启动随机游走,它是基于网络结构全局特性的方法。LINKREC是融合了图结构和属性的重启动随机游走。本实验使用用户的朋友网络形成的图结构以及用户的专业作为属性特征。SONAR利用多个数据源形成的网络,分别计算两个用户的相似性,再根据权重获得两个用户最终的相似性。本文考虑6种网络关系：用户朋友网络、用户留言网络、用户访问网络、用户博客引用网络、用户专业网络和用户圈子网络。每个网络形成邻接矩阵,根据向量夹角余弦,分别计算两个节点的相似性,使用平均值求出两个顶点最终的相似性。实验中参数如下设置以获得最佳性能：RWR、LINKREC、NMRWR、MRWR的重启动概率参数α=0．1,MRWR中参数λUA、λUUF、λUUW、λUUV、λUUB、λUC分别为0.1、0.5、0.1、0.1、0.1、0.1。

几种方法在科学网数据集上的朋友推荐的精确性和MRR如表1所示：

表1 各种方法性能比较

表1中各种方法推荐精确性对应的图形化如图5所示：

图5 各种方法的准确率比较

在基于单一用户朋友网络的朋友推荐的5种方法（CN、Jaccard、Adamic/Adar、RWR和LINKREC）中, RWR精确性（P@2为26．74％,P@5为24．71％,P@10为18.97％）最佳, LINKREC的MRR（16．44％）最高。总体来看,重启动随机游走相关的RWR和LINKREC工作良好。这说明相比于基于网络局部特性的方法,重启动随机游走能够捕捉到图形的全局结构以及顶点之间的多侧面关系。但是,这5种方法均逊于NMRWR和MRWR算法。MRWR比较于RWR方法, P@2、P@5、P@10分别提高了70％,38％和21％;MRWR在MRR上比LINKREC提高了91％。这说明了结合多个网络信息能够更加准确地洞察用户的兴趣和所从事的活动,从而提高推荐的质量。结合多网络信息的SONAR性能并不理想,甚至低于仅仅使用单一网络信息的方法。这意味着如何有效地使用多个网络信息在朋友推荐中起着关键性的作用。相比于NMRWR,因为考虑了不同网络对推荐工作的权重, MRWR的性能进一步提高, P@2、P@5、P@10和MRR均到达了最佳（45.45％, 34．18％, 22.91％, 31．40％）,相比于其他网络关系,用户朋友关系对于推荐工作起了最重要的作用。

5 结 语

现实的OSNs中常常包含多种网络对象,呈现复杂的关系。而传统的OSNs朋友推荐仅仅考虑一种网络,或者只是将多个网络进行简单的集成,忽略了网络之间对象的依赖关系。如何充分利用网络中的多种对象、关系对于OSNs系统设计者来说是一个挑战。本文结合丰富的异构网络资源信息,提出了混合图模型推荐算法,进行朋友推荐。真实数据集上的实验验证了本算法的有效性,并且该方法是领域独立的,它易于扩展,能够处理不同的OSNs应用。

The authors have declared that no competing interests exist.

作者已声明无竞争性利益关系。

参考文献
[1] Yin Z J, Gupta M, Weninger T, et al. LINKREC: A Unified Framework for Link Recommendation with User Attributes and Graph Structure[C]. In: Proceedings of the 19th International Conference on World Wilde Web. New York: ACM Press, 2010: 1211-1212. [本文引用:5]
[2] DiMicco J, Millen D R, Geyer W, et al. Motivations for Social Networking at Work[C]. In: Proceedings of the 2008 ACM Conference on Computer Supported Coorperative Work. New York: ACM Press, 2008: 711-720. [本文引用:1]
[3] Huang Y, Contractor N, Yao Y. CI-KNOW: Recomendation Based on Social Networks[C]. In: Proceedings of the 9th Annual International Digital Government Research Conference. USA: Digital Government Society of North Americal, 2008: 27-33. [本文引用:1]
[4] Leskovec J, Lang K J, Mahoney M W. Empirical Comparision of Algorithms for Network Community Detection[C]. In: Proceedings of the 19th International Conference on World Wide Web. New York: ACM Press, 2010: 631-640. [本文引用:1]
[5] Golder S A, Yardi S, Marwick A, et al. A Structural Approach to Contact Recommendations in Online Social Networks[C]. In: Proceedings of the Social Media at ACMSIGIR Conference on Information Retrieval. New York: ACM Press, 2009: 11-14. [本文引用:2]
[6] Liben-Nowell D, Kleinberg J. The Link-Prediction Problem for Social Networks[C]. In: Proceedings of the 12th International Conference on Information and Knowledge Management(CIKM). New York: ACM Press, 2003: 556-559. [本文引用:1]
[7] Konstas I, Stathopoulos V, Jose J M. On Social Network and Collaborative Recommendation[C]. In: Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM Press, 2009: 195-202. [本文引用:2]
[8] Pan J Y, Yang H J, Faloutsos C, et al. Automatic Multimedia Cross-modal Correlation Discoery[C]. In: Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2004: 653-658. [本文引用:1]
[9] Xia J, Caragea D, Hsu W H. Bi-relational Network Analysis Using a Fast Rand om Walk with Restart[C]. In: Proceedings of the 9th IEEE International Conference on Data Mining. USA: IEEE, 2009: 1052-1057. [本文引用:1]
[10] Gertner A, Gaimari R, Richer J, et al. Contact Recommendation from Aggegrated On-Line Activity[C]. In: Proceedings of the Intelligent Techniques for Web Personalization and Recommender Systems. Big Island of Hawaii: ITWP, 2010: 44-52. [本文引用:3]
[11] Guy I, Ronen I, Wilcox E. Do You Know? Recommending People to Invite into Your Social Network [C]. In: Proceeclings of the 13th International Conference on Intelligent User Interfaces. New York: ACM Press, 2009: 77-86. [本文引用:1]