李艳丽，周 涛

(电子科技大学复杂性科学实验室 成都611731)

链路预测的核心任务是预测两个没有连接关系的节点产生链接的可能性[1-4]。该研究方向最初的兴起是为了辅助万维网用户从海量的网页中寻找感兴趣的网页[5-6]。后来逐渐在朋友关系预测[7]、恐怖分子的发现[8]、潜在的学术合作关系预测[9]、生物学相互作用关系的揭示[10-11]、商品推荐[12]、网络生成机制探索[13-14]和网络可预测性[15-17]等问题上发挥了巨大价值。其预测类型囊括了根据观测到的网络结构预测可能存在的缺失连边(missing link)，未来可能产生的连边(future links)以及甄别虚假连边(spurious link)等[1,18]。其研究对象涵盖了简单网络、有向网络、二分网络、异构网络和时序网络等[19]。其方法论涉及了基于相似性的链路预测算法(similarity-based algorithms)[9,20]、概率模型(probabilistic models)[21-23]、最大似然模型(maximum likelihood methods)[8,18,24]、网络嵌入模型(network embedding)[25-28]和其他方法[29-31]。

基于相似性的链路预测算法尤其是局部相似性指标可应用领域最为广泛。因为它设计简洁、可解释性强、运算时间低、灵活可扩展，同时其预测准确度有时甚至优于相对复杂的概率模型、最大似然模型和网络嵌入模型[31-33]。该类算法的基本思路是利用节点的局部拓扑结构信息为每一条候选连边分配一个相似性得分，得分越高的连边被认为有更大可能是缺失边，因此在预测列表中排序更靠前。这些算法中最具代表性的几个工作分别是文献[9]总结的纯粹基于网络拓扑结构的一系列局部相似性指标的工作、文献[34]提出AA指标的工作和文献[20]提出RA指标(resource allocation)的工作。……