复杂网络社区探测算法及其分辨率限制研究

论文摘要

复杂网络社区探测问题一直以来是网络研究领域的热门课题,关于社区探测算法的研究成果也是硕果累累。例如,基于模块度的社区探测算法以及基于信息论的Infomap算法在应用中都取得相当不错的效果。但由于模块度函数本身的性质,使得基于模块度优化的算法对于复杂网络中存在的小型社区可能无法识别出来。类似的这种分辨率限制问题同样的存在于Infomap算法中。针对社区探测算法的分辨率限制问题,本文基于模块度最优化思想,给出了模块度算法社区识别的分辨率极限。类似的,基于信息编码理论我们进一步估计出Infomap算法的分辨率极限。通过对比两类算法的分辨率极限,我们发现Infomap算法在探测网络社区结构方面优于模块度算法,最后通过人工网络数据的模拟和真实网络数据的实证分析,也进一步印证了本文提出的在分辨率限制上Infomap算法的本质的优越性。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
•   §1.1 研究背景与意义
•   §1.2 研究现状分析
•   §1.3 本文研究内容
• 第二章 复杂网络以及社区探测算法概述
•   §2.1 复杂网络概述
•     §2.1.1 复杂网络的图表示以及相关概念
•     §2.1.2 复杂网络的特征
•     §2.1.3 复杂网络的社区结构
•   §2.2 社区结构质量评价指标
•     §2.2.1 模块度
•     §2.2.2 NMI
•   §2.3 社区探测算法
•     §2.3.1 模块度算法
•     §2.3.2 Infomap算法
•     §2.3.3 算法时间复杂度对比
• 第三章 复杂网络社区探测算法分辨率限制问题的研究
•   §3.1 引言
•   §3.2 基于模块度最优化算法分辨率限制问题的研究
•     §3.2.1 模块度最优化算法
•     §3.2.2 弱模块的定义
•     §3.2.3 模块度最优化
•     §3.2.4 模块度分辨率的极限
•   §3.3 基于映射方程的Infomap算法分辨率问题的研究
•     §3.3.1 基于映射方程的Infomap算法
•     §3.3.2 映射方程的分辨率极限
• 第四章 数值模拟与实证分析
•   §4.1 引言
•   §4.2 实验数据介绍
•     §4.2.1 人工网络数据集
•     §4.2.2 真实网络数据集
•   §4.3 实验结果分析
• 结论
• 附录A 相关引理及定理证明
•   §A.1 定理3.1的证明
•   §A.2 定理3.2的证明
• 参考文献
• 致谢

文章来源

类型: 硕士论文

作者: 方斌

导师: 张日权

关键词: 复杂网络,社区探测,模块度,算法,分辨率限制

来源: 华东师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 华东师范大学

分类号: O157.5

总页数: 53

文件大小: 2696K

下载量: 118