论文部分内容阅读
随着大数据时代的到来,各个领域的数据规模呈爆发式增长。由于现实世界中大部分的关系型数据都可以建模成网络的形式,所以为了能有效挖掘网络数据中所隐含的信息,从数据中获取更多的潜在价值,大规模网络数据可视化技术的研究一直受到社会各界广泛的关注。基于力导向模型的网络布局算法由于其布局结果直观并且便于分析所以在网络可视化中占有举足轻重的地位。但是由于传统的网络布局可视化技术不容易满足研究人员对大规模网络数据的分析需求。为此本文针对大规模网络数据可视化技术进行了深入研究。本文首先介绍了网络数据可视化的基础理论和相关技术,并且根据国内外的研究现状总结了当前的网络可视化技术在处理大规模网络数据时所面临的挑战。针对这些挑战,本文提出了一个基于PageRank的网络布局算法用于提升大规模网络布局的质量和效率。为了更加有效地减少大规模网络布局算法的计算时间,本文提出了一个异构并行计算框架,并且通过实验证明了本框架的有效性。最后,基于以上两个成果,本文设计了相关的可视化分析系统用于高效探索大规模网络数据。本人的主要贡献点在以下三个方面:(1)基于PageRank的网络布局算法,文中提出了一个基于PageRank的力导向模型的算法。该算法引入了PageRank来完善节点的重力和斥力计算以改善布局质量;然后引入接近度中心性来预估节点在初始布局中的位置,使得算法在开始受力计算前获得一个高质量的初始布局;同时,又提出了基于PageRank的自适应步长用来平衡布局算法的效率和质量。最后通过实验证明,本算法在处理大规模网络数据时,可以得到一个质量较高的布局结果。(2)异构并行计算框架,当处理数十万甚至数百万节点的大规模网络数据时,大部分优化算法都无法在较短时间内获取布局结果。由于力导向模型的网络布局算法如基于PageRank的网络布局算法等在布局阶段都需要大量简单的迭代计算,比较适合采用GPU并行计算的技术,所以本文提出了一个CPU+GPU的异构并行计算框架,控制密集型逻辑在CPU上执行,计算密集型逻辑在GPU上执行,通过PCI-E总线通信。根据实验评估可以得出结论,本文所提出的异构并行计算框架可以有效减少大规模网络数据的布局计算时间。(3)本文结合上述的两个工作,开发了大规模网络综合态势可视分析系统。本系统提出了新的多层布局算法等方法解决大规模多层网络的可视分析所遇到的关键问题。该系统可以快速的呈现大规模多层网络的布局结果,实现了针对多层次网络的整体态势可视分析;网络目标节点的属性、通联、链路等变化行为的分析;网络重点节点分析筛选和与态势感知算法结合的可视分析等功能。研究人员借助该系统可以流畅的交互式分析大规模多层网络数据。