An advanced pre-positioning method for the force-directed graph visualization based on pagerank algorithm. (April 2015)

• Record Type: Journal Article
• Authors: Dong, Wenqiang; Wang, Fulai; Huang, Yu; Xu, Guangluan; Guo, Zhi; Fu, Xingyu; Fu, Kun
• Is Part Of: Computers & graphics. Volume 47(2015)
• Page Start: 24
• Page End: 33
• Publication Date: 2015-04
• Subjects: Graph visualization -- Graph drawing -- PageRank -- Force-directed; Computer graphics -- Periodicals; 006.6
• DOI: 10.1016/j.cag.2014.10.001
• Languages: English
• ISSNs: 0097-8493

Abstract

Abstract: Graph visualization techniques aim to help users obtain deep insights about the structure and evolution of graphs through minimizing visual confusion and real-time updating of the drawing. This demands high effectiveness of the drawing algorithms to produce layout of graphs with few edge crossings. However, the classical force-directed algorithms fail to satisfy this requirement. In this paper, we solve this problem by using a novel and heuristic pre-positioning method based on a variant of the PageRank algorithm. In our algorithmic framework, five models are proposed to calculate the importance degree of each vertex, the relation matrix of the vertices, the layer each vertex belongs to, the available placing coordinates and the matching coefficient between a vertex and a position. After the pre-positioning procedure of each layer, the classical force-directed algorithm is used to calculate the final position of each vertex. Experimental results have shown that our approach can reduce the computing time as well as the number of edge crossings. Abstract : Graphical abstract: Abstract : Highlights: We take the importance degree of the vertices into consideration. We propose a variant of the PageRank algorithm to calculate the importance degree for undirected graphs. We propose a model to calculate the coordinates of center vertices. We preposition the vertices according to the importance degree.