复杂网络上大规模社团检测并行算法的设计与实现

摘要

随着计算机与互联网技术的不断发展，网络已成为人们日常生活不可或缺的一部分。人们现实生活中的大部分数据都可用网络或图(Graph)来表示，如通信网络，交通网络、社交网络、生物网络等。社团结构是复杂网络的一个重要结构特征，研究这些社团结构有利于更好地理解复杂网络的功能与特性。此外，复杂网络在社团结构层面通常会显示出一些单个节点或整个网络层面所不具备的特性。为了更深入地研究复杂网络，捕获更多有意义的潜在信息，需要使用社团检测技术。然而随着节点数量不断增加，网络结构不断复杂，传统的社团检测算法已不再适用于大规模复杂网络。而分布式并行处理技术为处理大规模复杂网络提供了有效手段。因此，研究复杂网络的社团检测并行算法对深入理解网络结构与性质具有重大理论意义与实际价值。 基于上述原因，本文提出了一种针对大规模复杂网络的并行化社团检测算法——Parallel LPA-Attractor算法(简称PLA)。在设计这种算法的过程中涉及图表示、分割、存储、计算以及结果融合问题，其中最重要的是单个计算单元的社团检测算法。在对现有的社团检测算法进行多方面的权衡比较后，本文采用Attractor算法作为核心计算算法。但该算法会检测出大量单节点社团，本文提出的LPA-Attractor算法(简称LA)利用标签传播算法LPA进行预处理改进这一问题。针对LPA算法只能发现非重叠社团的缺陷，本文提出一种改进型算法Adjustable Multi-Label Propagation Algorithm(简称AMLPA)，使节点携带多标签来检测重叠社团。 在算法并行化的其他方面，针对已有的图表示方法不再适合于并行及大规模运算的问题，本文提出了耦合表的图表示方式，耦合表可使数据得到更高效的利用，提高计算速度；PLA算法使用METIS图分割算法对输入的图数据进行分割；在数据存储方面，本文提出一种改进的分布式存储方式，利用节点的深层复制解决了现有图数据的分布式存储方法通信开销大的问题；此外对并行处理的结果提出了有效的合并方案。 相关实验结果表明，本文所提的并行化社团检测算法有效地减少了计算时间，具有时间复杂度较低，准确率较高等优点。其中核心计算算法LA大幅度地减少了单节点社团的发现数量。因此，PLA算法为解决大规模复杂网络的并行化社团检测问题提供了一种有效的解决方案。

目录

第一个书签之前

摘要

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 未来展望

参考文献

致谢

作者简介

1. 基本情况

2. 教育背景

3. 攻读硕士学位期间的研究成果

3.1 申请（授权）专利