论文部分内容阅读
现实世界中许多系统都以网络的形式存在,例如社会关系网络、科学家合作网络、因特网络和蛋白质交互网络等。这些网络具有很高的复杂性,被称为复杂网络。近年来,对复杂网络的结构和特性已给予充分研究,然而对网络信息的识别和恢复仍然是现代信息科学领域一项长期的挑战,具有重要的理论和现实意义。链路预测是解决上述问题的一个重要方向,在计算机、物理、生物等许多领域已有较为深入的研究。链路预测是指通过已知的节点以及网络结构等信息预测网络中尚未产生连边的两个节点之间出现链接的可能性。使用链路预测能够很好的恢复网络的拓扑结构,揭示网络的演化行为。与链路预测相对应的是丢失节点识别,丢失节点识别是指利用已知的网络信息识别未知的网络节点并恢复网络的拓扑结构。与链路预测一样,丢失节点识别对于网络信息的识别和恢复具有重要意义。本文针对复杂网络中的丢失节点识别问题进行研究。解决丢失节点识别问题一般情况下需要进行条件约束,增加已知信息,然后予以解决。占位符框架和模糊点框架是解决丢失节点识别问题的两个框架,本文在这两种不同的丢失节点识别框架下分别设计了相应的丢失节点识别算法。在占位符框架下,设计了基于图嵌入的丢失节点识别算法GEFN。算法首先使用node2vec方法将网络已知节点向量化,然后从已知节点中提取相似的节点对和不相似的节点对组成训练集,接着使用支持向量机训练分类模型,再使用训练好的模型评估占位符之间的相似程度,最后使用层次聚类算法识别丢失节点。在模糊点框架下,设计了基于节点相似度的丢失节点识别算法MIPS。算法基于PageSim算法计算节点相似度,然后使用层次聚类算法识别丢失节点。实验结果表明,GEFN和MIPS这两种算法在丢失节点识别问题上具有良好的识别准确率。