基于进化算法的复杂网络社区结构发现

论文摘要

在复杂网络中,节点可以被划分成若干组,组内节点之间的连接比较稠密,而不同组节点之间的连接则比较稀少,这样的划分结果被定义为复杂网络的社区结构。通过对复杂网络社区结构的研究,一方面可以使我们更好地了解和解释现实世界中所呈现出的各种社区现象,如人际关系网络、疾病传播区域;另外一方面我们可以将复杂网络社区结构的研究理论成果应用到具体问题当中去,如可以设计出具有更好特性的实际网络。在本文中,我们首先介绍了复杂网络社区结构的基本概念,以及用于复杂网络社区结构发现的若干著名算法,总结了不同算法所存在的优缺点。本文的重要成果如下:(1)提出了“基于DNA遗传算法的复杂网络社区结构发现”方法。此算法通过DNA编码的方式来形成DNA链(染色体),每个染色体都是一个潜在的针对问题的可行解。选择出最佳的若干染色体,进行交叉、变异等操作,从而使染色体产生新的特性,按照一定的标准计算染色体的适应度,并通过这种评价函数决定哪个染色体是适合问题的最佳解。该算法无需预知复杂网络的社区数量或者社区内的节点数量,同时实验结果表明该算法具有较高的准确度。(2)提出了“基于PSO算法的复杂网络社区结构发现”方法。该算法采用“PSO算法”来分析复杂网络社区结构,它收敛速度快、易于实现并且仅有少量参数需要调整,初始化微粒的空间位置后,在复杂空间中对最优解进行搜索,实验结果表明该算法具有较高的收敛性。我们用Zachary Karate Club和College Football Network模型对以上算法的准确性进行验证。上述两个模型是复杂网络的经典模型,该模型的社区结构是我们确切知晓的。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 问题的提出
• 1.2 研究背景、现状及其意义
• 1.2.1 研究背景
• 1.2.2 研究现状
• 1.2.3 研究意义
• 1.3 本文的主要成果及工作
• 1.4 本文的结构及内容安排
• 第二章 复杂网络社区结构发现研究概述
• 2.1 引言
• 2.2 复杂网络的基本特性
• 2.2.1 基本概念
• 2.2.2 网络模型
• 2.3 复杂网络的社区结构发现
• 2.4 复杂网络社区结构发现方法概述
• 2.4.1 迭代二分法
• 2.4.1.1 基于Laplace 图特征值的谱平分法
• 2.4.1.2 Kernighan-Lin 算法
• 2.4.1.3 Wu Huberman 算法
• 2.4.1.4 Capocci 算法
• 2.4.2 分层聚类法
• 2.4.2.1 聚集算法
• 2.4.2.2 分裂算法
• 2.5 复杂网络社区结构发现在网络方向的应用
• 2.5.1 网页搜索结果分类
• 2.5.2 网路病毒传播控制
• 2.6 本章小结
• 第三章 DNA 遗传算法及PSO 算法原理
• 3.1 引言
• 3.2 DNA 遗传算法
• 3.2.1 遗传算法
• 3.2.1.1 算法简介
• 3.2.1.2 基本步骤
• 3.2.1.3 算法特点
• 3.2.2 DNA 遗传算法的优点
• 3.3 PSO 算法
• 3.3.1 算法简述
• 3.3.2 算法流程
• 3.3.3 与其他算法的比较
• 3.3.3.1 相似点
• 3.3.3.2 不同点
• 3.4 本章小结
• 第四章 基于DNA 遗传算法的复杂网络社区结构发现
• 4.1 基于DNA 遗传算法的复杂网络社区发现
• 4.1.1 种群初始化
• 4.1.2 编码
• 4.1.3 选择
• 4.1.4 交叉
• 4.1.5 变异
• 4.1.6 基因转移
• 4.2 实验仿真
• 4.2.1 实验目的
• 4.2.2 数据模型
• 4.2.2.1 Zachary Karate Club 模型
• 4.2.2.2 College Football Network 模型
• 4.2.3 适应度函数的选择
• 4.2.4 操作流程
• 4.2.5 纠错操作
• 4.2.6 实验结果
• 4.2.7 结果分析
• 4.2.8 时间复杂度分析
• 4.3 本章小结
• 第五章 基于PSO 算法的复杂网络社区结构发现
• 5.1 基于PSO 算法的复杂网络社区结构发现
• 5.1.1 微粒群初始化
• 5.1.2 参数选择
• 5.1.3 进化计算
• 5.2 操作流程
• 5.3 实验仿真
• 5.3.1 实验结果
• 5.3.2 结果分析及改进
• 5.3.2.1 带惯性权重的PSO 算法
• 5.3.2.2 带收缩因子的PSO 算法
• 5.3.2.3 基于改进的PSO 算法的复杂网络社区结构发现的实验结果
• 5.3.3 时间复杂度分析
• 5.4 本章小结
• 第六章 结论及展望
• 6.1 结论
• 6.2 展望
• 致谢
• 参考文献
• 攻读硕士学位期间取得的科研成果