基于数据挖掘的网络链接预测研究

doi:10.3969/j.issn.1671-1122.2017.06.005

摘要/Abstract

摘要： 近年来社交网络日益火热,基于社交网络的数据挖掘也随之兴起。链接预测作为网络数据挖掘的重要课题,其借助已知的网络结构等信息来预测和估计尚未链接的两个节点间存在链接的可能性。社交网络的链接预测可以用于好友推荐,过滤冗余信息,提高用户的满意度、忠诚度,建立一个健康的社交网络环境。已有的链接预测算法集中研究网络结构信息或网络节点属性,以分析网络全局或局部特性。文章考虑到微博社交网络的本质,提出了融合多特征的链接预测方法,其中包括节点特征、拓扑特征、社交特征以及投票特征。基于这些特征,在微博社交网络数据上应用SVM、朴素贝叶斯、随机森林和逻辑回归4种机器学习算法训练预测模型,预测潜在的社交链接。结果表明,文章提出的组合特征相对于传统特征表现更好,且融合多种特征能够提高最终的预测精度。

关键词: 链接预测, 数据挖掘, 特征提取, 好友推荐, 机器学习算法

Abstract: In recent years, social networks have become increasingly hot, and data mining based on social networks has also arisen. Link prediction (LP) is an important topic of network data mining, which uses the known network structure and other information to predict and estimate the possibility of linking between two nodes that are not yet linked. Link prediction in social network can be used to recommend friends, filter redundant information, improve user’s satisfaction and loyalty, and build a healthy social networking environment. In previous researches, attentions are focused on structure information or node attributes, in order to analyze the global or local properties. Considering the natures of microblog social network, this paper proposes a link prediction method combining multiple features which includes node features, topological features, social features and voting features. Based on these features, 4 machine learning algorithms, SVM, naive Bayes, random forest and logical regression, are applied on microblog social network data to train predictive models to predict potential social links. The results show that combining multiple features performs better than the traditional features, and the combination of multiple features can achieve highest accuracy.

Key words: link prediction, data mining, features extraction, friends recommendation, machine learning algorithm

中图分类号:

TP393

徐燕. 基于数据挖掘的网络链接预测研究[J]. 信息网络安全, 2017, 17(6): 30-34.

XU Yan. Research on Network Link Prediction Based on Data Mining[J]. 信息网络安全, 2017, 17(6): 30-34.

参考文献

[1] GETTOR L, DIEHL C P. Link Mining: A Survey[J]. SIGKDD Explorations Newsletter, 2005,7 (2):3-12.
[2] LATHA R H, KUMARI K S. Survey on Link Prediction in Facebook and Twitter[J]. International Journal of Engineering Research and Application(IJERA) , 2012, 2 (5): 1631-1637.
[3] HASAN M A, CHAOJI V, SALEM S, et al. Link Prediction Using Supervised Learning[EB/OL].http://www.siam.org/meetings/sdm06/workproceed/Link%20Analysis/12.pdf,2017-4-28.
[4] 郝增帅,郭荣华,文伟平,等. 基于特征分析和行为监控的未知木马检测系统研究与实现[J]. 信息网络安全,2015（2）：57-65.
[5] FIRE M, TENENBOIM L, LESSER O, et al. Link Prediction in Social Networks Using Computationally Efficient Topological Features[C] //IEEE.2011 IEEE Third Inernational Conference on Social Computing (SocialCom) ,October 9-11,2011.Boston, MA, USA .NJ: IEEE, 2011: 73-80.
[6] VALVERDE-REBAZA J, LOPES A D A. Exploiting Behaviors of Communities of Twitter Users for Link Prediction[J]. Social Network Analysis and Mining, 2013,3 (4): 1063-1074.
[7] LIBEN-NOWELL D, KLEINBERG J. The Link Prediction Problem for Social Networks[C]//ACM.CIKM '03 Proceedings of the Twelfth International Conference on Information and Knowledge Management, November 3 - 8, 2003.New Orleans, LA, USA. New York:ACM,2007:556-559.
[8] WANG Dashun, PEDRESCHI D, SONG Chaoming,et al. Human Mobility, Social Ties, and Link Prediction[C]//ACM.KDD '11 Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 21 - 24, 2011. San Diego, California, USA. New York:ACM,2011:1100-1108.
[9] JIA Yantao, WANG Yuanzhuo, LI Jingyuan,et al. Structural-interaction Link Prediction in Microblogs[C]//ACM. WWW '13 Companion Proceedings of the 22nd International Conference on World Wide Web , May 13 - 17, 2013 .Rio de Janeiro, Brazil.New York: ACM, 2013:193-194
[10] NARASIMHAN J, HOLDER L. Feature Engineering for Supervised Link Prediction on Dynamic Social Networks[EB/OL].https://www.researchgate.net/publication/266619242_Feature_Engineering_for_Supervised_Link_Prediction_on_Dynamic_Social_Networks,2017-4-28.
[11] KIM J, CHOY M, KIM D, et al. Link Prediction Based on Generalized Cluster Information[C]//ACM.WWW '14 Companion Proceedings of the 23rd International Conference on World Wide Web,April 7-11, 2014. Seoul, Korea. New York: ACM, 2014: 317-318.
[12] 张士豪,顾益军,张俊豪. 基于用户聚类的热门微博分类研究[J]. 信息网络安全,2015（7）：84-89.
[13] TAN Fei, XIA Yongxiang, ZHU Boyao. Link Prediction in Complex Networks: A Mutual Information Perspective[J]. Plos One, 2014, 9(9):e107056.
[14] LEICHT E A, HOLME P, NEWMAN M E J. Vertex Similarity in Networks[J]. Physical Review E , 2006(2): 1-10.
[15] PAN Ying, LI Dehua, LIU Jianguo, et al. Detecting Community Structure in Complex Networks via Node Similarity[J]. Physica A: Statistical Mechanics and Its Applications, 2010, 389 (14):2849-2857.
[16] 钟杰,王海舟,王文贤. 基于话题的微博信息传播拓扑结构研究[J]. 信息网络安全,2016（3）：64-70.
[17] LV Linyuan, JIN Cihang, ZHOU Tao. Similarity Index Based on Local Paths for Link Prediction of Complex Networks[J].Physical Review E, 2009, 80(2):046122.
[18] YIN Dawei, HONG Liangjie, DAVISON B D. Structural Link Analysis and Prediction in Microblogs[C]//ACM.CIKM '11 Proceedings of the 20th ACM International Conference on Information and Knowledge Management , October 24 - 28, 2011.Glasgow, Scotland, UK .New York:ACM,2011:1163-1168.
[19] CHEN H, LI Xin, HUANG Zan. Link Prediction Approach to Collaborative Filtering[C]//ACM.JCDL '05 Proceedings of the 5th ACM/IEEE-CS Joint Conference on Digital Libraries, June 7 - 11, 2005. Denver, CO, USA .New York: ACM, 2005:141-142.
[20] 周红福,贾璐,张婷婷,等. 微博舆情分析中信息转发路径提取方法研究[J]. 信息网络安全,2016（4）：61-68.
[21] Hially Rodrigues S ?a, PRUDENCIO R B C. Supervised Learning for Link Prediction in Weighted Networks[J]. III International Workshop on Web & Text Intelligence,2010 , 42 (4) :1-6.
[22] SOUNDARAJAN S, HOPCROFT J E. Use of Supervised Learning to Predict Directionality of Links in a Network[A]// Advanced Data Mining and Applications[M].Heidelberg: Springer Berlin Heidelberg, 2012:395-406.
[23] 周美林.分类框架下融合多形态特征的微博好友推荐研究[D].北京：北京语言大学,2013.
[24] BREIMAN L. Random Forests[EB/OL].https://www.researchgate.net/publication/303151231_Random_forests_machine_learning_45,2017-4-28.
[25] ADAMIC L A, ADAR E. Friends and Neighbors on the Web[J]. Social Networks,2003,25 (3):211-230.
[26] LU Zhengdong, SAVAS B, TANG Wei, et al. Supervised Link Prediction Using Multiple Sources[C]//IEEE.2010 IEEE 10th International Conference on Data Mining (ICDM), December 13-17 , 2010.Sydney, NSW, Australia.NJ:IEEE, 2010: 923-928.
[27] BILGIC M, NAMATA G M, GETOOR L. Combining Collective Classification and Link Prediction[C]//IEEE.7th IEEE International Conference on Data Mining Workshops (ICDM),October 28 - 31, 2007.Omaha, NE, USA .NJ:IEEE,2007: 381-386.
[28] WEKA.Weka 3: Data Mining Software in Java[EB/OL]. http://www.cs.waikato.ac.nz/ml/weka/,2017-4-28.