融合朴素贝叶斯方法的复杂网络链路预测
|
摘要
近来复杂网络成为了众多学者的研究热点。但真实网络中的连边信息并不完整,不利于网络的分析研究,链路预测可以挖掘网络中的缺失连边,为网络重构提供基本依据。本文认为网络中链接的产生不仅受外部因素——共同邻居的影响,还受其自身因素的影响。其中,共同邻居的影响可以通过文献中的局部朴素贝叶斯(LNB)模型量化,节点的影响则根据其自身的度量化。本文将两者综合考虑,提出了融合朴素贝叶斯(SNB)模型,然后用共同邻居(CN)、Adamic-Adar(AA)和资源分配(RA)指标进行推广。在美国航空网(USAir)上的实验结果表明,该方法的预测准确度比LNB和基准方法均有所提高,从而证明了该方法的有效性。
Recently, complex networks have become a research hotspot. However, edge information in the real network is incomplete, which is not conducive to the analysis and research of the network. Link prediction can provide a fundamental basis for network reconstruction by digging out the missing edges in the network. This paper demonstrates that the generation of links in the network is not only influenced by external factors(common neighbors) but also by its own factors. Among them, the influence of common neighbors can be quantified via the local naive Bayes(LNB) model in the literature, whereas the influence of nodes can be quantified depending on their degree. Therefore, a syncretic naive Bayes(SNB) model is proposed based on comprehensive consideration of the influence of the two abovementioned aspects. The model is then extended to common neighbors, Adamic-Adar, and Resource Allocation methods. Finally, the experimental results on USAir show that the prediction accuracy of the method is higher than that of LNB and the benchmark method, which proves the effectiveness of the SNB model.
Recently, complex networks have become a research hotspot. However, edge information in the real network is incomplete, which is not conducive to the analysis and research of the network. Link prediction can provide a fundamental basis for network reconstruction by digging out the missing edges in the network. This paper demonstrates that the generation of links in the network is not only influenced by external factors(common neighbors) but also by its own factors. Among them, the influence of common neighbors can be quantified via the local naive Bayes(LNB) model in the literature, whereas the influence of nodes can be quantified depending on their degree. Therefore, a syncretic naive Bayes(SNB) model is proposed based on comprehensive consideration of the influence of the two abovementioned aspects. The model is then extended to common neighbors, Adamic-Adar, and Resource Allocation methods. Finally, the experimental results on USAir show that the prediction accuracy of the method is higher than that of LNB and the benchmark method, which proves the effectiveness of the SNB model.
引文
[1] LIU Yangyang, ZHAO Chengli,WANG Xiaojie,et al. The degree-related clustering coefficient and its application to link prediction[J]. Physica A:statistical mechanics and its applications, 2016, 454:24-33.
[2]何大韧,刘宗华,汪秉宏.复杂系统与复杂网络[M].北京:高等教育出版社,2009.
[3]刘宏鲲,吕琳媛,周涛.利用链路预测推断网络演化机制[J].中国科学,2011,41(7):816-823.LIU Hongkun, LU Linyuan, ZHOU Tao. Infer network evolution mechanism by using link prediction[J]. Chinese science, 2011,41(7):816-823.
[4]张学龙,王军进.链路预测下能源供应链网络合作演化机制研究[J].智能系统学报,2017, 12(2):221-228.ZHANG Xuelong, WANG Junjin. On the evolution cooperation mechanism of energy supply chain networks under link prediction[J]. CAAI transactions on Intelligent Systems, 2017, 12(2):221-228.
[5] ZHOU Tao, REN Jie,MEDO M, et al. Bipartite network projection and personal recommendation[J]. Physical reviewe, 2007, 76(4):046115.
[6] LU Linyuan, ZHOU Tao. Link prediction in complex networks:a survey[J]. Physica A:statistical mechanics and its applications, 2011, 390(6):1150-1170.
[7] 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.
[8] ADAMIC L A, ADAR E. Friends and neighbors on the Web[J]. Social networks, 2003, 25(3):211-230.
[9] ZHOU Tao, LU Linyuan, ZHANG Yicheng. Predicting missing links via local information[J]. The European physical journal B, 2009, 71(4):623-630.
[10] LIU Weiping, LU Linyuan. Link prediction based on local random walk[J]. EPL(europhysics letters), 2010, 89(5):58007.
[11] LU Linyuan, ZHOU Tao. Link prediction in weighted networks:the role of weak ties[J]. EPL(europhysics letters), 2010, 89(1):18001.
[12] LIU Zhen, ZHANG Qianming, LU Linyuan, et al. Link prediction in complex networks:a local naive Bayes model[J]. EPL(europhysics letters), 2011, 96(4):48007.
[13] VALVERDE-REBAZA J C, DE ANDRADE LOPES A.Link prediction in online social networks using group information[C]//Proceedings of the 14th International Conference on Computational Science and Its Applications.Guimaraes, Portugal, 2014:31-45.
[14] VALVERDE-REBAZA J, VALEJO A, BERTON L, et al.A naive Bayes model based on overlapping groups for link prediction in online social networks[C]//Proceedings of the 30th Annual ACM Symposium on Applied Computing. Salamanca, Spain, 2015:1136-1141.
[15] WU Jiehua. A generalized tree augmented naive Bayes link prediction model[J]. Journal of computational science, 2018, 27:206-217.
[16]闫玲玲,陈增强,张青.基于度和聚类系数的中国航空网络重要性节点分析[J].智能系统学报,2016, 11(5):586-593.YAN Lingling, CHEN Zengqiang, ZHANG Qing. Analysis of key nodes in China's aviation network based on the degree centrality indicator and clustering coefficient[J]. CAAI transactions on intelligent systems, 2016,11(5):586-593.
[17] PUJARI M, KAN AW ATI R. Link prediction in complex networks by supervised rank aggregation[C]//Proceedings of the 2012 IEEE 24th International Conference on Tools with Artificial Intelligence. Athens, Greece, 2012:782-789.
[18] LI Yun, NIU Kai, TIAN Baoyu. Link prediction in Sina Microblog using comprehensive features and improved SVM algorithm[C]//Proceedings of the 2014 IEEE 3rd International Conference on Cloud Computing and Intelligence Systems. Shenzhen, China, 2014:18-22.
[19] YUAN Weiwei, HE Kangya, GUAN Donghai, et al.Graph kernel based link prediction for signed social networks[J]. Information fusion, 2019, 46:1-10.
[20]孙诚,王志海.社会网络中基于神经网络的链路预测方法[J].数学建模及其应用,2017, 6(4):10-17.SUN Cheng, WANG Zhihai. The link prediction algorithms based on neural networks in social networks[J].Mathematical modeling and its applications, 2017, 6(4):10-17.
[21] LI Jichao, ZHAO Danling, GE Bingfeng, et al. A link prediction method for heterogeneous networks based on BP neural network[J]. Physica A:statistical mechanics and its applications,2018, 495:1-17.
[22] XIAO Yunpeng, LI Xixi, WANG Haohan, et al. 3-HBP:a three-level hidden Bayesian link prediction model in social networks[J]. IEEE transactions on computational social systems, 2018, 5(2):430-443.
[23]李勇军,尹超,于会,等.基于最大熵模型的微博传播网络中的链路预测[J].物理学报,2016, 65(2):31-41.LI Yongjun, YIN Chao, YU Hui, et al. Link prediction inmicroblog retweet network based on maximum entropy model[J]. Acta physica sinica, 2016, 65(2):31-41.
[24] WANG Yisen,LIU Fangbing, XIA Shutao, et al. Link sign prediction by variational Bayesian probabilistic matrix factorization with student-t prior[J]. Information sciences, 2017, 405:175-189.
[2]何大韧,刘宗华,汪秉宏.复杂系统与复杂网络[M].北京:高等教育出版社,2009.
[3]刘宏鲲,吕琳媛,周涛.利用链路预测推断网络演化机制[J].中国科学,2011,41(7):816-823.LIU Hongkun, LU Linyuan, ZHOU Tao. Infer network evolution mechanism by using link prediction[J]. Chinese science, 2011,41(7):816-823.
[4]张学龙,王军进.链路预测下能源供应链网络合作演化机制研究[J].智能系统学报,2017, 12(2):221-228.ZHANG Xuelong, WANG Junjin. On the evolution cooperation mechanism of energy supply chain networks under link prediction[J]. CAAI transactions on Intelligent Systems, 2017, 12(2):221-228.
[5] ZHOU Tao, REN Jie,MEDO M, et al. Bipartite network projection and personal recommendation[J]. Physical reviewe, 2007, 76(4):046115.
[6] LU Linyuan, ZHOU Tao. Link prediction in complex networks:a survey[J]. Physica A:statistical mechanics and its applications, 2011, 390(6):1150-1170.
[7] 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.
[8] ADAMIC L A, ADAR E. Friends and neighbors on the Web[J]. Social networks, 2003, 25(3):211-230.
[9] ZHOU Tao, LU Linyuan, ZHANG Yicheng. Predicting missing links via local information[J]. The European physical journal B, 2009, 71(4):623-630.
[10] LIU Weiping, LU Linyuan. Link prediction based on local random walk[J]. EPL(europhysics letters), 2010, 89(5):58007.
[11] LU Linyuan, ZHOU Tao. Link prediction in weighted networks:the role of weak ties[J]. EPL(europhysics letters), 2010, 89(1):18001.
[12] LIU Zhen, ZHANG Qianming, LU Linyuan, et al. Link prediction in complex networks:a local naive Bayes model[J]. EPL(europhysics letters), 2011, 96(4):48007.
[13] VALVERDE-REBAZA J C, DE ANDRADE LOPES A.Link prediction in online social networks using group information[C]//Proceedings of the 14th International Conference on Computational Science and Its Applications.Guimaraes, Portugal, 2014:31-45.
[14] VALVERDE-REBAZA J, VALEJO A, BERTON L, et al.A naive Bayes model based on overlapping groups for link prediction in online social networks[C]//Proceedings of the 30th Annual ACM Symposium on Applied Computing. Salamanca, Spain, 2015:1136-1141.
[15] WU Jiehua. A generalized tree augmented naive Bayes link prediction model[J]. Journal of computational science, 2018, 27:206-217.
[16]闫玲玲,陈增强,张青.基于度和聚类系数的中国航空网络重要性节点分析[J].智能系统学报,2016, 11(5):586-593.YAN Lingling, CHEN Zengqiang, ZHANG Qing. Analysis of key nodes in China's aviation network based on the degree centrality indicator and clustering coefficient[J]. CAAI transactions on intelligent systems, 2016,11(5):586-593.
[17] PUJARI M, KAN AW ATI R. Link prediction in complex networks by supervised rank aggregation[C]//Proceedings of the 2012 IEEE 24th International Conference on Tools with Artificial Intelligence. Athens, Greece, 2012:782-789.
[18] LI Yun, NIU Kai, TIAN Baoyu. Link prediction in Sina Microblog using comprehensive features and improved SVM algorithm[C]//Proceedings of the 2014 IEEE 3rd International Conference on Cloud Computing and Intelligence Systems. Shenzhen, China, 2014:18-22.
[19] YUAN Weiwei, HE Kangya, GUAN Donghai, et al.Graph kernel based link prediction for signed social networks[J]. Information fusion, 2019, 46:1-10.
[20]孙诚,王志海.社会网络中基于神经网络的链路预测方法[J].数学建模及其应用,2017, 6(4):10-17.SUN Cheng, WANG Zhihai. The link prediction algorithms based on neural networks in social networks[J].Mathematical modeling and its applications, 2017, 6(4):10-17.
[21] LI Jichao, ZHAO Danling, GE Bingfeng, et al. A link prediction method for heterogeneous networks based on BP neural network[J]. Physica A:statistical mechanics and its applications,2018, 495:1-17.
[22] XIAO Yunpeng, LI Xixi, WANG Haohan, et al. 3-HBP:a three-level hidden Bayesian link prediction model in social networks[J]. IEEE transactions on computational social systems, 2018, 5(2):430-443.
[23]李勇军,尹超,于会,等.基于最大熵模型的微博传播网络中的链路预测[J].物理学报,2016, 65(2):31-41.LI Yongjun, YIN Chao, YU Hui, et al. Link prediction inmicroblog retweet network based on maximum entropy model[J]. Acta physica sinica, 2016, 65(2):31-41.
[24] WANG Yisen,LIU Fangbing, XIA Shutao, et al. Link sign prediction by variational Bayesian probabilistic matrix factorization with student-t prior[J]. Information sciences, 2017, 405:175-189.