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

doi:10.11959/j.issn.2096-0271.2016050

Abstract

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.

Key words: force-directed algorithm, visualization analysis, social network, parallel layout algorithm

Zhiyuan CHENG, Yubin BAO, Fangling LENG. Parallel graph layout algorithm for large-scale graph data[J]. Big Data Research, 2016, 2(5): 12-21.

Figures/Tables 7

References 12

[1]	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.
[2]	REINGOLD E . Graph drawing by forcedirected placement[J]. Software:Practice and Experience, 1991,21(11): 1129-1164.
[3]	HU Y F . Efficient and high quality forcedirected graph drawing[J]. Mathematica Journal, 2005,10(6): 37-71.
[4]	HADANY R , HAREL D . A multi-scale algorithm for drawing graphs nicely[J]. Discrete Applied Mathematics, 2001,113(1): 3-21.
[5]	KAMADA T , KAWAI S . An algorithm for drawing general undirected graphs[J]. Information Processing Letters, 1989,31(1): 7-15.
[6]	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.
[7]	BREITKREUTZ B J , STARK C , TYERS M . Osprey:a network visualization system[J]. Genome Biology, 2003,4(3): 22-24.
[8]	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.
[9]	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.
[10]	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.
[11]	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
[12]	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.

Metrics

Recommended 0

No Suggested Reading articles found!

Parallel graph layout algorithm for large-scale graph data

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 12

Related Articles 5

Metrics

Recommended 0

[1]	Shuo QIN, Xin LU, Fanhui MENG, Yanqing HU. Modeling and empirical research of information redundancy on online social media [J]. Big Data Research, 2018, 4(5): 50-61.
[2]	Yang WANG, Ye TIAN, Tieshan LI, HENC.L.Philip C, Dongcheng PENG, Yihua ZHOU. Visualization analysis of shipping recruitment information based on Gephi [J]. Big Data Research, 2018, 4(3): 81-91.
[3]	Yingxia SHAO, Shicong FENG. Applications of social network analysis in public security [J]. Big Data Research, 2017, 3(2): 38-44.
[4]	Hui Gao, Jun Chen, Haibo Niu, Wei Luo. Internet Information Sources Automatic Discovery Technology for Scientific and Technological Intelligence [J]. Big Data Research, 2015, 1(4): 48-56.
[5]	Wei Chen. Research on Influence Diffusion in Social Network [J]. Big Data Research, 2015, 1(3): 82-98.