基于XGBoost算法的社交网络链路预测

陈耀飞 王友国 朱亮

摘 要：提升链路预测精度是复杂网路研究的基础问题之一。传统基于局部信息相似性、基于全局信息相似性与基于随机游走相似性的链路预测都是基于单个相似性指标进行预测的，而没有充分利用这些相似性指标的综合信息。将链路预测问题看作机器学习中的二分类问题，将有连接的样本标签记为1，无连接的样本标签记为0，将基于局部信息、基于全局信息与基于随机游走相似性等15个指标作为样本特征。综合考虑以上信息，使用XGBoost算法，选取AUC作为模型评价准则，在facebook真实数据集上进行实验。结果表明，该算法在测试集上的AUC高于基于单个相似性指标链路预测的AUC。

关键词：链路预测; XGBoost;机器学习;社交网络

0 引言

随着网络时代的到来，社交网络已逐渐成为学者们研究的热点。作为网络科学领域的研究方向之一，链路预测是指通过已知与已观察到网络中的链接，预测给定网络中尚不存在的两个节点之间链接的可能性。链路预测既包含了对未知链接的预测，也包含了对未来链接的预测[1]。在计算机领域，已有不少学者针对链路预测进行深入研究，当前主要的链路预测方法是基于网络拓扑结构的链路预测方法，其可分为基于节点邻居相似性、基于最大似然估计及基于概率模型3种类型。在基于节点邻居相似性的链路预测中，具有代表性的算法有基于局部信息相似性的共同邻居算法、基于路径相似性的Katz算法与基于游走相似性的RWR算法。

Getoor等[1]把文档与单词之间的关系看作链路预测问题，通过观察到的链接与节点属性可以估计一个链接存在的最大可能性。之后，David & Kleinberg[2]首次定义了社交网络中的链路预测问题，并且在大规模共同作者网络数据集上进行实验，结果表明，关于未来交互的信息可以单独从网络拓扑中提取出来。社交网络中由于存在不准确信息，导致网络中存在虚假链接[3-4]，链路预测算法可用于发现网络中的虚假链接，还原真实网络[5]。链路预测不仅可以帮助分析网络中的缺失数据，还可用来发现网络演化过程中将来可能出现的链接[6-7]。O'Madahain等[8]提出局部条件概率模型，在进行预测时充分利用網络拓扑结构和节点属性等信息;Lin等[9]根据节点属性定义节点相似性，从而利用节点相似性进行预测。利用节点属性可以很好地进行预测，但节点属性信息很难获取，即使能获取到，也不能保证信息的真实性，如社交网络中很多用户的注册信息则不够真实。Linben等[10]基于网络拓扑结构分析了几种指标对社会网络中链路预测产生的效果;Clauset等[11]发现在具有明显层次结构的网络中，利用网络层次结构进行链路预测可取得不错的效果。基于相似性的方法是最基本且最具启发式的方法，通过利用相似性指标进行链路预测，如Adamic等[12]通过分配给较少的相连邻居更高权重，重新定义CN（Common Neighbor）为Adamic-Adar（AA）得分;Katz[13]基于所有路径集合，直接对所有路径求和，对于更长路径，通过指数衰减赋予更少权重得到Katz得分。还有一些其它相似性指标，包括资源分配指标（RA）[14]、Jaccard指标[15]、Sorensen指标[16]等。基于随机游走的相似性指标包括重启的随机游走（RWR）与余弦相似性（Cos+）。Mohammad等[17]通过使用有监督学习方法，分别在BIOBASE和DBLP两个数据集上进行测试，都取得了不错的效果;Backstrom等[18]提出有监督的随机游走算法，可以自然地将网络结构中边与节点级别的信息结合起来;吴祖峰等[19]使用有监督学习方法，使用Adaboost算法对arXiv 论文合作网络与电子邮件网络两个真实数据集进行测试，准确率和召回率都显著高于当时的主流算法。

基于相似性的链路预测是目前运用最多的链路预测算法，进行预测前首先需要计算两个节点之间的相似性，包括CN等基于局部信息的相似性指标、Katz等提出的基于全局信息的相似性指标、Cos+等基于随机游走的相似性指标。基于相似性的方法凭借其计算简单、速度快等优点吸引了很多学者关注，但该方法的缺点是只考虑单一相似性指标，而未综合考虑这3类基于不同信息的相似性指标。

本文在基于相似性的链路预测算法基础上，将链路预测问题看作机器学习中的二分类问题，使用有监督学习中的XGBoost算法[20]进行链路预测，从而综合考虑所有相似性指标信息，提高链路预测精度。

3 结语

本文基于XGBoost算法进行链路预测，与基于单相似性指标算法的链路预测不同，基于XGBoost算法的链路预测将链路预测问题看作机器学习中的二分类问题，模型训练时选取基于局部信息、基于全局信息与基于随机游走的相似性指标作为机器学习中的特征，考虑多个指标进行链路预测，并且使用AUC作为模型评价准则。经过实验发现，基于XGBoost的多个指标链路预测优于基于单个相似性指标的链路预测，而且综合考虑所有信息相似性指标后进行链路预测效果最好。链路预测可用于社交网络中的好友推荐，推荐准确度的提升可提高社交网站用户的忠诚度。

参考文献：

[1] GETOOR L， DIEHL C P. Link mining：a survey[J]. ACM Sigkdd Explorations Newsletter， 2005， 7（2）：3-12.

[2] LIBEN-NOWELL D， KLEINBERG J. The link-prediction problem for social networks[M]. New York：John Wiley & Sons， Inc. 2007.

[3] VON MERING C， KRAUSE R， SNEL B， et al. Comparative assessment of large-scale data sets of protein-protein interactions[J]. Nature， 2002， 417：399-403.

[4] BUTTS C T. Network inference， error， and informant （in）accuracy： a Bayesian approach[J]. Social Networks， 2003， 25（2）：103-140.

[5] GUIMERA R， SALES-PARDO M. Missing and spurious interactions and the reconstruction of complex networks[C]. Proceedings of the National Academy of Sciences， 2009， 106（52）：22073-22078.

[6] Lü L， ZHOU T. Link prediction in complex networks： a survey[J]. Physica A：statistical mechanics and its applications， 2011， 390（6）： 1150-1170.

[7] 吕琳媛. 复杂网络链路预测[J]. 电子科技大学学报，2010，39（5）：651-661.

[8] OMADADHAIN J，HUTCHINS J， SMYTH P. Prediction and ranking algorithms for event-based network data[C]. Proceedings of the ACM SIGKDD 2005. New York： ACM Press， 2005： 23-30.

[9] LIN D. An information-theoretic definition of similarity[C]. Proceedings of the 15th International Conference of Machine Learning，1998： 296-304.

[10] LIBEN N D，KLEINBERG J. The link-prediction problem for social networks[J]. Journal of American Soci Information Science Technology，2007，58（7）： 1019-1031.

[11] CLAUSET A，MOOR C，NEWMAN M E J. Hierarchical structure and the prediction of missing links in networks[J]. Nature，2008， 453： 98-101.

[12] ADAMIC L A，ADAR E. Friends and neighbors on the Web[J].  Social Networks，2003， 25（3）：211-230.

[13] KATZ L. A new status index derived from sociometric analysis[J].  Psychometrika，1953，18（1）：39-43.

[14] ZHOU T，LINYUAN Lü， ZHANG Y C. Predicting missing links via local information[J]. The European Physical Journal B，2009，71（4）：623-630.

[15] JACCARD P. étude comparative de la distribution ？orale dans une portion des Alpes et des jura[J]. Bull Soc Vaudoise Sci Nat， 1901， 37：547-579.

[16] S？RENSEN T. A method of establishing groups of equal amplitude in plant sociology based on similarity of species and its application to analyses of the vegetation on danish commons[J]. Biol. Skr， 1948， 5： 1-34.

[17] HASAN M A，CHAOJI V，SALEM S， et al. Link prediction using supervised learning[C]. The Proceedings of the Fourth Workshop on Link Analysis， Counterterrorism and Security， 2006.

[18] BACKSTROM L，LESKOVEC J. Supervised random walks： predicting and recommending links in social networks[C]. WSDM，2011.

[19] 吳祖峰，梁棋，刘峤，等. 基于AdaBoost的链路预测优化算法[J]. 通信学报，2014，35（3）：116-123.

[20] CHEN T，GUESTRIN C. XGBoost：a scalable tree boosting system[J]. KDD '16 Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2016：785-794.

（责任编辑：黄 健）