复杂网络上大规模社团检测并行算法的设计与实现
发布时间:2022-07-08 11:41
随着计算机与互联网技术的不断发展,网络已成为人们日常生活不可或缺的一部分。人们现实生活中的大部分数据都可用网络或图(Graph)来表示,如通信网络,交通网络、社交网络、生物网络等。社团结构是复杂网络的一个重要结构特征,研究这些社团结构有利于更好地理解复杂网络的功能与特性。此外,复杂网络在社团结构层面通常会显示出一些单个节点或整个网络层面所不具备的特性。为了更深入地研究复杂网络,捕获更多有意义的潜在信息,需要使用社团检测技术。然而随着节点数量不断增加,网络结构不断复杂,传统的社团检测算法已不再适用于大规模复杂网络。而分布式并行处理技术为处理大规模复杂网络提供了有效手段。因此,研究复杂网络的社团检测并行算法对深入理解网络结构与性质具有重大理论意义与实际价值。基于上述原因,本文提出了一种针对大规模复杂网络的并行化社团检测算法——Parallel LPA-Attractor算法(简称PLA)。在设计这种算法的过程中涉及图表示、分割、存储、计算以及结果融合问题,其中最重要的是单个计算单元的社团检测算法。在对现有的社团检测算法进行多方面的权衡比较后,本文采用Attractor算法作为核心计算算法。...
【文章页数】:85 页
【学位级别】:硕士
【文章目录】:
摘要
ABSTRACT
符号对照表
缩略语对照表
第一章 绪论
1.1 研究背景
1.2 研究意义
1.3 国内外研究现状
1.4 本文的工作与安排
1.4.1 研究内容
1.4.2 本文组织结构
第二章 复杂网络社团检测的相关基础
2.1 网络与社团的相关基础
2.1.1 复杂网络定义
2.1.2 复杂网络的表示方法
2.1.3 其他基本概念
2.1.4 社团的定义
2.2 社团检测评价指标
2.2.1 模块度
2.2.2 归一化互信息
2.2.3 F1分数
2.3 复杂网络中的经典社团检测算法
2.3.1 标签传播算法
2.3.2 其他常见算法
2.4 本章小结
第三章 基于动态距离的Attractor算法及其改进算法
3.1 基于动态距离的Attractor算法
3.1.1 Attractor算法的基本原理
3.1.2 Attractor算法的相关定义与计算模式
3.1.3 Attractor算法时间复杂度及算法流程
3.1.4 Attractor算法存在的问题
3.2 Attractor的改进算法——LA算法
3.2.1 LA算法的基本原理
3.2.2 LA算法的三种计算模式
3.2.3 LA算法的流程
3.2.4 LA算法的时间复杂度
3.3 LPA的改进算法——AMLPA算法
3.3.1 AMLPA算法的基本原理
3.3.2 AMLPA的算法流程
3.3.3 AMLPA算法的时间复杂度
3.4 本章小结
第四章 LA的并行化算法——PLA算法
4.1 一种图的表示方式——耦合表
4.2 大规模图的分布式处理
4.2.1 METIS算法
4.2.2 分布式存储方式
4.2.3 改进的分布式存储方式
4.2.4 分布式结果融合方法
4.3 PLA算法
4.3.1 PLA算法的原理
4.3.2 PLA算法的流程
4.3.3 PLA算法的时间复杂度分析
4.4 本章小结
第五章 实验与分析
5.1 实验设备
5.2 实验数据集
5.3 PLA核心算法社团分布对比实验
5.4 PLA算法对输入参数的敏感性测试
5.5 PLA算法的NMI测试
5.6 PLA算法时间性能
5.7 本章小结
第六章 总结与展望
6.1 工作总结
6.2 未来展望
参考文献
致谢
作者简介
本文编号:3656963
【文章页数】:85 页
【学位级别】:硕士
【文章目录】:
摘要
ABSTRACT
符号对照表
缩略语对照表
第一章 绪论
1.1 研究背景
1.2 研究意义
1.3 国内外研究现状
1.4 本文的工作与安排
1.4.1 研究内容
1.4.2 本文组织结构
第二章 复杂网络社团检测的相关基础
2.1 网络与社团的相关基础
2.1.1 复杂网络定义
2.1.2 复杂网络的表示方法
2.1.3 其他基本概念
2.1.4 社团的定义
2.2 社团检测评价指标
2.2.1 模块度
2.2.2 归一化互信息
2.2.3 F1分数
2.3 复杂网络中的经典社团检测算法
2.3.1 标签传播算法
2.3.2 其他常见算法
2.4 本章小结
第三章 基于动态距离的Attractor算法及其改进算法
3.1 基于动态距离的Attractor算法
3.1.1 Attractor算法的基本原理
3.1.2 Attractor算法的相关定义与计算模式
3.1.3 Attractor算法时间复杂度及算法流程
3.1.4 Attractor算法存在的问题
3.2 Attractor的改进算法——LA算法
3.2.1 LA算法的基本原理
3.2.2 LA算法的三种计算模式
3.2.3 LA算法的流程
3.2.4 LA算法的时间复杂度
3.3 LPA的改进算法——AMLPA算法
3.3.1 AMLPA算法的基本原理
3.3.2 AMLPA的算法流程
3.3.3 AMLPA算法的时间复杂度
3.4 本章小结
第四章 LA的并行化算法——PLA算法
4.1 一种图的表示方式——耦合表
4.2 大规模图的分布式处理
4.2.1 METIS算法
4.2.2 分布式存储方式
4.2.3 改进的分布式存储方式
4.2.4 分布式结果融合方法
4.3 PLA算法
4.3.1 PLA算法的原理
4.3.2 PLA算法的流程
4.3.3 PLA算法的时间复杂度分析
4.4 本章小结
第五章 实验与分析
5.1 实验设备
5.2 实验数据集
5.3 PLA核心算法社团分布对比实验
5.4 PLA算法对输入参数的敏感性测试
5.5 PLA算法的NMI测试
5.6 PLA算法时间性能
5.7 本章小结
第六章 总结与展望
6.1 工作总结
6.2 未来展望
参考文献
致谢
作者简介
本文编号:3656963
本文链接:https://www.wllwen.com/kejilunwen/yysx/3656963.html