万杨晔,郭进利

(上海理工大学管理学院,上海 200093)

0 引 言

现实世界中不同实体之间的相互作用组成了各式各样的网络，实体之间的关系是不断变化的，所以节点和连边的增加或移除总在发生，导致网络的高度动态和复杂，理解这些网络的演化机制具有理论价值和实际意义。链路预测能处理网络的结构和演化的问题，能根据节点属性信息、结构特征来估计2个节点间存在链接的可能性[1]。在现实生活中，预测网络中的缺失链接有着广泛的应用。在京东、淘宝等线上购物网络中，链路预测能根据用户购物记录或浏览记录推荐用户感兴趣的商品；在生物领域，利用已知的蛋白质之间存在的相互作用关系[2]，准确预测蛋白质之间未知相互作用可以帮助人们大幅降低实验成本并节省实验时间；在线上社交网络如微博中，通过用户现有的关注关系，链路预测能挖掘出可能认识的朋友或感兴趣的用户[3]。

目前，基于相似性的链路预测方法在实际应用中较为常见，其计算简单、精度较高并且对于同种类型结构的网络都具有普遍良好的效果。这种相似性指标主要分3类，第1类是局部信息指标，这类指标大多在CN(Common Neighbors)指标上进行进一步的挖掘，如Adamic-Adar(AA)指标[4]给共邻节点以度值对数倒数赋权，资源分配(Resource Allocation, RA)指标[5]也是以同样思想以度值倒数赋权，CCLP (Clustering Coefficient based Link Prediction)指标[6]以共邻的聚集系数之和表示出现链接的可能性等。第2类是路径指标，主要有LP(Local Path)[7]、Katz指标[8]等，分别计算节点间不同长度的路径。……