基于最小生成树的复杂网络社区检测与图像分割

摘要

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

目录

声明

摘要

第一章 绪论

1．1 研究背景与意义

1．2 研究概况

1．3 主要研究内容

1．4 论文组织结构

第二章 社区检测理论基础

2．1 复杂网络相关基础

2．1．1 复杂网络的描述方式

2．1．2 平均路径长度与节点度

2．1．3 集聚系数

2．1．4 小世界性质

2．1．5 无标度性

2．2 社区检测的相关基础

2．2．1 社区的定义及评价标准

2．2．2 社区检测的经典算法

2．3 最小生成树算法

2．3．1 最小生成树定义

2．3．2 最小生成树算法

2．4 本章小结

第三章 基于启发式距离矩阵的社区检测

3．1 启发式距离矩阵

3．1．1 边介数

3．1．2 距离矩阵的创建

3．1．3 无叶子结构的距离矩阵

3．2 算法具体步骤

3．3 仿真实例

3．4 本章小结

第四章 基于最小生成树的社区检测

4．1 聚类算法的启发

4．2 距离矩阵改进

4．3 社区检测具体算法

4．3．1 二层MSTs

4．3．2 基于二层MST算法

4．4 仿真

4．4．1 社会网络

4．4．2 模块度最大化无法正确检测出社区的网络

4．4．3 LFR社区检测基准网络

4．5 本章小结

第五章 基于分水岭-最小生成树的图像分割

5．1 图像分割的研究背景和意义

5．1．1 研究背景

5．1．2 图像分割研究意义

5．2 图像分割的定义和分水岭算法

5．2．1 定义

5．2．2 分水岭算法

5．3 小波能量特征

5．4 相似性矩阵

5．5 图像分割具体步骤

5．6 具体仿真

5．6．1 简单自然图像

5．6．2 复杂自然图像

5．7 本章小结

第六章 总结与展望

6．1 本文工作总结

6．2 工作展望

致谢

参考文献

研究生在读期间研究成果