周明强，王莹

（重庆大学计算机学院，重庆 400044）

0 引言

社交网络是Web2.0的一种典型应用即社会性网络服务（Social Networking Service，SNS），也是复杂网络中的一个特例。链路预测是指如何通过已知的网络结构等信息预测网络中尚未产生连边的两个节点之间产生连接的可能性，它既包含了对未知链接的预测，也包含了对未来链接的预测。社交网络链路预测，就是分析社交网络的链路预测，它对信息检索和电子商务中的推荐系统有着关键的作用，可以从最终的链接关系着手帮助使用者找到新的推荐用户和潜在用户，在网上购物提供合理和贴切的推荐。

如何在社交网络中准确进行链路预测，就要考虑到社交网络本身的特点，社交网络的链接在多大程度上可以使用网络本身固有的特性来建模，问题是网络和节点如何相互关联。真实的社交网络通常具有丰富的结构特征，如同质性、异质性和核心-外围性等。如果能够找到网络结构和辅助信息之间的联系，则可以在一定程度上恢复缺失的链路信息。从技术角度来看,如何构建一种以原则性方式将节点（用户配置文件信息）、边（交互）的功能与网络结构组合在一起的方法是核心问题。

1 问题的相关研究

在传统的链路预测问题中，对于无向网络G(V,E)，其中V={v1,v2,…vN}是节点集合，E={e1,e2,…eN}是边的集合，N与M分别是节点数和边数。一个图的邻接矩阵记为A，无向网络中节点x和节点y对应的连接情况记为axy，当且仅当节点vx与vy之间有连边时axy=1，否则 axy=0，如下所示：