基于AdaBoost的链路预测优化算法

doi:10.3969/j.issn.1000-436x.2014.03.013

摘要/Abstract

摘要：

针对当前主流的基于网络拓扑结构的链路预测算法普遍存在召回率较低的问题，研究发现一些算法输出的结果中部分正确结果具有互补性，据此采用基于Boosting的集成学习方法对其进行改进。按照网络中节点之间是否存在链接关系，将链路预测问题定义为二分类问题，进一步遵循算法互补的原则选择若干具有代表性的链路预测算法作为弱分类器，基于AdaBoost算法提出并实现了一个新型链路预测算法。在arXiv论文合作网络和电子邮件网络等真实数据集上的实验结果表明，该算法的准确率以及召回率表现均显著优于当前的主流算法。

关键词: 链路预测, 社会网络分析, AdaBoost算法, 推荐系统, 机器学习

Abstract:

The mainstream of current link prediction algorithm based on network topology structure generally have the problem of low efficiency of recalls.Study found that the correct results from some of the link prediction algorithms are complementary,accordingly,the Boosting method was considered to improve it.According to whether there is a link relationship between the nodes,the problem was divided into two categories,thus the link prediction algorithm as a two classification problem was defined.Furthermore,the algorithm complementary principle to select a number of representative link prediction algorithms as weak classifiers was followed,and a novel link prediction algorithm based on the AdaBoost algorithm was come up.The experimental results on the data from real dataset like the arXiv paper cooperation network and E-mail network show that,the novel algorithm has a better accuracy than the current mainstream algorithms.

Key words: link prediction, social network analysis, AdaBoost algorithm, recommended system, machine learning

吴祖峰,梁棋,刘峤,秦志光. 基于AdaBoost的链路预测优化算法[J]. 通信学报, 2014, 35(3): 116-123.

Zu-feng WU,Qi LIANG,Qiao LIU,Zhi-guang QIN. Modified link prediction algorithm based on AdaBoost[J]. Journal on Communications, 2014, 35(3): 116-123.

图/表 9

表1

预测算法名称及公式"

算法名称	公式
CN	S_uv=\|Γ(u)∩Γ(v)\|
JC	$S_{u v} = \frac{\| Γ (u) \cap Γ (v) \|}{\| Γ (u) \cup Γ (v) \|}$
AA	$S_{u v} = \sum_{z \in Γ (u) \cap Γ (v)} \frac{1}{\log \| Γ (z) \|}$
RWR	S_uv=cWR_u?1+(1?c)e_v ,c=0.85

表1

图1

表2

图2

表3

图3

表4

图4

表5

参考文献 15

[1]	LIBEN-NOWELL D , KLEINBERG J . The link-prediction problem for social networks[J]. Journal of the American Society for Information Science and Technology, 2007,58(7): 1019-1031.
[2]	LESKOVEC J , BACKSTROM L , KUMAR R , et al. Microscopic evolution of social networks[A].[A]. Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[A]. Las Vegas,Nevada,USA, 2008. 462-470.
[3]	MYERS S A , LESKOVEC J . On the convexity of latent social network inference[J]. Threshold, 2010,9: 20.
[4]	SUN Y , BARBER R , GUPTA M , et al. Co-author relationship prediction in heterogeneous bibliographic networks[A]. Advances in Social Networks Analysis and Mining (ASONAM)[C]. Kaohsiung, 2011. 121-128.
[5]	LARS BACKSTROM J L . Supervised random walks:predicting and recommending links in social networks[A]. WSDM'11[C]. Hong Kong,China, 2011. 635-644.
[6]	CLAUSET A , MOORE C , NEWMAN M E J , et al. Hierarchical structure and the prediction of missing links in networks[J]. Nature, 2008,453(7191): 98-101.
[7]	LV L Y . Link prediction on complex networks[J]. Journal of University of Electronic Science and Technology of China, 2010,9: 5-39.
[8]	SCHAFER J L , GRAHAM J W . Missing data:our view of the state of the art[J]. Psychol Methods, 2002,7(2): 147-177.
[9]	CHOWDHURY G . Introduction to Modern Information Retrieval,Third Edition[M]. Facet Publishing, 2010.
[10]	ADAMIC L A , ADAR E . Friends and neighbors on the web[J]. Social Networks, 2003,25(3): 211-230.
[11]	TONG H H , FALOUTSOS C , PAN J Y . Fast random walk with restart and its applications[A]. Proceedings of the ICDM'06[C]. Washington,DC,USA, 2006. 613-622.
[12]	SHANG M S , LV L , ZENG W , et al. Relevance is more significant than correlation:information filtering on sparse data[J]. Europhys Lett, 2009,88(6): 68008.
[13]	POLIKAR R . Ensemble based systems in decision making[J]. IEEE Circuits and Systems Magazine, 2006,6(3): 21-45.
[14]	SCHAPIRE R E . The strength of weak learnability[J]. Machine Learning, 1990,5(2): 197-227.
[15]	BRADLEY A P . The use of the area under the ROC curve in the evaluation of machine learning algorithms[J]. Pattern Recognition, 1997,30(7): 1145-1159.

数据集名称	总文章(邮件)数	N	E	A	B
Hep-th	38 429	11 529	30 258	1 695	2 098
Cond-mat	42 551	27 655	116 147	2 353	5 896
Astro-ph	43 509	24 152	277 153	3 128	7 523
Hep-ph	39 945	13 636	86 800	2 366	3 174
Email-Net	127 989	53 671	123 914	2 635	3 503

ROC曲线下面积	算法名称
ROC曲线下面积	CN	JC	AA	RWR	ALP
Hep-th	0.57	0.56	0.58	0.52	0.64
Cont-Mat	0.61	0.53	0.58	0.53	0.68
Astro-ph	0.56	0.55	0.62	0.52	0.64
Hep-ph	0.59	0.55	0.58	0.54	0.64
Email-Net	0.56	0.50	0.56	0.55	0.60

ROC曲线下面积	算法名称
ROC曲线下面积	CN	JC	AA	RWR	W_uv	本文提出的算法ALP
Hep-th	0.52	0.55	0.59	0.54	0.63	0.72
Cont-Mat	0.53	0.55	0.58	0.55	0.60	0.70
Astro-ph	0.57	0.59	0.57	0.56	0.58	0.69
Hep-ph	0.57	0.59	0.58	0.53	0.61	0.71
Email-Net	0.53	0.52	0.51	0.53	0.64	0.71