复杂网络中丢失节点识别算法研究

发布时间：2021-06-29 03:12

　　现实世界中许多系统都以网络的形式存在,例如社会关系网络、科学家合作网络、因特网络和蛋白质交互网络等。这些网络具有很高的复杂性,被称为复杂网络。近年来,对复杂网络的结构和特性已给予充分研究,然而对网络信息的识别和恢复仍然是现代信息科学领域一项长期的挑战,具有重要的理论和现实意义。链路预测是解决上述问题的一个重要方向,在计算机、物理、生物等许多领域已有较为深入的研究。链路预测是指通过已知的节点以及网络结构等信息预测网络中尚未产生连边的两个节点之间出现链接的可能性。使用链路预测能够很好的恢复网络的拓扑结构,揭示网络的演化行为。与链路预测相对应的是丢失节点识别,丢失节点识别是指利用已知的网络信息识别未知的网络节点并恢复网络的拓扑结构。与链路预测一样,丢失节点识别对于网络信息的识别和恢复具有重要意义。本文针对复杂网络中的丢失节点识别问题进行研究。解决丢失节点识别问题一般情况下需要进行条件约束,增加已知信息,然后予以解决。占位符框架和模糊点框架是解决丢失节点识别问题的两个框架,本文在这两种不同的丢失节点识别框架下分别设计了相应的丢失节点识别算法。在占位符框架下,设计了基于图嵌入的丢失节点识别算法G... 

【文章来源】：兰州大学甘肃省 211工程院校 985工程院校 教育部直属院校

【文章页数】：53 页

【学位级别】：硕士

【图文】：

完整网络H[8]

兰州大学硕士学位论文复杂网络中丢失节点识别算法研究图2-2克罗内克图模型[8]M步直到最后收敛求出Z，即目标未知网络。虽然KronEM算法能够在已知网络信息很少的情况下推断出剩余未知的网络结构，但由于该方法是基于克罗内克构图的方法，使得该方法过于依赖具体网络性质，如果网络自相似性质明显，则效果好，如果网络自相似性质不明显，则效果欠佳。2.2聚类2.2.1k-meansk-means聚类算法是一种应用广泛的聚类算法[18]。k-means算法首先随机选择k个数据点作为k个初始的簇中心，然后计算每个数据点与各个簇中心之间的距离，把每个数据点分配到距离这个数据点最近的簇中心，簇中心和分配的数据点构成了一个聚类。根据现有的聚类，重新计算每个聚类的聚类中心，再将所有样本点重新分类，不断迭代上述过程直到没有数据点被重新分配给不同的聚类、聚类中心不再发生变化或者达到迭代次数。k-means算法计算效率高，使用范围广泛，但是因为初始的聚类中心是随机选择的，初始聚类中心的选择对聚类结果影响较大。2.2.2聚类层次聚类分成自底向上的凝聚方法和自顶向下的分裂方法[28]。凝聚法初始将毎个节点视作一个小簇，通过合并相似的簇实现聚类。分裂法初始将所有节点视作同一个大簇，不断分裂成更小的簇。层次聚类算法并不是直接给出聚类的结果，而是每聚类一个阶段产生一个聚类结果。比如凝聚法，初始将每个节点作为一个簇，然后每次迭代计算选取距离最近的两个簇，并将它们合并，直到只有一个簇为止。8

完整网络


本文编号：3255605