复杂网络链接预测与社团发现混合方法研究

Link prediction and community detection are both important and hot research issues in complex networks, and have both theoretical and applied values in many fields. Recent research results show that link prediction and community detection have some close correlations, however the clear correlations are not known well. To this problem, we will combine the solving of the two problem in-depth. For one hand, we will use link prediction methods to complement network information for community detection in sparse networks; on the other hand, we will employ various kinds of community structures to enhance the design of models and algorithms in link prediction for better precision and efficiency. The research of this project will push forward the understanding of the formation mechanism of links and communities, and will have a broad influence in dynamic complex networks.

链接预测与社团结构发现都是复杂网络研究中非常重要的问题和研究热点，在许多领域都有着明确的理论和应用价值。近期的研究结果表明链接预测与社团发现之间存在着某种内在的紧密联系，但是它们之间明确的相关性仍然并不清晰。本课题针对链接预测与社团发现的相关性展开研究，拟将这两个问题的求解进行深度结合，一方面利用链接预测方法对网络进行必要的信息补充以提升稀疏网络中社团的可发现性；另一方面利用网络中可能存在的各类社团结构信息增强链接预测模型和算法的设计，以求获得更好的预测精度和效率。项目的研究将推进对网络中链接和社团结构形成机制的理解，对网络动态的研究产生广泛的影响。

复杂网络中的社团/聚集结构与网络中链接的形成机制、链接预测有着密切的联系，深入研究两者之间的关系和相互作用机理对于更好地理解网络的形成进而实现预测有着重要的意义。本项目首先研究了一种基于三角形叠加的网络增长模型，该模型包括两种简单的三角形增长机制，通过参数调节既可以生成平面网络也可以生成无尺度网络，生成的网络具有明显的高聚集性、高模块性以及非平凡异质曲率分布的网络，该项研究揭示了网络中的三角形结构对于网络中链接的生成具有重要影响。基于这一发现，我们进一步研究了多种基于网络局部聚集信息的链接预测方法，包括基于节点聚集系数的链接预测方法、基于非对称边聚集系数的链接预测方法以及结合节点和边聚集系数的链接预测算法。在公共邻居的框架下，我们首先提出了一种非常简洁的基于节点聚集系数的链接预测方法CCLP，该方法虽然简单，但却可以得到与一些比较复杂、计算量更大的方法相当的预测结果，显示了聚集信息在链接预测当中的价值。进一步，为了得到更加局部和有针对性的聚集信息，我们提出一种非对称边聚集系数的方法，该方法可以将基于节点聚集系数的几种方法的预测效果显著提升。最后我们将节点和边聚集系数结合使用，在大规模网络上得到了更好的结果。这一系列研究表明：（1）网络中的局部聚集信息可以有效提升链接预测的准确性；（2）提升聚集信息的局部性和针对性可以有效提升链接预测的准确性；（3）各种类型的局部聚集信息结合使用可显著提升大规模网络的链接预测效果。此外，我们还提出了一种结合网络社团结构的链接类型预测方法和以及一种基于层聚类的多层网络社团发现算法。