基于力学模型的图布局算法实验性对比研究

摘要

随着信息时代的到来，网络数据越来越多，然而人们收集数据的能力远远强于分析理解数据的能力，如何方便快速的分析收集到的网络数据成为了摆在人们面前的一道难题，这个问题也越来越受到学者们的关注。
　　图可视化技术通过将网络数据以及网络数据之间的关系转化为图，使人们能够更加清楚方便地理解网络数据所隐含的信息，其关键问题是如何在屏幕上清晰美观地展现节点以及节点之间的关系，因而图布局算法是研究图可视化的核心方法。
　　由于不同的网络数据有不同的布局要求，所以应该采取不同的图布局算法，并且各个图布局算法的性能各有优劣，为了使布局呈现想要的理想结果，采取合适的算法是必要的。针对此种情况，本文对T.M.J.Fruchterman和E.M.Reingold提出的FR算法、Davidson和David Harel提出的DH算法、Andreas Noack提出的LinLog算法三种图布局算法进行了比较研究，实验中采用大量的数据对三种图布局算法进行了测试。
　　本文的研究内容有以下几方面:
　　(1)简单介绍了图与图布局的基本概念以及图布局涉及到的常用美学规则，并详细阐述基于力学模型的几种基本图布局算法。
　　(2)提出了选取数据集的策略，用自选对称性数据测试算法的对称性效果，用随机产生的数据集测试了面积、边交叉、最长边、最长边与最短边的比值以及算法的运行效率。用真实的复杂网络数据集和计算机产生的网络测试了三种算法的聚类特性。
　　(3)用Java语言实现是了FR算法、LinLog算法、DH算法。
　　(4)对三种算法在美学规则、聚类特性以及运行效率做了详细比较，结合实验结果对三种算法的优缺点进行分析。

目录

摘要

第一章 引言

1．1 研究背景及意义

1．2 国内外研究现状

1．3 本文主要工作及论文组织

第二章 知识背景与相关工作

2．1 图布局算法的输入

2．1．1 图和简单图

2．1．2 图的规模和稠密程度

2．1．3 选取数据集

2．2 图布局算法的输出

2．2．1 图布局

2．2．2 图布局的评价标准

2．3 本章小结

第三章 基于力学模型的图布局算法概述

3．1 经典力学弹簧模型

3．2 FR算法

3．3 DH算法

3．4 Linlog算法

3．5 本章小结

第四章 算法实现与比较分析

4．1 算法实现的环境

4．2 算法比较结果与分析

4．2．1 美学规则的比较

4．2．2 聚类比较

4．2．3 算法运行效率的比较

4．3 本章小结

第五章 结论与展望

参考文献

发表文章目录

致谢

个人简况及联系方式

声明