论文部分内容阅读
在科学研究的进程当中,任何学科都必然会遇到预测问题,对复杂网络的链接预测是数据挖掘领域内一个极其重要的研究方向。在现实世界中,无论是自然界中存在的形形色色的复杂系统,还是我们为分析问题、解决问题而创造的模型系统,都可以用复杂网络去描述和刻画。在这些系统之中,个体与个体间往往存在着复杂联系。复杂网络在构建过程中,由于时间和空间或者实验条件的限制,难免有错误或冗余的链接出现,还有不少潜在的链接并未探测到。再者,复杂网络往往是随时间动态演化的,其链接会不断地添加或去除。因此,需要根据已知的网络信息对缺失的链接以及未来的链接进行预测,这就是网络链接预测问题。链接预测有助于我们更好地分析和认识相关网络。早期的链接预测的途径,主要是基于马尔科夫链和机器学习等方法。随着研究的深入,人们认识到,网络自身的拓扑结构能够清晰地反应出顶点之间的结构相似性,而这种相似性往往揭示了它们之间是否存在链接。因此学者们提出了各种刻画这种结构相似性的指标,例如CN, AA, Katz等,这些指标都显示出了较好预测效果。在一些应用问题中,网络的顶点自身带有极其丰富的属性信息。这些属性反映了顶点所代表的对象的特性和内容,这些信息也很大程度上影响着链接存在的可能性。如果能够把结构信息和属性信息结合到一起,势必能够极大地提高链接预测算法的预测精度。目前,如何将结构信息和属性信息有机地融合在一起,以提高链接预测质量,还是一个有待探讨的问题。本文针对顶点带属性网络的链接预测问题,从顶点的结构相似性和属性相似性出发,研究如何有机地融合结构信息和属性信息、设计高效的链接预测算法,以提高预测精度。本文的研究工作和主要研究成果有:(1)我们提出了一种基于相似度传播的链接预测算法,把顶点的属性相似度作为一种权重附加给每一条边,结合最短路径的算法,得到网络中所有顶点间信息能力的大小。然后根据这种传播能力的大小,按照设定的传递法则,使每一对顶点间的相似度都在整个网络之间传播,并在传播过程中更新自身的值。在传播过程收敛之后,便得到了每一对顶点之间相似度,来反映他们之间存在链接的可能性。我们在相关的数据集上进行测试的结果表明,我们所提出的算法具有较高的预测精度。(2)我们提出了基于参数选择的链接预测算法,该算法利用Katz链接预测算法中需要确定的参数值,把顶点的属性信息作为求得该参数最优值的条件来求得该参数,使得结构信息和属性信息有效地结合。我们在相关的数据集上进行测试的结果表明,该算法可以取得高质量的预测结果。(3)我们提出了基于空间映射思想的链接预测算法,该算法把网络中顶点的属性信息和结构信息映射到相同的空间中,在新的空间中进行相似度的计算。在映射过程中利用了矩阵分解的方法,在完成映射后,利用矩阵比对的方法,使结构相似度和属性相似度保持一致,求得最终的相似度得分矩阵。在数据集上的测试结果显示,我们的算法取得结果质量要高于其他相关的算法。