郭 静，孟昱煜

（兰州交通大学 电子与信息工程学院，兰州 730070）

现实中许多复杂系统都可以被复杂网络刻画表示，比如因特网［1］、万维网［2］、社交网络［3］和蛋白质网络［4］等等.通过研究复杂网络的信息传播、社团结构以及链路预测等特性来挖掘真实复杂系统存在的信息、相互关系和结构特性等等［5］.对于任何一种网络都可以用点和边组成的图表示，这样的图定义为G（V，E），其中：V是顶点集合；E是连边集合.在复杂网络研究与应用中，链路预测是指通过已知的网络拓扑结构以及网络节点属性等信息，预测网络中尚未产生连边的两个节点之间产生链接的可能性或者推断网络中缺失的连边［6］.它的一些应用包括在社交网络中的朋友推荐［7］、预测蛋白质之间的相互作用［8］、推断网络演化机制［9］等.

目前，已提出的链路预测方法主要有基于局部信息、全局信息和准局部3种相似性度量.基于局部信息的算法是根据节点间的相似性选择邻居节点并进行预测，此类算法可以非常有效地计算相似性指数，并且在许多情况下可以很好地执行并且适合大规模的网络应用，如：共同邻居指标（common neighbor index，CN）［10］关注两个节点是否处于同一个环境；Jaccard相似性指标［10］是在任意两点之间的共同邻居数量的基础上引入节点度来刻画相似性；AA（adamic-adar index，AA）指标［10］的思想是度小的共同邻居节点的贡献大于度大的共同邻居节点；资源分配（resource allocation，RA）指标［10］考虑网络中没有直接相连的节点通过共同邻居传递资源；优先链接指标（preferential attachment，PA）算法［10］定义为新链接连接节点的概率正比于两节点度的乘积；……