基于离散灰狼优化算法的社团检测算法研究

摘要

研究人员发现复杂网络中有一些具有相同功能或属性的节点，这些节点聚集在一起形成具有特定功能的模块，节点集合称为社团。复杂网络可以划分为若干个社团组成的社团结构，该结构是复杂网络重要的特征。通过分析社团结构，可以加深对复杂网络的拓扑关系与模块功能的了解，有助于解决生活中的实际问题。近年来，研究人员从谱分析方法、基于标签传播的方法、随机游走方法、网络动力学方法和基于优化的方法等不同角度提出了多种社团检测算法，其中有一类基于群智能优化算法的社团检测算法表现突出。本文对传统算法和基于群智能优化算法的社团检测算法进行了分析，提出了基于灰狼优化算法的两种社团检测算法。 (1)基于离散化灰狼优化算法并利用标签传播思想的非重叠社团检测算法GWO-net：针对非重叠社团检测问题，将灰狼优化算法的编码和相关公式离散化，使用两种基于标签传播思想的初始化方法，并加入突变操作和爬山搜索策略，设计了用于检测非重叠社团结构的GWO-net算法。其中离散化灰狼优化算法框架，使用线性的离散化编码，用以表示非重叠社团结构。算法定义了进化过程的数学公式和相关操作，并使用模块度密度作为目标函数，评价非重叠社团结构的优劣。搜索节点在进化过程中，不断优化目标函数，最终得到质量较高的社团结构。两种初始化方法，一种作用于网络全局，倾向于得到精度较高的社团结构；一种作用于节点局部，倾向于得到得到多样性较强的社团结构。算法在迭代时对最优搜索节点使用爬山搜索策略，以增强算法的局部搜索能力。算法在进化后期加入突变操作，以保持种群多样性。为验证GWO-net算法性能，本文在一些实际网络数据集上进行实验，并将算法的检测结果与其它一些非重叠社团检测算法的结果进行对比，结果表明GWO-net可以得到精度较高的社团结构，相比其他算法具有明显优势。 (2)基于离散化灰狼优化算法并利用节点邻居社团内度之和的重叠社团检测算法OLGWO-net：在GWO-net的基础上，针对重叠社团检测问题，定义了非线性离散化编码和相关公式，使用节点邻居社团内度之和及其标准差寻找重叠节点，设计了用于检测重叠社团结构的OLGWO-net算法。框架使用非线性离散化编码，使搜索节点的每一维可以存储多个社团的类标。算法定义了灰狼优化算法中进化过程的数学公式和相关操作，使用扩展模块度作为目标函数，用以评价重叠社团结构的优劣。为寻找网络中的重叠节点，算法使用节点邻居社团内度之和，衡量节点与周围社团联系的紧密程度，并使用节点邻居社团内度之和的标准差判断节点与周围社团联系是否平衡，当节点与邻居社团联系紧密且平衡时，节点被划分为重叠节点，然后获得网络的重叠社团结构。算法对最优搜索节点使用爬山搜索策略，该策略在种群进化前期倾向于探索非重叠社团结构，在进化后期倾向于探索重叠社团结构。为了验证算法性能，本文将OLGWO-net在实际网络数据集上进行实验，与一些重叠社团检测算法的检测结果进行对比。结果表明，OLGWO-net可以检测出较为合理的重叠社团结构，具有较强的重叠社团检测能力。

目录

第一个书签之前

摘 要

Abstract

第一章 绪论

1.1 课题研究的背景与意义

1.1.1 课题研究的背景

1.1.2 课题研究的意义

1.2 社团检测的研究现状

1.2.1 非重叠社团检测算法

1.2.2 重叠社团检测算法

1.3 本论文的主要工作与内容安排

第二章 复杂网络与灰狼优化算法的相关理论

2.1 复杂网络社团检测的相关理论

2.1.1 复杂网络的表示方法与社团结构的定义

2.1.2 社团结构质量的评价指标

2.2 灰狼优化算法

2.2.1 灰狼优化算法的基本原理

2.2.2 灰狼优化算法的数学模型

2.2.3 灰狼优化算法的改进与应用

第三章 基于灰狼优化算法和标签传播思想的非重叠社团检测算法

3.1 搜索节点的离散编码

3.2 GWO-net

3.2.1 算法流程

3.2.2 目标函数

3.2.3 初始化

3.2.4 进化

3.2.5 突变操作

3.2.6 爬山搜索策略

3.2.7 时间复杂度分析

3.3 实验结果及分析

3.3.1 实际网络

3.3.2 实验结果

3.4 本章小结

第四章 基于灰狼优化算法和节点邻居社团内度之和的重叠社团检测算法

4.1 节点邻居社团内度之和及其标准差

4.2 搜索节点编码

4.3 OLGWO-net

4.3.1 算法流程

4.3.2 初始化

4.3.3 进化

4.3.4 突变操作

4.3.5 爬山搜索策略

4.3.6 时间复杂度分析

4.4 实验结果及分析

4.5 本章小结

第五章 总结与展望

5.1 本文工作总结

5.2 未来研究方向展望

参考文献

在学期间的研究成果

致 谢