基于排序学习的社会网络链接预测算法研究

刘 英, 郭景涛

(1.内蒙古大学 公共管理学院，内蒙古 呼和浩特 010010;2.内蒙古机电职业技术学院 信息与管理工程系，内蒙古 呼和浩特 010070;3.内蒙古大学 公共管理学院,内蒙古 呼和浩特 010010)



基于排序学习的社会网络链接预测算法研究

刘 英1，2*, 郭景涛3

(1.内蒙古大学 公共管理学院，内蒙古 呼和浩特 010010;2.内蒙古机电职业技术学院 信息与管理工程系，内蒙古 呼和浩特 010070;3.内蒙古大学 公共管理学院,内蒙古 呼和浩特 010010)

链接预测是大规模社会网络分析挖掘的重要研究内容之一，具有非常重要的应用前景.社会网络种类繁多，不同的网络链接类型往往需要不同的链接预测方法.为了满足用户的个性化需求并提高链接预测的性能，该文提出了一种基于排序学习的社会网络链接预测算法.该算法以传统的链接预测方法为基础，通过排序学习方法对不同的排序结果进行学习，从而得到具有最大准确性的综合排序列表.在综合排序列表的构建中，在每个排序列表中设置一个滑动窗口，通过对滑动窗口的维护每次迭代选出一个全局最优值，从而使得最终的排序列表是最优的.实验表明，该文提出的算法与相关的链接预测算法相比较具有更高的预测性能,能找出一个预测最准确的排序结果.

链接预测；排序学习；社会网络；监督学习

链接预测是大规模社会网络分析挖掘的重要研究内容之一，具有非常重要的应用前景[1].在电子商务网站中，通过对用户-商品二部图中潜在的链接进行预测，可以为用户推荐商品，在提高商品销售量的同时也提高了用户对网站的粘性[2].在社会网络服务中，通过用户间的链接进行预测可以进行相似用户的查询以及好友的推荐，而用户查询和好友推荐是社会网络服务最基本的服务内容[3].在随着时间演化的复杂网络中，通过分析网络中节点间的相似性，可以预测复杂网络的结构变化，从而为复杂网络动力学的研究提供基础[4].此外，在信息不完全的网络中，如移动通信网络，运营商只有用户间的通过记录网络，而没有用户的电话薄列表(即好友关系)，通过链接预测方法可以识别用户的好友,从而为服务的推广提供依据[5].

然而，上述链接预测方法往往适用于特定的社会网络.在不同的社会网络中，网络中的链接表示不同的含义，如电子商务推荐中的链接表示用户对商品的评价，社会网络服务中的链接表示用户间的好友关系，移动通信网络中的链接表示通话记录等.在具体的社会网络中，网络中的链接受网络环境的影响，具有不同的角色，因而需要不同的链接预测方法.基于上述原因，研究人员在链接预测时同时考虑多种指标(每种指标对应着相应的计算方法)，并采用非监督学习的方法对不同指标下的结果进行融合，如Borda方法[12]和马尔科夫序列[13]等.

本文在对社会网络中的链接进行预测时同时考虑多种指标，并采用有监督的机器学习方法对不同指标下的结果进行融合.为了满足用户的个性化需求并提高链接预测的性能，本文提出了一种基于排序学习的社会网络链接预测算法.该算法以传统的链接预测方法为基础，通过排序学习方法对不同的排序结果进行学习，从而得到具有最大准确性的综合排序列表.在综合排序列表的构建中，在每个排序列表中设置一个滑动窗口，通过对滑动窗口的维护,每次迭代选出一个全局最优值，从而使得最终的排序列表是最优的.

1 相基于排序学习的链接预测

在社会网络中，用户之间的链接有着不同的角色，如家庭成员、好友及同事等.通过对不同预测结果进行相关性分析可以得出如下结论：通过某种方法预测到的链接在另外一种算法中可能不会出现.本节采用有监督的排序学习方法对不同预测结果进行融合，在综合多种指标的优势下进行链接的预测.

在排序学习中，我们对α个排序器的结果列表集合R={r1,r2,…,rα}进行学习，从而得到最优的排序结果.算法的基本思想为：

(1) 对于每个排序器的结果列表ri，维持一个固定长度的滑动窗口，令滑动窗口的起点的索引为0，终点的索引为ρi，令f(ri)为ri中滑动窗口ρi内的正确预测的边的个数，即

(1)

(3) 对于R中除ri以外的所有列表rj，如果rj的滑动窗口ρj中含有rmax，那么移除rmax并相应的更新ρj的起点和终点索引值.

(4) 更新R中所有列表的f(ri)值.

(5) 重复第2至4步，直到最终的结果列表包含所需的结果个数T.

如果在进行排序学习前共包含α个排序器，最终得到的包含T个结果的列表为L，那么上述方法的目标是最大化结果列表中的正确预测个数，即

其中li∈{0,1}为L中第i个结果对应的预测结果.在上述方法中，每个结果只能预测一次，当某个预测结果第一次出现时，删除其在其他结果列表中的出现.该思想的依据是：最终的预测结果中的每一项都来自于其对应的最优排序器，这样使得最终的结果列表也是最优的.该算法的细节如下：

算法：RankLearn输入：R={r1，r2，…，rα}，排序列表集合；E，社会网络中的已知边；T，最终列表的长度；g，滑动窗口大小；输出：结果列表L；初始化阶段：∀i，w[i]←ri中的前g个链接；∀i，x[i]=w[i]∩E，ρ[i]=0，σ[i]=g；n=0；循环阶段：Whilen≤Tdoimax←x[i]的最大索引；L[n]=R[imax][ρ[imax]]；n=n+1；ρ[imax]=ρ[imax]+1；For∀ido Ifl[n]∈w[i]，thenw[i]=w[i]l[n]； Whilew[i]≤gdo l=R[i][σ[i]]； σ[i]=σ[i]+1； Ifl∉Lthenw[i]=w[i]+1； Endwhilex[i]=w[i]∩E；Endwhile

RankLearn算法的思想是，在每一次迭代中，在α个排序器的前g个链接中找出一个预测最准确的排序结果.为了实现上述思想，用wi作为排序器ri中包含前g个结果的滑动窗口，用x[i]作为wi中正确预测的链接个数.在选取了最佳的链接后，将其加入到结果列表L中，并更新滑动窗口的索引值.对于最优排序结果的计算，暴力搜索方法需要对所有的链接组合进行搜索，所需的时间复杂度为O(αN).本文通过局部搜索的方法寻找最优的结果列表，每个排序器列表访问一次，因此算法所需的时间复杂度仅为O(αN).

下面通过一个具体的实例对算法的执行过程进行阐述.给定rA和rB两个排序列表，令g=5，表1通过3个子表描述了算法的两次迭代过程.其中rA和rB两个列表中上部分边的出现概率大于下面的边，例如p(1,2)≥p(1,4)；当rA=(1,2)时，tp=0，这表明虽然边(1,2)出现的概率最大，但是在未来仍没有出现.初始时，在rA和rB中分别取长度为5的滑动窗口(见表1(a)中的灰度部分)，计算可得f(rA)=4和f(rB)=3，并选取(1,2)作为最终列表中的第一项.在第一次迭代过程中，删除rB中的(1,2)项(用下划线表示)并更新滑动窗口，此时有f(rA)=4和f(rB)=4.在第二次迭代过程中，删除rA中的(5,18)项，更新滑动窗口，并将(5,18)加入到最终的排序列表中.经过两次迭代后，排序列表L={(1,2),(5,18)}.

表1 排序学习算法的实例

Tab.1 Instance of sort learning algorithm

2 实验结果与分析

2.1 数据集与评价指标

实验采用公开的DBLP[14]社会网络数据集.DBLP数据集是学者学术合作数据集，包含1990年至2004年间关于计算机领域的学术文章发表情况.该数据集包含540 459篇发表的文章以及1 564 617个作者.在实验过程中，应用1990年至2000年共11年的数据作为训练数据，并用余下4年的数据作为测试算法性能的数据.

在评价算法的性能时，采用了信息检索领域常用的评价指标，包含查准率、召回率和F值，关于这些指标的详细定义可参见文献[15].

2.2 对比算法

为了评价RankLearn算法的性能，实验将RankLearn与一些经典的链接预测算法进行了对比.

Borda算法[12]：该算法将不同排序方法得到的结果进行融合，采用投票的方法以便在结果中达成共识，是一种非监督的学习方法.

最近邻算法(Nearest Neighbors，NN)：NN算法是一种简单的基于局部链接结构的方法，该算法通过节点的最近邻来计算节点间的相似性.

AdaBoost(AB)算法[7]：AB算法是一种迭代算法，其核心思想是针对同一个训练集训练不同的弱分类器，然后把这些弱分类器集合起来，构成一个更强的最终分类器.

分类树算法(Classification Trees，CT)[9]：CT算法通过决策树思想构建一个分类器，并应用得到的分类器对链接进行预测.

2.3 实验结果

首先，通过实验分析了上述5种算法在链接预测时的整体性能.在实验中，令RankLearn算法的g=300，关于g的取值的分析见下文.在实验结果的展示中，预测结果的查询率-召回率分布如图1所示.从图中可以看出，当要求预测结果的召回率很小时，AB算法具有最高的查准率，然而由于召回率低导致大部分正确结果没有被返回.当召回率逐渐提高时，RankLearn和Borda算法的曲线始终处于右上方，这表明这两种算法具有更好的检索性能.此外，在RankLearn和Borda的对比中，RankLearn算法的检索性能要优于Borda算法.

接下来，通过改变算法返回的预测结果个数来观察不同算法的F值变化，实验结果如图2所示.由于F值综合考虑了检索结果的查准率和召回率，因而能代表检索结果的性能.同样令RankLearn算法的g=300，从该图中可以看出，RankLearn和Borda算法的曲线始终处于其他三种算法的上方，并且RankLearn算法处于Borda算法的上方，因而可以认为RankLearn算法的检索性能是最好的，Borda算法次之.

最后，通过实验分析了RankLearn算法的滑动窗口大小g对算法性能的影响.在图3和图4中，横轴为滑动窗口的大小g，纵轴为RankLearn算法的F值相对于Borda算法的F值的提高百分比，负值表示RankLearn算法的F值 低于Borda算法的F值.图3和图4分别为RankLearn算法在训练数据集和测试数据集中相对于Borda算法的性能提高程度.从这两幅图中可以看出，无论在训练数据集还是测试数据集上，RankLearn算法的F值相对于Borda算法都有所提高，并且在200至400处取到最大值.

3 结束语

链接预测是大规模社会网络分析挖掘的重要研究内容之一，然而社会网络种类繁多，不同的网络链接类型往往需要不同的链接预测方法.本文在对社会网络中的链接进行预测时同时考虑多种指标，采用有监督的机器学习方法对不同指标下的结果进行融合，提出了一种基于排序学习的社会网络链接预测算法.该算法以传统的链接预测方法为基础，通过排序学习方法对不同的排序结果进行学习，从而得到具有最大准确性的综合排序列表.在综合排序列表的构建中，在每个排序列表中设置一个滑动窗口，通过对滑动窗口的维护每次迭代选出一个全局最优值，从而使得最终的排序列表是最优的.实验表明，本文提出的算法与相关的链接预测算法相比较具有更高的预测性能.

[1] 胡海波, 王科, 徐玲, 等. 基于复杂网络理论的在线社会网络分析[J]. 复杂系统与复杂性科学, 2008, 5(2): 1-14.

[2] 朱岩, 林泽楠. 电子商务中的个性化推荐方法评述[J]. 中国软科学, 2009 (2): 183-192.

[3] 张中峰, 李秋丹. 社交网站中潜在好友推荐模型研究[J]. 情报学报, 2012, 30(12): 1 319-1 325.

[4] 武南南. 时变网络的链接预测研究[D].重庆： 重庆大学, 2012.

[5] JANICIK G A, LARRICK R P. Social network schemas and the learning of incomplete networks[J]. Journal of Personality and Social Psychology, 2005, 88(2): 348.

[6] LIBEN-NOWELL D, KLEINBERG J. The link-prediction problem for social networks[J]. JASIST, 2007, 58(7):1 019-1 031.

[7] Al HASAN M, CHAOJI V, SALEM S, et al. Link prediction using supervised learning[C]. SDM’06: Workshop on Link Analysis, Counter-terrorism and Security, 2006.

[8] BROUARD C, SZAFRANSKI M. Semi-supervised penalized output kernel regression for link prediction[C]. Proceedings of the 28th International Conference on Machine Learning (ICML-11), 2011: 593-600.

[9] FENG X, ZHAO J C, XU K. Link prediction in complex networks: a clustering perspective[J]. The European Physical Journal B,2012, 3(85):1-9.

[10] MENON A K, ELKAN C. Machine learning and knowledge discovery in databases[M]. Springer Berlin Heidelberg, 2011:437-452.

[11] LIU W, LÜ L. Link prediction based on local random walk[J]. EPL (Europhysics Letters), 2010, 89(5): 58 007.

[12] DWORK C,KUMAR R,NADR M, et al. Rank aggregation methods for the web[C].In WWW’01, ACM, 2001：613-622.

[13] 陈彦萍, 李增智, 唐亚哲, 等. 一种满足马尔可夫性质的不完全信息下的 Web 服务组合方法[J]. 计算机学报, 2006, 29(7): 1 076-1 083.

[14] Al HASAN M, CHAOJI V, SALEM S, et al. Link prediction using supervised learning[C]. SDM’06: Workshop on Link Analysis, Counter-terrorism and Security,2006.

[15] MANNING C D, RAGHAVAN P, SCHÜTZE H. Introduction to information retrieval[M]. Cambridge: Cambridge University Press, 2008.

[16] 曹建芳,陈俊杰,杨灿.面向自然语言理解的图像情感语义检索[J].湘潭大学自然科学学报,2014,29(2):81-85.

责任编辑：龙顺潮

Learning to Rank Based Link Prediction Algorithm in Social Networks

LIUYing1，2*，GUOJing-tao3

(1.Public Management College,Inner Mongolia University, Hohhot 010010;2.Information Technology and Management Engineering Department,Inner Mongolia Technical College of Mechanics and Electrics，Hohhot 010010;3.Public Management College,Inner Mongolia University,Hohhot 010010 China)

Link prediction is one of the most important research issues for mining and analyzing large-scale social networks, and is ubiquitous in many applications. There are kinds of social networks, and different types of link need different methods for link prediction. In order to satisfy personalized user requests and improve the performance of link prediction, this paper proposed a learning to rank based link prediction algorithm in social networks. Based on traditional link prediction methods, the proposed algorithm tried to learn a final list with maximized accuracy from existing ranking list. On the constructing of the final list, we set and maintained a slide window for each ranking list, and at each iteration, chose a global optimum from all slide windows, which made sure that the final list was optimum. The experiments show that, the proposed algorithm has better performance in link prediction than related works.

link prediction; learning to rank; social networks; supervised learning

2015-02-08

内蒙古自治区教育厅课题(NJ274)

刘英(1981— ),女，内蒙古 乌兰察布人，讲师.E-mail:478345761@qq.com

TP319

A

1000-5900(2015)03-0120-07