基于子图结构和功能的复杂网络链路预测研究

链路预测是复杂网络领域新兴的研究方向，是指在已知网络部分链接信息的情况下推断哪些节点间存在虚假链接或缺失链接，在静态网络和动态网络中都有广泛应用。目前基于局域信息的链路预测算法的基本假设是结构越相似的节点越倾向于链接，但是该假设并不适用于所有网络，因此本研究提出基于子图的链路预测算法，其进行链路预测的基本思想是：两个节点是否链接不但取决于两个节点的相似关系，更取决于两个节点之间的链接是否会和周围其他节点一起构成具有一定功能的局部结构。本项目也将分析网络结构和链路可预测性之间的关系，使用结构等价、社交平衡和弱链接等复杂网络经典理论分析子图结构对应的功能和子图结构可进行链路预测的机理。本项目具有广泛的实际应用前景和重要的理论研究价值，不仅将提高网络链路预测的准确性，解决网络存在异质节点或异质边情况下的链路预测问题；同时也将揭示网络结构和功能的对应关系，促进复杂网络理论的发展和完善。

链路预测是指在已知网络部分链接信息的情况下推断哪些节点间存在虚假链接或缺失链接，对于静态网络和动态网络，链路预测研究都具有重要的理论意义和实际应用价值。对于采样（或称静态）网络，链路预测算法能够评估链接的准确性；对于演化（或称动态）网络而言，链路预测有助于理解网络的演化机制。本项目研究主要有以下四点学术贡献：（1）阐明了富节点之间的链接对于复杂网络结构和功能可控性的重要作用，揭示了子图在链路预测和网络可控性方面的重要作用；（2）提出基于子图结构来检验和预测网络的层次结构的方法，建立了基于网络子图的集群运动分析范式，该方法对于各种动物的集群运动研究具有一定的普适性；（3）研究了加权网络上的子图特征与链路预测之间的内在联系，提出在时变网络上使用子图随机置乱作为分析工具的新思路；（4）从理论上提出了链路的可预测性指标，发现复杂网络的局域结构特点和网络的可预测性密切相关，也通过对实际网络的预测证明了所提链路预测算法的有效性。除上述重要进展外，本课题组还尽可能发展和完善了复杂网络上的推荐算法，尤其是与大规模在线社会网络相关的朋友推荐算法。本研究进行链路预测的新思想是：两个节点是否链接不但取决于两个节点的相似关系，更取决于两个节点之间的链接是否会和周围其他节点一起构成具有一定功能的局部结构。基于本项目的子图结构和功能的预测方法不仅能提高链路预测的准确性，也能解决其他方法较难处理的含异质边、异质节点网络的链路预测问题，相关研究成果已经开始和工业界的大数据相结合，对于挖掘垃圾广告传播者、寻找优质商家等实际应用具有重要的参考价值。