基于GPU的大规模复杂网络并行社团发现算法研究

摘要

社团结构是复杂网络中最普遍和最典型的拓扑特征之一，正确高效地发现网络社团结构是有效分析和利用这些网络的前提。现有社团发现算法计算复杂度很高，其性能很难满足超大规模复杂网络分析的需求。由于计算速度的限制，只适合对小规模的网络进行社团划分。
　　近几年，图形处理器(Graphics Processing unit，GPU)高速发展，目前其高速的浮点运算能力、并行计算和可编程功能为通用计算提供了良好的计算平台。基于GPU的并行计算在医学图像、计算流体动力学、环境科学等领域得到了成功的应用。本文利用GPU并行计算架构，研究针对大规模复杂网络的社团发现算法以提高计算速度，主要完成的工作有:
　　(1)针对GN算法中的介数计算问题，给出了一种基于GPU的介数并行计算算法，实现该算法并通过实验证明其计算速度有10-50倍的提高，为GN算法基于GPU的改进提供了并行基础。
　　(2)介绍了基于模块度优化的Blondel算法，分析该算法中有数据并行性的部分，即计算每个节点和邻居节点所属社团的模块增量，由于和各邻居节点所属社团的计算具有不相关性，适合在GPU上计算，因此提出了在该算法基础上的基于GPU并行算法，实现该算法并通过实验验证其计算速度20％到50％的提高。
　　(3)给出了基于模拟退火的社团发现算法的原理，实现了该算法。由于模拟退火算法具有天然的并行特性，本文利用GPU的细粒度并行特性，对基于模拟退火的社团发现算法做了基于GPU的并行改进，并通过实验验证改进后算法的计算速度和串行算法相比有2-5倍的提高。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．2 国内外研究现状

1．3 主要研究内容

1．4 本文工作和论文组织结构

第2章 相关工作

2．1 复杂网络

2．1．1 复杂网络简介

2．1．2 网络结构指标

2．1．3 常见模型及特性

2．2 GPU并行计算及CUDA架构

2．2．1 GPU通用计算介绍

2．2．2 CUDA架构

2．3 复杂网络社团发现

2．3．1 基于划分的社团发现

2．3．2 基于模块度的社团发现

2．3．3 并行社团发现算法

2．4 本章小结

第3章 基于GPU加速的复杂网络介数计算

3．1 最短路径及介数计算

3．2 GPU加速的介数计算并行算法

3．2．1 算法思路及数据结构

3．2．2 算法流程

3．2．3 GPU优化设置

3．3 实验与分析

3．3．1 实验环境

3．3．2 实验数据集

3．3．3 试验初始参数设置

3．3．4 实验结果及性能分析

3．4 本章小结

第4章 基于模块度优化的复杂网络并行社团划分算法

4．1 基于GPU改进的Blondel社团发现算法

4．1．1 Blondel社团发现算法

4．1．2 基于GPU改进的Blondel算法

4．1．3 实验分析

4．2 基于GPU改进的模拟退火社团发现算法

4．2．1 模拟退火

4．2．2 基于模拟退火的社团发现算法

4．2．3 基于GPU改进的模拟退火社团发现算法

4．3 本章小结

第5章 总结与展望

5．1 工作总结

5．2 进一步研究工作

参考文献

致谢

攻读硕士期间参加的科研项目