链路预测中的一种局部结构相似度算法  

Local Structure Similarity Algorithm for Link Prediction

作　　者：尹永超 徐敏[1,2] 傅皇麟 孙胜男 

机构地区：[1]南京航空航天大学计算机科学与技术学院,南京211106 [2]软件新技术与产业化协同创新中心,南京210023 [3]云南师范大学外国语学院,昆明650500

出　　处：《小型微型计算机系统》2018年第1期27-31,共5页Journal of Chinese Computer Systems

基　　金：国家"九七三"重点基础研究发展计划项目(2014CB744900)资助

摘　　要：随着复杂网路理论的不断完善,对网络结构及演化模型的研究具有重要的应用价值,而链路预测作为复杂网络的研究热点越来越受到人们的重视.由于在大规模网络中,节点的属性等信息较难获取且相对不完整,因此现有的链路预测算法大都基于局部信息的相似度指标.这些算法往往计算简单、复杂度低,且能取得较好的预测效果,比较适合大规模的网络应用.但是由于其往往仅考虑到了不同节点之间的共同邻居数量,以及节点的度数影响,在个别网络中很难取得较好的预测效果.本文通过分析、比较现有的相似度指标算法,验证各算法的侧重点以及预测效果.对不同的网络结构模型进行提取以及比较,提出了一个新的基于邻节点结构相似度的LSCN指标算法.通过节点与其对应节点的邻居节点的结构相似度来计算节点对之间的连接概率,从而预测两个节点之间产生连接的可能性.通过在多个不同的网络结构中进行重复试验,由平均预测结果得出在部分网络中,算法的预测效果与其他依据节点结构相似性的算法相比得到了明显提升.With the constantly improve of complex network theory ,the study of network structure and it＇s evolution become more ap-plied value,and link prediction as the research focus of complex network has attracted more and more people＇s attention. For the largescale networks, because the information of node attribute is incomplete and hard to obtain, so at present the most algorithms of linkprediction are based on similarity index of local information. These algorithms always have the simple calculation and better effect ofprediction, so they are more suitable for the large-scale network applications. But because they usually just considered the amount ofcommon neighbors and degree of nodes. On several networks it＇s hard to get the better predictive effect for different algorithms. In thispaper we analysis and compare the different points of the different similarity index algorithms. And through analyzed the based struc-ture models we proposed a new LSCN index algorithm. According the structure similarity between one node and another node＇s allneighbors,to predict the link possibility. Through abundant experiments we can find that the effect of prediction has a great promotionin several networks.

关 键 词：复杂网络 链路预测 共同邻居 结构相似度 局部信息 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]