复杂网络社团划分算法的研究与实现

论文摘要

研究发现各种复杂网络都具有社团结构,正确高效地将网络划分为合理的社团是有效地理解和利用这些网络的前提,找到网络社团划分的精确解是一个NP难题,当网络规模很大的时不存在有效精确解法。本文提出了两种社团划分算法：第一种算法是基于遗传规律的复杂网络社团划分算法,将遗传算法应用到复杂网络社团划分的过程中,引入了可提高收敛速度的孤立点修复策略,经实验证明此算法具有在复杂网络的海量划分方案中搜索到可接受划分方案的能力；第二种算法是基于引力定律的复杂网络社团划分算法,算法中提出弹性算法的概念,将复杂网络节点邻接关系快速映射到二维空间,继而结合引力聚类方法快速识别出社团结构,经实验证明此算法在不需要较多先验信息的情况下表现出较优的划分速度和划分精度。为辅助算法研究,本文提出了用于验证划分算法的方案,给出了利用真实数据构建复杂网络的方法,提供了随机网络生成算法,搭建了可扩展的网络社团划分算法试验平台,实现了三种对比划分算法。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 选题背景和意义
• 1.1.1 背景
• 1.1.2 意义
• 1.2 国内外研究现状
• 1.3 本文工作
• 1.4 论文章节安排
• 第二章 复杂网络社团发现算法概述
• 2.1 复杂网络社团发现算法分类
• 2.1.1 基于优化的方法
• 2.1.2 启发式方法
• 2.1.3 其它划分算法
• 2.2 复杂网络社团发现算法分析
• 2.2.1 算法特性对比
• 2.2.2 算法局限及待解决问题
• 2.3 社团结构度量标准
• 2.3.1 社团结构描述
• 2.3.2 社团结构划分适值函数定义
• 2.4 本章小结
• 第三章 基于遗传规律的复杂网络社团划分算法
• 3.1 复杂网络社团划分与遗传算法
• 3.2 遗传算法的特点
• 3.3 遗传算法在社团划分中的应用
• 3.3.1 基因编码
• 3.3.2 初始群体的生成
• 3.3.3 优良个体选择
• 3.3.4 基因交换
• 3.3.5 基因变异
• 3.3.6 遗传算法实现流程
• 3.3.7 孤立点修复策略
• 3.4 本章小结
• 第四章 基于引力定律的复杂网络社团划分算法
• 4.1 引力定律在现有聚类算法中的应用
• 4.1.1 基于引力的聚类算法
• 4.1.2 基于网格的引力聚类算法
• 4.1.3 基于引力概念的聚类质量评估算法
• 4.1.4 问题与启示
• 4.2 基于引力定律的复杂网络社团划分算法
• 4.2.1 基于引力的社团划分算法
• 4.2.2 基于引力的社团划分算法流程
• 4.2.3 弹性算法模型假设
• 4.2.4 弹性算法二维映射方法
• 4.2.5 弹性算法二维映射效果
• 4.2.6 引力聚类过程
• 4.2.7 弹性算法优化
• 4.3 本章小结
• 第五章 复杂网络社团结构划分算法验证实验
• 5.1 复杂网络社团划分算法验证
• 5.1.1 划分算法验证
• 5.1.2 测试数据与环境
• 5.1.3 基于遗传规律的复杂网络划分算法分析
• 5.1.4 基于引力定律的复杂网络划分算法分析
• 5.1.5 算法验证结论
• 5.2 复杂网络的构建
• 5.2.1 从数据关系中抽象复杂网络
• 5.2.2 随机复杂网络生成
• 5.3 算法实验平台的搭建
• 5.3.1 算法实验平台介绍
• 5.3.2 图的逻辑存储
• 5.3.3 平台图形接口
• 5.4 本章小结
• 第六章 结束语
• 6.1 工作总结
• 6.2 工作展望
• 致谢
• 参考文献
• 作者在读研期间的研究成果