论文部分内容阅读
随着Facebook,Twitter等网站的兴起,社交网络的规模日趋复杂和庞大。通常,如何从这些庞杂的网络信息中挖掘出有潜在价值的模式和结构是数据挖掘领域中富有挑战性的热点话题之一。为了处理如此规模庞大的图数据,一些大图处理平台应运而生,比如Pregel、Giraph、Graphlab等,这些系统都是BSP模型,BSP程序从开始到结束要经过N个超步。但是在迭代计算过程中,图的结构和顶点的值、标签的变化对用户是不可见的,为了使用户能够更好的理解大图迭代计算的过程,辅助用户分析大规模的图数据,挖掘数据中隐藏的信息,本文提出了面向大图迭代计算过程的可视化。此外,本文将图数据分为静态数据和动态数据,为了能够实现迭代计算过程的可视化,首先需要实现静态数据的可视化,但是目前的图可视化系统所能显示的图数据的规模是有限的,并且经常会出现运行时间较长、可视化效果不佳和空间利用率低等问题。所以本文提出了大图分层可视化的模型,设计并实现了大图可视化系统和面向大图迭代计算的可视化,本文的贡献如下:(1)设计并实现了基于分层的大图可视化系统。首先,本文通过分析传统的标签传播算法,提出了一种标签传播策略,设计了一种快速、高效的大图聚类算法;然后依据聚簇合并后的模块度大小,提出了小聚簇的合并策略;将这两个算法作为大图可视化系统的预处理过程的依据,最终实现了基于分层的大图可视化系统。(2)本文在分析传统力导向布局算法和图可视化系统分层显示的特点的基础上,提出了基于边权的力导向布局算法,并使用Bary-Centralizing算法来优化初始布局,进而加快布局算法的收敛。最后,提出了该布局算法的评价标准。(3)在实现的大图可视化系统的基础上,研究并实现了面向大图迭代计算过程的可视化模型,即能够根据用户需求,显示每一步或每隔几步的迭代计算过程,便于用户对图算法的迭代计算过程有个更直观的了解。实验表明,在大规模社交网络中,本文设计并实现的大图可视化系统能够有效地可视化图数据信息,并且所提出的布局算法布局效率更高,最终能够实现大图迭代计算过程的可视化。