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

doi:10.11959/j.issn.2096-0271.2016050

大数据 ›› 2016, Vol. 2 ›› Issue (5): 12-21.doi: 10.11959/j.issn.2096-0271.2016050

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

程致远,鲍玉斌,冷芳玲

东北大学计算机科学系，辽宁沈阳 110819

出版日期:2016-09-20 发布日期:2018-02-08
基金资助:
国家自然科学基金资助项目

Parallel graph layout algorithm for large-scale graph data

Zhiyuan CHENG,Yubin BAO,Fangling LENG

Department of Computer Science of Northeastern University,Shenyang 110819,China

Online:2016-09-20 Published:2018-02-08
Supported by:
The National Natural Science Foundation of China

摘要/Abstract

摘要：

图模型是一种广泛使用的建模工具。图的可视化作为一种直观的图数据分析工具被广泛使用。图数据可视化中最关键的技术是图布局算法，但是目前并没有高效的并行图布局算法，因此目前对于海量图数据的可视化是一个挑战性问题。针对这一问题，在力导向布局算法基础上，忽略弱关联顶点间的斥力计算，提出了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.

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

程致远, 鲍玉斌, 冷芳玲. 面向大规模图数据的并行图布局算法[J]. 大数据, 2016, 2(5): 12-21.

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

图/表 7

图1

图2

图3

图4

图5

图6

图7

参考文献 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.

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

Parallel graph layout algorithm for large-scale graph data

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 12

相关文章 4

Metrics

推荐阅读 0

[1]	秦烁, 吕欣, 孟凡辉, 胡延庆. 在线社交媒体信息冗余现象建模与实证研究[J]. 大数据, 2018, 4(5): 50-61.
[2]	王扬, 田野, 李铁山, 陈俊龙, 彭东成, 周义华. 基于Gephi的航运招聘信息可视化分析[J]. 大数据, 2018, 4(3): 81-91.
[3]	邵蓥侠, 冯是聪. 社交网络分析在公共安全领域的应用[J]. 大数据, 2017, 3(2): 38-44.
[4]	陈卫. 社交网络影响力传播研究[J]. 大数据, 2015, 1(3): 82-98.