论文部分内容阅读
随着社会网络服务(SNS)的迅速兴起,产生了越来越多的基于互联网的大规模社会网络数据。然而人们对数据的分析理解能力却远远落后于对数据的收集能力。如何更加有效地分析数据及展示分析结果,从而更有效地提高人们对所发现的特征的理解能力,正受到学者们越来越多的关注。图的可视化技术通过将数据以及数据之间的关系转化为图,使人们能够更加深入地理解数据。图的可视化的有效性依赖于布局结果的可读性。快速并且能够清晰地反映节点之间关系的强弱是海量社会网络图布局技术的关键。但是传统的图布局技术,或者无法清晰地反映出节点之间的关系强弱,或者在处理大规模数据方面遇到瓶颈。本文首先从社会网络图的化简和布局两个方面详细介绍了现有的海量社会网络图的可视化技术,同时列举了主要的图形交互技术。在此基础上本文提出了一种既能清晰地反映出节点之间关系的强弱又能够快速处理海量社会网络图的MWFR(Multi-level Weighted Fruchterman Reingold)布局算法,并通过实验证明了该算法的优越性。本文的主要贡献体现在以下三个方面:(1)定义了社会网络图中边的权重的表示形式,并在FR(Fruchterman Reingold)布局算法的基础上提出了一种能够可视化带权社会网络图的布局算法WFR。WFR布局算法将边的权重引入到FR布局算法的力学模型中,并对该力学模型做了适当的调整使其能够更加适合社会网络图的可视化需要。此外本文还提出了两种针对带权图的布局质量的评价标准。本文通过实验证明WFR布局算法无论在布局质量上还是在收敛时间上都要优于目前的主要算法。(2)在WFR布局算法的基础上,设计并实现了一种快速并能够清晰地反映节点关系强弱的海量社会网络图的布局算法——MWFR(Multi-level Weighted Fruchterman Reingold)布局算法。MWFR算法将WFR算法应用到压缩-求精模式的多级海量社会网络图布局算法中,并通过实验证明了MWFR布局算法在仅仅损失少量布局质量的情况下,可以显著地缩短海量社会网络图的布局时间。(3)基于上述理论的研究成果,本文设计并实现了一个社会网络图的可视化原型系统,在原型系统中集成了若干社会网络图的布局算法以及一些常用的可视化技术。通过原型系统提供的相应可视化手段可以发掘出那些隐藏在数据集之中的特性,便于选择相应的社会网络分析方案,同时还可以去掉噪声数据并对分析结果进行直观地评估。