大规模网络布局压缩算法及加速研究

发布时间：2017-09-21 21:18

  本文关键词：大规模网络布局压缩算法及加速研究

  更多相关文章： 力导引布局算法 关节点 介数中心性 k-核 GPU

【摘要】：复杂网络可视化是复杂网络研究中的重要手段。随着Web2.0时代和大数据时代的来临,作为研究对象的复杂网络的规模越来越大,人们也越来越需要对规模庞大的数据进行准确地表达和理解,并从中进一步探索和挖掘有效信息。采用传统的数据表达方式已经不再能够满足人们的需求。因此,将复杂网络数据进行可视化成为了人们理解和研究复杂网络数据的一个主要方式。然而伴随着复杂网络数据的海量式增长,对复杂网络可视化布局算法的布局效果和运算速度都提出了新的挑战。在可视化布局算法中,力导引布局算法由于其布局结果的美观性等原因得到了最为广泛的应用。因而,本文基于力导引布局算法,从优化布局效果和提高算法效率两方面同时对大规模网络数据的布局算法进行了改进和实现。在优化布局效果方面,分别利用复杂网络中的关节点,介数中心性和k-核的概念,提出了三种不同的网络数据压缩方式。将网络节点划分为不同类别,并根据节点所属类别进一步对其进行聚集合并,实现大规模网络数据的压缩布局显示,从整体上清晰地显示网络宏观结构。在提高算法效率方面,针对压缩后的网络数据,对力导引算法需要的斥力计算、引力计算和更新坐标三个部分均实现了基于GPU的并行计算,大大缩短了算法的运行时间,从而使人们在可接受时间内获得大规模网络数据的可视化布局结果。最后,给出相应算法的实验布局结果,并提出了面向压缩布局的复杂网络信息量的概念,用于量化衡量网络数据在压缩前后的变化情况。结合实验数据分析和对比了网络数据性质压缩前后的变化,验证了三种网络数据压缩方式和GPU并行计算力导引算法的有效性。
【关键词】：力导引布局算法 关节点 介数中心性 k-核 GPU
【学位授予单位】：北京化工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-6
• Abstract6-12
• 第一章 绪论12-22
• 1.1 课题研究背景及意义12-14
• 1.2 国内外相关研究14-19
• 1.3 论文主要贡献19-20
• 1.4 论文的组织结构20-22
• 第二章 本文相关概念及算法22-28
• 2.1 FR布局算法22-24
• 2.2 关节点及查找算法24-25
• 2.3 本文相关拓扑参数25-26
• 2.4 本章小结26-28
• 第三章 大规模网络压缩布局及算法加速28-42
• 3.1 基于关节点的大规模网络数据压缩算法(CABAP)28-33
• 3.2 基于介数关节点的大规模网络数据压缩算法(CABBAP)33-35
• 3.3 基于k-核的大规模网络布局压缩算法(CABK)35-37
• 3.4 基于GPU的FR算法加速37-41
• 3.4.1 大规模网络数据ICSR式存储结构37-39
• 3.4.2 基于GPU的FR算法39-41
• 3.5 本章小结41-42
• 第四章 大规模网络压缩布局及算法加速实验与分析42-62
• 4.1 面向压缩布局的复杂网络信息量42-43
• 4.2 CABAP算法实验结果及分析43-47
• 4.3 CABBAP算法实验结果及分析47-53
• 4.4 CABK算法实验结果及分析53-56
• 4.5 基于GPU加速FR算法实验结果及分析56-58
• 4.6 压缩网络细节展示58-59
• 4.7 本章小结59-62
• 第五章 结论与展望62-64
• 5.1 论文主要成果62-63
• 5.2 未来工作展望63-64
• 参考文献64-68
• 致谢68-70
• 研究成果及发表的学术论文70-72
• 作者及导师简介72-73
• 附件73-74

【参考文献】

中国期刊全文数据库 前2条

1 任磊;杜一;马帅;张小龙;戴国忠;;大数据可视分析综述[J];软件学报;2014年09期

2 张清国,黄竞伟;一个无向平面图的画图算法[J];小型微型计算机系统;2003年06期

，

本文编号：896930