论文部分内容阅读
随着科技的发展,人们身边出现了越来越多的复杂网络。无论是自然界本身存在的神经网络、生物链网络,还是人类活动产生的Internet网络、电力网络,其内在关系都是非常复杂的。虽然这些网络来自不同的领域,但它们有许多相同的特征。社区结构就是复杂网络的一个重要特征之一。对复杂网络进行有效地社区检测能帮助我们更好地理解网络的拓扑结构,分析网络特性,特别是处在社区之间的重叠节点是研究复杂网络动力学的关键因素之一。社区检测广泛应用于生物学、计算机学、社会学等领域,因此,对社区检测算法的研究同样具有很高的实际应用价值。本文首先对复杂网络重要特征以及社区检测的经典算法做了简要的介绍。在对这些经典算法深入理解和分析的基础上,提出了一种简单的距离矩阵,并通过层次聚类算法中的凝聚算法在简单网络上实现了社区检测。与其他社区检测算法中所使用的阻抗矩阵或连通度矩阵相比,该距离矩阵具有计算简单快速的优势。随后本文从聚类角度,应用前文所定义的距离矩阵,提出了一种基于二层最小生成树的社区检测算法。通过比较来自不同最小生成树的划分子集可以实现社区检测,同时还能识别出社区之间的重叠节点。该算法除了不需要给定具体社区数外,还成功摆脱了分辨率极限问题,同时较之凝聚算法在性能上有很大提高。本文分别在真实网络、由于分辨率极限问题无法完整检测出社区的网络以及LFR基准网络成功验证了该算法的合理性和有效性。最后本文结合分水岭算法,提出了一种基于二层最小生成树的图像分割算法,扩展了该算法的应用。并针对自然图像进行了测试,通过与基于聚类的传统图像分割算法K-means和FCM所得的结果进行比较,总结出了本文算法的优缺点。