FMR:基于FR的快速多层次算法
|
摘要
图可视化技术是可视化研究的重要内容,近年来大图的绘制问题一直是图可视化技术的焦点。为此,提出了一种快速多层次算法用于解决大图绘制问题。采用多层次方法作为算法的框架,以FR力导向算法的变体结合质心算法以及四叉树空间分解等方法对单层布局进行优化。另外,还使用了约束规范化和能量模型2种加速方法。实验表明,该算法具有高效的性能和良好的布局效果。其效率非常高,在单核CPU下,可以在大约5 s内很好地绘制出10 000个顶点的图。并与几种经典的算法进行了比较,也证明了该算法的有效性和实用性。此外,该算法易于实现,可被轻易推广到其他布局算法上,以加速其运算。
Graph visualization technology is an important part of visualization research. The drawing of large graphs has been the focus of graph visualization technology in recent years. This paper proposes a fast multilevel algorithm for solving large graph drawing problems. The algorithm uses a multilevel method as the framework of the algorithm. The present study uses a FR force-directed algorithm variant combined with centroid algorithm and quad-tree space decomposition method to refine the single-level layouts. Also, energy-model and constraint-normalization are used.Experiments show that the algorithm has high performance and good layout effect. The algorithm is of high efficiency, and under a single-core CPU, it can effectively draw a graph of 10,000 vertices in about 5 seconds. Through comparison with several classical algorithms, the effectiveness and practicability of the algorithm was proved. In addition, the algorithm is easy to implement and can be easily generalized to other layout algorithms to speed up its operations.
Graph visualization technology is an important part of visualization research. The drawing of large graphs has been the focus of graph visualization technology in recent years. This paper proposes a fast multilevel algorithm for solving large graph drawing problems. The algorithm uses a multilevel method as the framework of the algorithm. The present study uses a FR force-directed algorithm variant combined with centroid algorithm and quad-tree space decomposition method to refine the single-level layouts. Also, energy-model and constraint-normalization are used.Experiments show that the algorithm has high performance and good layout effect. The algorithm is of high efficiency, and under a single-core CPU, it can effectively draw a graph of 10,000 vertices in about 5 seconds. Through comparison with several classical algorithms, the effectiveness and practicability of the algorithm was proved. In addition, the algorithm is easy to implement and can be easily generalized to other layout algorithms to speed up its operations.
引文
[1]KEIM D A.Information visualization and visual data mining[J].IEEE Transactions on Visualization and Computer Graphics,2002,8(1):1-8.
[2]DIDIMO W,MONTECCHIANI F.Fast layout computation of hierarchically clustered networks:Algorithmic advances and experimental analysis[J].Information Sciences,2014,260(1):185-199.
[3]KAUFMANN M,WAGNER D.Drawing graphs methods and models[J].Methods and Models,2001,2025:293-377.
[4]EADES P A.A heuristic for graph drawing[J].Congressus Numerantium,1984,42(42):149-160.
[5]FRUCHTERMAN T M J,REINGOLD E M.Graph drawing by force-directed placement[M].Hoboken:John Wiley&Sons,1991:1129-1164.
[6]LIN C C,YEN H C.A new force-directed graph drawing method based on edge-edge repulsion[J].Journal of Visual Languages&Computing,2012,23(1):29-42.
[7]ORTMANN M,KLIMENTA M,BRANDES U.Asparse stress model[C]//International Symposium on Graph Drawing and Network Visualization.Cham:Springer International Publishing,2016:18-32.
[8]KOREN Y.On spectral graph drawing[C]//International Conference on Computing and Combinatorics.Berlin:Springer-Verlag,2003:496-508.
[9]EADES P,QUAN N,HONG S H.Drawing big graphs using spectral sparsification[C]//International Symposium on Graph Drawing and Network Visualization.Cham:Springer International Publishing,2017:272-286.
[10]MA K L,MUELDER C W.Large-scale graph visualization and analytics[J].Computer,2013,46(7):39-46.
[11]WALSHAW C.A multilevel algorithm for force-directed graph-drawing[C]//International Symposium on Graph Drawing.Berlin:Springer-Verlag,2000:171-182.
[12]HACHUL S,JüNGER M.Large-graph layout algorithms at work:An experimental study[J].Journal of Graph Algorithms and Applications,2007,11(2):345-369.
[13]HAREL D,KOREN Y.A fast multi-scale algorithm for drawing large graphs[J].Journal of Graph Algorithms and Applications,2002,6(3):183-196.
[14]HACHUL S.Drawing large graphs with a potential-field-based multilevel algorithm[C]//International Conference on Graph Drawing.Berlin:Springer-Verlag,2004:285-295.
[15]HU Y F.Efficient,high-quality force-directed graph drawing[J].Mathematica Journal,2005,10(1):37-71.
[16]MEYERHENKE H,N?LLENBURG M,SCHULZ C.Drawing large graphs by multilevel maxent-stress optimization[EB/OL].[2018-05-02].hattps://www.doc88.com/P-6661536104867.html.
[17]BADER D,MEYERHENKE H,SANDERS P,et al.Graph partitioning and graph clustering[J].Contemporary Mathematics,2013,588:240.
[18]MEYERHENKE H,SANDERS P,SCHULZ C.Partitioning complex networks via size-constrained clustering[C]//International Symposium on Experimental Algorithms.Cham:Springer International Publishing,2014:351-363.
[19]RAGHAVAN U N,ALBERT R,KUMARA S.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E,2007,76(3):036106.
[20]张世洲.海量社会网络图的可视化技术研究[D].哈尔滨:哈尔滨工业大学,2009.
[21]卢宇婷,林禹攸,彭乔姿,等.模拟退火算法改进综述及参数探究[J].大学数学,2015,31(6):96-103.
[22]HACHUL S,JüNGER M.An experimental comparison of fast algorithms for drawing general large graphs[J].Graph Drawing,2006,3843:235-250.
[23]GREENGARD L,ROKHLIN V.A fast algorithm for particle simulations[J].Journal of Computational Physics,1986,73(2):325-348.
[24]BARNES J,HUT P.A hierarchical O(N log N)force-calculation algorithm[J].Nature,1986,324(6096):446-449.
[25]TUNKELANG D.A numerical optimization approach to general graph drawing[R].Watson:IBM TJ Watson Research Center,1999.
[26]SALMON J K,WARREN M S.Skeletons from the treecode closet[J].Journal of Computational Physics,1993,111(1):136-155.
[27]HAREL D,KOREN Y.Graph drawing by high-dimensional embedding[C]//International Symposium on Graph Drawing.Berlin:Springer-Verlag,2002:207-219.
[28]FRISHMAN Y,TAL A.Multi-level graph layout on the GPU[J].IEEE Transactions on Visualization and Computer Graphics,2007,13(6):1310.
[29]HUANG W,EADES P,HONG S H,et al.Improving multiple aesthetics produces better graph drawings[J].Journal of Visual Languages and Computing,2013,24(4):262-272.
[2]DIDIMO W,MONTECCHIANI F.Fast layout computation of hierarchically clustered networks:Algorithmic advances and experimental analysis[J].Information Sciences,2014,260(1):185-199.
[3]KAUFMANN M,WAGNER D.Drawing graphs methods and models[J].Methods and Models,2001,2025:293-377.
[4]EADES P A.A heuristic for graph drawing[J].Congressus Numerantium,1984,42(42):149-160.
[5]FRUCHTERMAN T M J,REINGOLD E M.Graph drawing by force-directed placement[M].Hoboken:John Wiley&Sons,1991:1129-1164.
[6]LIN C C,YEN H C.A new force-directed graph drawing method based on edge-edge repulsion[J].Journal of Visual Languages&Computing,2012,23(1):29-42.
[7]ORTMANN M,KLIMENTA M,BRANDES U.Asparse stress model[C]//International Symposium on Graph Drawing and Network Visualization.Cham:Springer International Publishing,2016:18-32.
[8]KOREN Y.On spectral graph drawing[C]//International Conference on Computing and Combinatorics.Berlin:Springer-Verlag,2003:496-508.
[9]EADES P,QUAN N,HONG S H.Drawing big graphs using spectral sparsification[C]//International Symposium on Graph Drawing and Network Visualization.Cham:Springer International Publishing,2017:272-286.
[10]MA K L,MUELDER C W.Large-scale graph visualization and analytics[J].Computer,2013,46(7):39-46.
[11]WALSHAW C.A multilevel algorithm for force-directed graph-drawing[C]//International Symposium on Graph Drawing.Berlin:Springer-Verlag,2000:171-182.
[12]HACHUL S,JüNGER M.Large-graph layout algorithms at work:An experimental study[J].Journal of Graph Algorithms and Applications,2007,11(2):345-369.
[13]HAREL D,KOREN Y.A fast multi-scale algorithm for drawing large graphs[J].Journal of Graph Algorithms and Applications,2002,6(3):183-196.
[14]HACHUL S.Drawing large graphs with a potential-field-based multilevel algorithm[C]//International Conference on Graph Drawing.Berlin:Springer-Verlag,2004:285-295.
[15]HU Y F.Efficient,high-quality force-directed graph drawing[J].Mathematica Journal,2005,10(1):37-71.
[16]MEYERHENKE H,N?LLENBURG M,SCHULZ C.Drawing large graphs by multilevel maxent-stress optimization[EB/OL].[2018-05-02].hattps://www.doc88.com/P-6661536104867.html.
[17]BADER D,MEYERHENKE H,SANDERS P,et al.Graph partitioning and graph clustering[J].Contemporary Mathematics,2013,588:240.
[18]MEYERHENKE H,SANDERS P,SCHULZ C.Partitioning complex networks via size-constrained clustering[C]//International Symposium on Experimental Algorithms.Cham:Springer International Publishing,2014:351-363.
[19]RAGHAVAN U N,ALBERT R,KUMARA S.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E,2007,76(3):036106.
[20]张世洲.海量社会网络图的可视化技术研究[D].哈尔滨:哈尔滨工业大学,2009.
[21]卢宇婷,林禹攸,彭乔姿,等.模拟退火算法改进综述及参数探究[J].大学数学,2015,31(6):96-103.
[22]HACHUL S,JüNGER M.An experimental comparison of fast algorithms for drawing general large graphs[J].Graph Drawing,2006,3843:235-250.
[23]GREENGARD L,ROKHLIN V.A fast algorithm for particle simulations[J].Journal of Computational Physics,1986,73(2):325-348.
[24]BARNES J,HUT P.A hierarchical O(N log N)force-calculation algorithm[J].Nature,1986,324(6096):446-449.
[25]TUNKELANG D.A numerical optimization approach to general graph drawing[R].Watson:IBM TJ Watson Research Center,1999.
[26]SALMON J K,WARREN M S.Skeletons from the treecode closet[J].Journal of Computational Physics,1993,111(1):136-155.
[27]HAREL D,KOREN Y.Graph drawing by high-dimensional embedding[C]//International Symposium on Graph Drawing.Berlin:Springer-Verlag,2002:207-219.
[28]FRISHMAN Y,TAL A.Multi-level graph layout on the GPU[J].IEEE Transactions on Visualization and Computer Graphics,2007,13(6):1310.
[29]HUANG W,EADES P,HONG S H,et al.Improving multiple aesthetics produces better graph drawings[J].Journal of Visual Languages and Computing,2013,24(4):262-272.