基于改进遗传算法的复杂网络社区检测研究

摘要

随着互联网的发展，复杂网络受到了各学科研究者的关注，社区结构是复杂网络的网络属性。对复杂网络进行社区检测，不仅对解决复杂性问题具有重要的理论意义，而且在众多领域都有着可观的应用前景。近几年，很多社区检测算法被提出，其中基于函数优化的方法备受关注。本论文主要研究进化算法在社区检测中的应用，主要工作如下：
　　(1)传统的遗传算法处理社区检测问题时易陷入局部最优且收敛速度较慢。针对遗传算法存在这些缺点，本文研究了密母算法、遗传算法、禁忌搜索算法的基本理论，在密母算法基础上，提出了一种结合禁忌搜索算法的密母算法(Memetic algorithm with tabusearch strategy，MATS)。采用遗传算法作为其全局搜索策略，同时引入禁忌搜索算法作为其局部搜索策略，这不仅提高了算法的收敛速度，还增强了跳出局部最优的能力。常用的模块度函数存在分辨率限制问题，我们采用扩展的模块密度函数为新的适应度函数，通过调节该函数的参数，以不同的分辨率对网络的社区进行分析，解决了模块度优化算法中普遍存在的分辨率限制问题。MATS不仅克服了遗传算法易陷入局部最优值和收敛速度慢等缺点，同时还解决了模块度本身具有的分辨率限制问题。在基准网络上和真实网络上进行测试，实验结果表明本文算法能够准确地发现社区结构。
　　(2)遗传算法在社区检测中易陷入局部最优解且随机性较强，针对遗传算法存在这些缺点，本文采用一种高效、快速的变异策略，该变异算子结合节点隶属度函数，能有效提高检测的稳定性及社区划分的准确率。同时采用启发式的初始化算法产生初始的种群，使初始种群具有一定的精度和多样性，从而进一步提高搜索效率。另外使用模块度函数作为适应度函数，可简化算法，降低复杂性。在基准网络上和真实网络上进行测试，实验结果表明本文算法能够准确地发现社区结构。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景及意义

1.2 复杂网络社区检测的研究现状

1.3 本文的主要工作

1.4 本文组织结构

2经典的复杂网络社区检测算法概述

2.1 基于图分割的复杂网络社区检测算法

2.2 基于层次聚类的复杂网络社区检测算法

2.3 基于模块度优化算法

3 结合禁忌搜索策略的密母算法用于复杂网络社区检测

3.1 算法背景介绍

3.2模块密度

3.3算法描述

3.4 实验结果与分析

3.5 本章小结

4 基于遗传算法优化模块度的复杂网络社区检测方法

4.1 引言

4.2 算法描述

4.3实验结果及分析

4.4 本章小结

5 总结与展望

5.1 总结

5.2 展望

致谢

参考文献