蔡 彪，李蕊岑，吴媛媛

（成都理工大学计算机与网络安全学院，成都 610059）

（*通信作者电子邮箱caibiao@cdut.edu.cn）

0 引言

复杂网络是研究真实世界中各种复杂系统的结构和演化规律的常用工具。许多社会、生物和信息系统都可以被抽象成一个个的网络来对它们加以描述，一个典型的网络是由许多节点和连接两个节点之间的一些边组成，其中节点用来代表真实系统中不同的个体或组织，而边则用来表示它们之间的相互作用。与复杂网络有关的研究越来越受到人们的关注，链路预测是复杂网络的一个重要分支，它的任务是基于已知网络结构［1-3］，挖掘出给定网络中节点之间缺失的链接。对于某些网络，特别是生物网络，如蛋白质-蛋白质相互作用网络［4-6］、代谢网络和食物网，节点之间是否存在连接需要通过大量实验结果来进行推断。已知的实验结果仅仅揭示了巨大网络的冰山一角，但揭示这类网络中隐而未现的链接需要耗费高额的实验成本，如果预测能足够准确，事先在已知网络结构的基础上设计出精确的链路预测算法，则可以大大降低实验成本，而不是逐个地检查所有可能的交互。链路预测因其重大的实际应用价值，成为许多科学分支的共同焦点［7-9］。

传统上，一种有效的链路预测模型是对潜在节点对进行相似性评分，这对节点越相似，它们之间的联系就越紧密，产生链接的可能性也就越大。此类方法可以通过研究网络的结构特征来实现，如三元图［10］、节点聚类［11］、社区结构［12］和环结构［13］等。……