李治成，吉立新，刘树新，李 星，李劲松

(中国人民解放军战略支援部队信息工程大学 郑州 450001)

随着网络科学的发展，复杂网络成为了重要的研究内容[1-5]。生活中的很多复杂系统都可以抽象为网络来表示，不同类型的网络如交通网络、引文网络、蛋白质作用关系网络、社交网络等均是复杂网络的研究对象。而链路预测作为复杂网络的研究方向，旨在利用已有的网络结构发现网络中缺失的连边、错误的连边和未来可能产生的连边[6-8]。链路预测应用于诸多领域，如在社交网络中用于好友推荐[9]，生物网络中用于发现未知的生物结构[10]，以及引文网络中发现科学家之间的合作关系[11]等。

当前，链路预测的研究已经取得较显著的成果。基于拓扑结构的链路预测方法因简单、高效而备受关注[12-14]，根据拓扑结构信息可将链路预测方法分为基于局部结构、基于半局部结构和基于全局结构3 种方法[15]。基于局部结构信息的预测方法假设如果节点越相似，产生连接的可能性越大，其中以共同邻居结构为出发点已有较多的研究方法，AA 指标对共同邻居的大度节点进行惩罚，CAR 方法考虑共同邻居节点之间相互交互[15]。文献[16]对资源分配指标RA 进行了改进，提出扩展的资源分配指标。全局信息考虑网络的全局结构，例如考虑全局路径的Katz 方法[17]，基于随机游走的节点偏好性游走指标(degree-biased random walk, DRW)[18]和有重启的随机游走指标(random walk with restart,RWR)[19]等，全局方法预测结果优于局部指标，但因其时间复杂度高不适用于大型网络。……