常 圣 马 宏 刘树新 朱宇航

(中国人民解放军战略支援部队信息工程大学 河南 郑州 450002)

0 引 言

链路预测作为复杂网络研究的一个重要分支，是指通过已知的网络信息，预测网络中两个节点之间存在连边的可能性[1]。链路预测是从连边这个微观角度探究网络的结构特点以及演化规律。链路预测技术可以解决缺失信息的还原、错误信息的纠正、未来信息的预测等问题[2]。网络技术的发展使网络数据的获取变得越来越容易，同时门户网站、社交平台和网上购物等新兴事物的出现也使得对于推荐系统的需求变得更加迫切。如何吸引更多的用户、创造更多的流量、提高自己的知名度等一直是各大平台关注的焦点。通过链路预测技术，可以基于已有的用户信息和网络拓扑结构，发现用户潜在的朋友、兴趣圈子、感兴趣的商品等，将此类信息推送给用户。如果推荐内容与用户的兴趣一致性较高，将会极大地改善用户的使用体验并增加用户对于平台的忠诚度。

链路预测不仅在现实世界中有着广泛的应用价值，在理论研究中也具有重要的意义。预测效果较好的方法在一定程度上反映了网络的内在特性和演化机制，为网络演化理论提供思路，从而可以推动相关理论研究的进展。O’Madadhain等[3]曾使用链路预测方法对电话呼叫网络进行建模，进而模拟社区的形成。Leicht等[4]提出了刻画节点相似性的理论问题，而链路预测技术中基于相似性的指标[5]就是从不同角度刻画节点间的关系，这些方法可为该理论问题提供重要的研究依据。……