基于标签传播和遗传算法的复杂网络社区发现算法研究

论文摘要

随着网络技术和社会需求的快速发展,各行各业与互联网的结合产生了大量的复杂系统。研究者们将这些复杂系统抽象为复杂网络进行研究,以此来揭示其蕴含的规律和行为特征,挖掘深层次的价值和意义。复杂网络的一个共同特性就是社区结构,即将网络划分成各个分区内部联系紧密,外部联系稀松的集群。社区发现是近年来研究的热点问题,研究复杂网络的社区结构有助于我们分析网络中个体之间的共同特性以及整体与部分之间的关系。本文从单目标优化和多目标优化两个方面对社区发现进行研究,主要工作如下:(1)系统地介绍了复杂网络社区发现的研究基础和进展,分类列举目前常用的复杂网络社区发现算法,并分析了不同社区发现算法的优缺点,发现这些算法大多在大型网络上应用效果不好,并且部分算法必须设置先验知识,这使得算法的可用性降低。本文对遗传算法进行了详细的说明,分析了遗传算法在社区发现问题上的可行性和适用性。(2)提出了一种基于模块度优化的社区发现算法,改进了传统的交叉算子和变异算子,将标签传播的思想引入到交叉算子中,使用已产生的社区结构进行交叉,加强了算法的局部搜索能力。将变异控制在已产生的社区结构之间,避免了无效的变异操作。(3)在标准NSGA2算法框架下,使用标签传播的思想来改进传统的交叉算子,提出一种基于多目标优化的社区发现算法。该算法以KKM和RC作为目标函数,采用基于数字字符的编码方式,将种群进行随机初始化,并使用本文中提出的改进交叉算子和变异算子进行操作,从而实现种群的进化。本文提出的两个算法均在人工网络和真实网络数据集上进行了实验,并与其它经典社区发现算法进行比较。实验结果表明本文提出的算法在求解精度上有一定的提高,能够有效检测出复杂网络中存在的社区结构。

论文目录

摘要

ABSTRACT

第1章绪论

1.1 研究背景及意义

1.1.1 研究背景

1.1.2 研究意义

1.2 国内外研究现状

1.2.1 基于图分割的社区发现算法

1.2.2 基于聚类的社区发现算法

1.2.3 基于动态过程的社区发现算法

1.2.4 基于进化算法的社区发现算法

1.3 论文组织结构

第2章理论基础

2.1 复杂网络的基础知识

2.1.1 网络的图的表示

2.1.2 节点的度

2.2 人工网络数据集和真实数据集

2.2.1 LFR基准网络数据集

2.2.2 真实网络数据集

2.3 遗传算法

2.3.1 遗传算法基本概念

2.3.2 遗传算法流程

2.4 多目标优化问题

2.5 本章小结

第3章基于遗传算法的社区发现算法

3.1 算法概述

3.1.1 适应度函数

3.1.2 算法设计

3.2 主要算子设计

3.2.1 基于数字字符的编码方式与初始化

3.2.2 模拟标签传播的交叉算子

3.2.3 带约束的变异算子

3.2.4 带精英策略的选择算子

3.3 算法框架

3.4 实验结果与分析

3.4.1 真实网络实验结果分析

3.4.2 LFR基准网络实验结果分析

3.5 本章小结

第4章基于多目标优化的社区发现算法

4.1 算法概述

4.1.1 基于多目标的社区发现评价函数

4.1.2 算法设计

4.2 算法框架

4.3 实验结果与分析

4.3.1 真实网络实验结果分析

4.3.2 LFR基准网络实验结果分析

4.4 本章小结

第5章结论与展望

5.1 工作总结

5.2 工作展望

致谢

参考文献

附录1 攻读硕士学位期间发表的论文

中文详细摘要

文章来源

类型: 硕士论文

作者: 刘文君

导师: 张凯

关键词: 复杂网络,社区发现,遗传算法,标签传播

来源: 武汉科技大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,自动化技术

单位: 武汉科技大学

分类号: O157.5;TP18

总页数: 62

文件大小: 5300K

下载量: 158

基于标签传播和遗传算法的复杂网络社区发现算法研究

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢