Parallel graph layout algorithm for large-scale graph data

Zhiyuan CHENG; Yubin BAO; Fangling LENG

doi:10.11959/j.issn.2096-0271.2016050

您当前的位置：

首页 >

文章列表页 >

Parallel graph layout algorithm for large-scale graph data

research | 更新时间：2024-06-03

- Parallel graph layout algorithm for large-scale graph data
- Big data research Vol. 2, Issue 5, Pages: 2016050(2016)
- 作者机构：
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-0271.2016050
  CLC： TP391
- Online First：2016-09，
  
  Published：20 September 2016
- 稿件说明：
移动端阅览
Zhiyuan CHENG, Yubin BAO, Fangling LENG. Parallel graph layout algorithm for large-scale graph data[J]. Big data research, 2016, 2(5): 2016050.
DOI：

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 .

Views

1251

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Technology system based on the 5W communication model: a review of computational communication technology

Modeling and empirical research of information redundancy on online social media

Visualization analysis of shipping recruitment information based on Gephi

Research on Influence Diffusion in Social Network

Reliability enhancement-based link prediction algorithm for social network

Related Author

WANG Runqiang

HE Hongbo

WANG Xupeng

Yanqing HU

Fanhui MENG

Xin LU

Shuo QIN

Yang WANG

Related Institution

Computer Network Information Center, Chinese Academy of Sciences

College of Systems Engineering,National University of Defense Technology

School of Business,Central South University

Department of Public Health Sciences,Karolinska Institute,Stockholm

School of Data and Computer Science,Sun Yat-sen University

Postal code：100079
Tel：（010）53879208、53859533 Email：bdr@bjxintong.com.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09064830号-19 京公网安备11010802024621
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.
Total Visits：273427 Visits Today：333

⁰