论文总字数：28966字

摘 要

图数据应用广泛，相应的可视化网络分析越发重要，但市面上仍缺乏面向普通用户的高灵活度大型图交互探索工具。本文设计了丰富友好的交互操作，直观清晰的可视化数据表示方法，灵活便捷的用户界面。针对大型图场景，本文从三个角度切入：一是传统力导向布局的计算代价极高，本文对采用Barnes-Hut近似的力导向布局算法进行并行改进，有效提高了布局速度；二是为粗略概括全图结构信息采用热度图来表示图数据；三是针对热度图，设计了一种基于空间的单元采样算法，以减少数据规模。在此基础上，本文开发了一个基于网页的大型图可视化探索系统，提供可视化建图功能和全局探索、局部探索两种探索模式，以及三个典型图分析算法的迭代展示。用户能够通过热度图和节点-连接图分别探索网络的全貌和局部，按照自顶向下和自底向上两种流程进行探索。本文还在三个真实数据集上测试了并行布局算法和采样算法的性能，展示了方法的可用性和有效性。

关键词：大型网络探索,可视化分析,并行力导向布局,采样

Abstract

The application of graph data is extensive, and visual analysis is becoming more and more important, but there is still a lack of flexible scalable interactive exploration tools for ordinary users. In this paper, I designed rich and friendly interactions, intuitive and clear visual representation, flexible and convenient user interface. For the large graph scene, I studied in three aspects: First, the computational cost of the traditional force-directed layout is extremely high. I improved the layout speed effectively by parallelizing the approximation of force-directed layout algorithm using Barnes-Hut approximation, and the second is to use the heat map to represent data in order to generalize the rough structure information of the whole graph; the third is to design a space-based unit sampling algorithm for the heat map to reduce the data size. On this basis, I developed a web-based large graph visualization exploration system, which provides a visual function to create a graph in the database, two exploration modes including global exploration and local exploration, and the iterative display of three typical graph analysis algorithms. Users can explore the whole graph and part of the graph through the heat map and the node-link diagram respectively, and explore according to the top-down and bottom-up processes. I also tested the performance of the paralleled layout algorithm and sampling algorithm on three real data sets, showing the availability and effectiveness of the method.

KEY WORDS: large graph exploration, visualization analysis, paralleled force-directed layout, sample

目 录

摘要 I

Abstract II

第一章 绪论 1

1.1课题的背景和意义 1

1.2国内外研究现状 2

1.3研究内容与组织结构 3

第二章 相关工作 4

2.1图数据的可视化表示 4

2.2图数据布局算法 4

2.2.1树形布局 4

2.2.2依据附带信息布局 4

2.2.3力导向布局 4

2.3采样算法 5

第三章 系统功能设计 6

3.1导航 6

3.2建图模块 7

3.3全局探索模块 10

3.4局部探索模块 11

3.5探索流程与系统使用场景 16

第四章 系统架构设计 18

4.1技术路线 18

4.2可视化系统架构与实现 18

4.2.1用户界面 19

4.2.2可视化引擎 19

4.2.3中间层接口 21

4.2.4SQLGraph 21

第五章 算法设计 22

5.1改进的并行近似力导向布局算法 22

5.2空间单元采样算法 24

5.3迭代展示算法模块 24

5.3.1最短路径 25

5.3.2网页排名 25

5.3.3社区发现 25

第六章 实验 26

6.1数据集 26

6.2性能 26

6.2.1布局算法 26

6.2.2采样算法 27

第七章 结论 30

参考文献 31

致 谢 33

第一章 绪论

1.1课题的背景和意义

信息爆炸时代，社会学、生物建模、金融交易等领域产生海量描述实体间的关系的网络数据。通过技术手段分析这些数据，抽取有用信息，能够指导研究和生产，这也是大数据时代的要求。图是一种抽象网络数据的有力工具，能够将数据简单地抽象为描述实体的节点和描述关联关系的边。如一个微博社交网络中，节点代表账户，边代表账户间的关注关系。传统的图分析系统，虽能很好地挖掘图上的信息，但无法为用户提供直观认识。图可视化恰恰能解决这一问题，一方面能够将网络数据中的关联关系以直观的方式交互式呈现给用户，另一方面能够对如团块发现、频繁子图挖掘等图分析算法的结果进行直观展示。总之，能够帮助用户在探索过程中逐步迭代地概括、解释、分析数据^[1]。图可视化拥有直观性和交互性两点优势。一方面设计代表节点和边的符号或其他表示方法，并在空间中合理安排，进而突出图的结构信息。另一方面设计交互操作，提供可交互的展示界面，让用户极大地参与探索分析图的过程，符合视觉和认知的要求。

图可视化的一个关键环节是图结构的空间表示，即图的布局。它是指将图中的节点映射为二维平面中的某个位置。图的布局应符合两点要求：可解释和易于可视化。节点的位置应是有意义的，如相关的节点位置更近。节点位置的距离关系不应过远或过近，绘制成具有大小的点时，过近会造成重叠，过远难以分辨距离的区别。

剩余内容已隐藏，请支付后下载全文，论文总字数：28966字