基于进化计算的网络社团挖掘研究

论文摘要

现实世界中的很多复杂系统,都可以抽象成图的形式,而复杂网络是研究各类系统普适性特征的有效工具。随着网络科学的发展,社团结构被证实为复杂网络的普遍性质。社团挖掘旨在识别网络中特定的社团结构,不仅对分析复杂网络拓扑结构、揭示复杂网络中的规律和预测复杂网络演化具有重要意义,而且有着广泛的应用前景,如社交网络上的信息传播分析,蛋白质功能预测,推荐系统优化等等。但是随着时代的发展,传统社团挖掘算法面临新的考验:1)网络数据规模增加,如何提高静态网络社团挖掘算法的效率是亟需解决的问题;2)网络呈现动态性,如何高效准确地捕捉网络的社团演化过程是亟待解决的问题;3)网络呈现层次性,如何挖掘出复合社团结构从而深层次地了解系统的全貌是目前的研究热点。针对现有的社团挖掘算法面临的静态社团识别效率低、动态社团结构不稳定,复合社团划分不合理的不足,本文围绕进化算法求解网络社团挖掘问题,将社团挖掘转化成优化问题,结合生物仿生模型和多目标优化理论,以“如何提高静态网络社团挖掘算法的效率”、“如何识别高质量且稳定的动态网络社团结构”和“如何识别具有较高全局特征的多层网络复合社团结构”为主线。针对静态网络社团挖掘,提出了一种基于多头绒泡菌仿生模型的离散粒子群优化算法。针对动态网络社团挖掘,提出了一种基于分解的多目标离散粒子群优化算法。针对多层网络社团挖掘,探究了现阶段多目标进化算法在多层网络上的研究现状和应用前景。本文的主要研究贡献可以概括为以下三个方面:(1)针对静态网络社团挖掘问题,采用离散粒子群优化算法求解该问题。设计基于数字串的编码方式利于解码,方便计算适应度值。通过结合网络拓扑邻居的信息和基于贪心的模块度增量策略,修改传统粒子群算法的速度和位置更新公式。并介绍一种多头绒泡菌网络模型(PNM,Physarum network model),可以在一定程度上识别网络社团间和社团内的边。之后,将PNM模型对社团边属性的识别作为先验知识,对粒子群算法的种群初始化进行指导,提出了一种基于多头绒泡菌仿生模型的离散粒子群优化算法。最后,在计算机生成的基准网络和现实世界的网络数据集上进行对比实验,从准确度、鲁棒性和收敛速度方面证明算法的有效性。(2)针对动态网络社团挖掘问题,根据演化聚类框架思想,同时考虑网络社团的结构质量和稳定程度。为了自动确定演化框架中的权重系数和网络的社团数目,同时降低多目标进化算法的计算复杂度,使用基于分解的多目标粒子群优化算法进行问题求解,该算法分别以网络模块化密度和标准化互信息作为优化目标,采用切比雪夫(Tchebycheff)聚合的方式评价个体的适应度值。基于单目标粒子群优化算法,重新设计算法的初始化过程和最优个体状态更新规则,并设计帕累托(Pareto)最优解选取策略,从Pareto最优前端上选取模块化密度最大的解作为当前时刻的社团划分,同时当作下个时刻网络社团挖掘的参照。最后,通过对4类基准网络和7个真实网络数据集上的实验证明了算法的有效性,并对动态社团结构的演变进行了可视化。(3)由于多层网络社团挖掘研究刚刚起步,缺少清晰、统一的定义,本文仅探讨现阶段多层网络社团挖掘的相关理论基础和研究成果,介绍了两种不同类型的多层网络:复合型多层网络和相互依赖型多层网络。针对复合型多层网络的社团挖掘问题进行了形式化定义,汇总现阶段多层网络社团挖掘研究成果,特别是基于多目标进化计算的多层网络社团挖掘算法,为基于进化计算的多层网络社团挖掘研究奠定理论基础。综上,本文在复杂网络理论基础上,结合进化计算和多目标优化理论进行静态和动态网络社团挖掘,并探讨了多目标进化算法在多层网络社团挖掘中的有效性和应用前景。同时,通过大量实验证明了基于进化计算框架的社团挖掘算法的有效性。

论文目录

• 摘要
• Abstract
• 第1章 绪论
•   1.1 研究背景
•   1.2 国内外研究现状
•   1.3 研究内容与创新点
•     1.3.1 研究内容
•     1.3.2 创新点
•   1.4 论文组织结构
• 第2章 相关工作
•   2.1 复杂网络
•     2.1.1 网络特征分析
•     2.1.2 社团挖掘问题
•   2.2 社团挖掘算法
•     2.2.1 静态网络社团挖掘算法
•     2.2.2 动态网络社团挖掘算法
•     2.2.3 多层网络社团挖掘算法
•     2.2.4 基于进化计算的社团挖掘算法
•   2.3 基于进化计算的多目标优化
•     2.3.1 进化算法
•     2.3.2 多目标优化问题
•   2.4 本章小结
• 第3章 基于粒子群算法的静态网络社团挖掘
•   3.1 粒子群算法在社团挖掘中的应用
•     3.1.1 问题形式化定义
•     3.1.2 社团挖掘背景下的粒子群算法
•   3.2 基于多头绒泡菌仿生模型和粒子群优化的静态网络社团挖掘算法
•     3.2.1 多头绒泡菌网络模型的社团边属性识别
•     3.2.2 基于多头绒泡菌网络模型的粒子群算法
•     3.2.3 计算复杂度分析
•   3.3 数值实验及性能分析
•     3.3.1 数据集及对比算法
•     3.3.2 评估指标
•     3.3.3 实验结果及性能分析
•   3.4 本章小结
• 第4章 基于多目标粒子群算法的动态网络社团挖掘
•   4.1 基于多目标的动态网络社团挖掘
•     4.1.1 动态网络形式化
•     4.1.2 社团挖掘中的多目标优化
•   4.2 基于分解的多目标粒子群算法求解动态网络社团挖掘
•     4.2.1 MOEA/D算法
•     4.2.2 DYN-MODPSO算法
•   4.3 数值试验及性能分析
•     4.3.1 数据集及对比算法
•     4.3.2 实验结果及性能分析
•   4.4 本章小结
• 第5章 基于多目标遗传算法的多层网络社团挖掘
•   5.1 多层网络社团挖掘问题定义
•     5.1.1 多层网络
•     5.1.2 问题形式化
•   5.2 基于多目标遗传算法求解多层网络社团挖掘
•     5.2.1 MOEA-MultiNet算法
•     5.2.2 MLMaOP算法
•   5.3 数值试验及性能分析
•     5.3.1 数据集及对比算法
•     5.3.2 评估指标
•     5.3.3 实验结果及性能分析
•   5.4 本章小结
• 第6章 总结与展望
•   6.1 本文工作总结
•   6.2 未来工作的展望
• 参考文献
• 致谢
• 硕士期间发表的论文

文章来源

类型: 硕士论文

作者: 陈正鹏

导师: 高超

关键词: 复杂网络,社团挖掘,动态网络,多层网络,进化计算,多目标优化理论

来源: 西南大学

年度: 2019

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

专业: 数学,自动化技术

单位: 西南大学

分类号: O157.5;TP18

总页数: 66

文件大小: 5075K

下载量: 65