基于密度峰值和鲸鱼优化算法的社区发现方法

摘要

网络是一种有用的模型工具，许多现实中的复杂系统都可以借助网络模型来进一步研究。社区是网络中一种重要的结构性质，它是由网络中联系紧密的节点构成的集合。同一个社区内的节点具有某种共性，因此社区体现了网络的局部特性，能够帮助人们挖掘和分析网络中所蕴含的知识。社区发现是检测网络中社区的主要方法，然而网络往往规模庞大且结构复杂，社区间的分界线不明显等为社区发现带来了巨大挑战。为了解决这些问题，本论文从重叠和非重叠两个方面对社区发现进行了研究，将密度峰值算法和鲸鱼优化算法应用于社区发现，同时借助粗糙集理论对节点间相似性的衡量和重叠节点的划分问题进行了相关研究。主要研究工作概述如下：　　1.针对密度峰值应用于社区发现存在局部密度和最小距离计算效果不好的问题，设计了一种基于拓扑结构的密度峰值重叠社区发现(TSDP)算法。TSDP通过节点及邻居的度来计算节点局部密度，该方法能高效且准确地计算局部密度；TSDP采用余弦相似性计算最小距离并设计离散化最小距离模型，该模型增大了最小距离的区分度，有利于更准确地选取中心点；TSDP定义核心跳变值来衡量各节点核心值变化情况，并寻找跳变值最大的节点作为分界点，提高了中心点选取的准确率。在人工网络和真实网络中进行测试，实验结果表明TSDP对于划分重叠社区具有一定有效性。　　2.针对密度峰值在大规模网络中效率低的问题，提出了一种基于粗糙集的快速密度峰值重叠社区发现(RSDPCD)算法。RSDPCD依据节点局部聚集系数来高效且更准确地计算局部密度，将网络所有节点分为局部峰和普通点集合并分别定义了最小距离计算方法，该方法有效避免了大量计算节点间距离，提升了算法效率。针对已有节点相似性衡量方法没有充分考虑节点连接关系导致结果粒度粗糙和不准确，RSDPCD引入粗糙集近似描述节点间拓扑关系，定义了粗糙子图模型来充分考虑节点连接关系，该模型能更准确衡量节点间相似性。针对重叠节点划分低效和不准确的问题，RSDPCD借助粗糙集描述社区，通过迭代不断增大重叠参数来不断缩减和重新划分网络中各社区上近似从而高效且准确地划分重叠节点。在人工网络和真实网络验证了RSDPCD的有效性。　　3.针对群体智能的社区发现算法存在搜索能力有限、易陷入局部优化、时间复杂度高的问题，提出了一种基于动态种群的改进鲸鱼社区发现(EP-WOCD)算法。EP-WOCD结合了搜索能力强且稳定的鲸鱼优化算法进行社区寻优，对鲸鱼优化算法的三种搜索行为进行离散化改进使其更适用于社区发现，加入了多种变异策略来提升鲸鱼群体多样性以提升算法全局搜索能力，加入边界节点调整策略从而提升算法的局部搜索能力，加入了社区融合策略来消除划分结果中的异常小社区从而进一步提升结果质量。另外，为了提升EP-WOCD效率，加入了多种群动态缩减策略。在人工网络和真实网络中进行测试和对比，实验结果表明EP-WOCD是有效的非重叠社区发现算法。

目录

声明

第 1 章绪 论

1.1 课题背景和研究意义

1.1.1 课题背景

1.1.2 研究意义

1.2 国内外研究现状分析

1.2.1 社区发现主要发展

1.2.2 基于聚类方法的社区发现算法国内外研究现状

1.2.3 基于群体智能优化的社区发现算法法国内外研究现状

1.3 本论文的主要内容

第 2 章相关理论知识

2.1 社区发现相关知识

2.1.1 网络及社区的相关概念

2.1.2 评价指标

2.2 密度峰值聚类算法

2.3 粗糙集理论基本理论

2.4 鲸鱼优化算法

2.5 本章小结

第 3 章基于拓扑结构的密度峰值重叠社区发现算法

3.1 TSDP 的基本原理及算法流程

3.1.1 基于拓扑结构的局部密度计算方法

3.1.2 离散化的最小距离计算方法

3.1.3 基于核心跳变值的社区中心选择

3.1.4 TSDP重叠社区划分方法

3.2 实验设计及性能分析

3.2.1 时间性能对比

3.2.2 人工网络中算法性能对比

3.2.3 真实网络中算法性能对比

3.2.4 TSDP参数分析和调整

3.3 本章小结

第 4 章基于粗糙集的快速密度峰值重叠社区发现算法

4.1 RSDPCD的基本原理及算法流程

4.1.1 基于粗糙子图模型节点相似性衡量

4.1.2 快速局部密度和最小距离计算方法

4.1.3 社区中心点选择

4.1.4 基于粗糙集的重叠社区发现

4.2 实验设计及性能分析

4.2.1 参数调整

4.2.2 真实网络中算法性能对比

4.2.3 人工网络中算法性能对比

4.3 本章小结

第 5 章基于动态种群的改进鲸鱼社区发现算法

5.1 EP-WOCD的基本原理及算法流程

5.1.1 鲸鱼群体初始化

5.1.2 离散化的鲸鱼搜索行为

5.1.3 变异和边界节点调整策略

5.1.4 多种群动态缩减策略

5.1.5 社区融合策略

5.1.6 EP-WCOD算法流程

5.2 实验设计及性能分析

5.2.1 参数设置

5.2.2 时间性能对比

5.2.3 真实网络中算法性能对比

5.2.4 人工网络中算法性能对比

5.2.5 不同优化目标结果对比

5.3 本章小结

总结与展望

工作总结

未来展望

致谢

参考文献

攻读硕士学位期间发表的论文及科研成果