面向大规模图数据的并行图布局算法

程致远; 鲍玉斌; 冷芳玲

doi:10.11959/j.issn.2096-0271.2016050

您当前的位置：

首页 >

文章列表页 >

面向大规模图数据的并行图布局算法

研究 | 更新时间：2024-06-03

- 面向大规模图数据的并行图布局算法
- Parallel graph layout algorithm for large-scale graph data
- 大数据 2016年2卷第5期页码：2016050
- 作者机构：
- 作者简介：
  
  [ "程致远（1991-），男，东北大学计算机科学系硕士生，主要研究方向为云计算、数据可视化。" ]
  [ "鲍玉斌（1968-），男，博士，东北大学计算机科学系教授，主要研究方向为联机分析处理、云计算、图数据管理等。" ]
  [ "冷芳玲（1978-），女，博士，东北大学计算机科学系讲师，主要研究方向为大数据分析、数据可视化。" ]
- 基金信息：
  
  国家自然科学基金资助项目;The National Natural Science Foundation of China(61433008)
- DOI：10.11959/j.issn.2096-0271.2016050
  中图分类号： TP391
- 网络首发：2016-09，
  
  纸质出版：2016-09-20
- 稿件说明：
移动端阅览
程致远, 鲍玉斌, 冷芳玲. 面向大规模图数据的并行图布局算法[J]. 大数据, 2016,2(5):2016050.

Zhiyuan CHENG, Yubin BAO, Fangling LENG. Parallel graph layout algorithm for large-scale graph data[J]. Big data research, 2016, 2(5): 2016050.
程致远, 鲍玉斌, 冷芳玲. 面向大规模图数据的并行图布局算法[J]. 大数据, 2016,2(5):2016050. DOI： 10.11959/j.issn.2096-0271.2016050.

Zhiyuan CHENG, Yubin BAO, Fangling LENG. Parallel graph layout algorithm for large-scale graph data[J]. Big data research, 2016, 2(5): 2016050. DOI： 10.11959/j.issn.2096-0271.2016050.

摘要

图模型是一种广泛使用的建模工具。图的可视化作为一种直观的图数据分析工具被广泛使用。图数据可视化中最关键的技术是图布局算法，但是目前并没有高效的并行图布局算法，因此目前对于海量图数据的可视化是一个挑战性问题。针对这一问题，在力导向布局算法基础上，忽略弱关联顶点间的斥力计算，提出了k-friend布局算法；并针对海量图数据设计了高效的并行图布局算法。在人工和实际数据集上的测试结果表明，在布局质量降低可容忍的情况下，该算法大幅度提升了布局的速度。

Abstract

Graph models are modeling tools which are widely used.Data visualization techniques have been widely used as intuitive data analysis tools.Graph layout algorithm is the most critical technique of graph visualization

while there are no effective parallel graph layout algorithms.So to study on visualization of massive graph data is a challenging problem.Aiming at this problem

based on the force-directed layout algorithm and ignoring the repulsion force computation between weakly associated vertexes partially

a k-friend approximate layout algorithm was proposed

and an effective parallel layout algorithm was designed for massive graph data.The experimental results on artificial and real dataset show that the algorithms proposed greatly improve the layout speed.

关键词

Keywords

references

QUIGLEY A , EADES P . FADE:graph drawing,clustering,and visual abstraction [C ] // The 8th Symposium on Graph Drawing,September 20-23,2000,Colonial Williamsburg,VA,USA . London : Springer-Verlag , 2000 : 197 - 210 .

REINGOLD E . Graph drawing by forcedirected placement [J ] . Software:Practice and Experience , 1991 , 21 ( 11 ): 1129 - 1164 .

HU Y F . Efficient and high quality forcedirected graph drawing [J ] . Mathematica Journal , 2005 , 10 ( 6 ): 37 - 71 .

HADANY R , HAREL D . A multi-scale algorithm for drawing graphs nicely [J ] . Discrete Applied Mathematics , 2001 , 113 ( 1 ): 3 - 21 .

KAMADA T , KAWAI S . An algorithm for drawing general undirected graphs [J ] . Information Processing Letters , 1989 , 31 ( 1 ): 7 - 15 .

GAJER P , GOODRICH M T , KOBOUROV S G . A fast multi-dimensional algorithm for drawing large graphs [J ] . Computational Geometry:Theory and Applications , 2004 , 29 ( 1 ): 3 - 18 .

BREITKREUTZ B J , STARK C , TYERS M . Osprey:a network visualization system [J ] . Genome Biology , 2003 , 4 ( 3 ): 22 - 24 .

ELMQVIST N , DO T N , GOODELL H , et al . ZAME:interactive large scale graph visualization [C ] // IEEE Pacific Visualization Symposium,March 5-7,2008,Kyoto,Japan . New Jersey : IEEE Press , 2008 : 215 - 222 .

BECKER R A , EICK S G , WILKS A R . Visualizing network data [J ] . IEEE Trans on Visualization and Computer Graphics , 1995 , 1 ( 1 ): 16 - 28 .

TIKHONOVA A , MA K L . A scalable parallel force-directed graph layout algorithm [C ] // Eurographics Conference on Parallel Graphics and Visualization,April 14-15,2008,Crete,Greece . New Jersey : ACM Press , 2008 : 25 - 32 .

JACOMY M , VENTURINI T , HEYMANN S , et al . ForceAtlas2,a continuous graph layout algorithm for handy network visualization designed for the gephi software [J ] . Plos One , 2014 , 9 ( 6 ):e98679

CHAN S M , CHUA K S , LECKIE C , et al . Visualisation of power-law network topologies [C ] // The 11th IEEE International Conference on Networks(ICON2003),September 28-October 1,2003,Sydney,NSW,Australia . New Jersey : IEEE Press , 2003 : 69 - 74 .

浏览量

1251

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于5W传播模型的技术体系：计算传播技术综述

在线社交媒体信息冗余现象建模与实证研究

基于Gephi的航运招聘信息可视化分析

社交网络影响力传播研究

基于可靠性增强的社交网络链接预测算法