基于图匹配的分层布局算法

doi:10.3969/j.issn.1006-2475.2015.08.022

计算机与现代化

基于图匹配的分层布局算法

国防科学技术大学电子科学与工程学院,湖南长沙410073

收稿日期:2015-03-23 出版日期:2015-08-08 发布日期:2015-08-19
作者简介:赵玉聪(1990-),男,辽宁营口人,国防科学技术大学电子科学与工程学院硕士研究生,研究方向:信息可视化; 钟志农(1975-),男,副教授,博士,研究方向:数据挖掘与信息处理; 吴烨(1986-),讲师，博士,研究方向：信息系统与信息处理技术。

A Hierarchical Layout Algorithm Based on Graph Matching

College of Electronic Science and Engineering, National University of Defense Technology, Changsha 410073, China

Received:2015-03-23 Online:2015-08-08 Published:2015-08-19

摘要/Abstract

摘要： 针对节点数目较大并且度数比较平均的无向图，根据分层扩展的思想，提出一种基于图匹配的分层布局算法（Graph Matching Hierarchy，GMH）。基于图匹配思想对大图进行递归化简，然后应用FR算法对最粗化图进行布局，最后利用质心布局算法对图进行扩展。实验结果表明，GMH算法能够提高可视化效率，改善布局效果，且分层布局的结果更易于理解。


关键词: 可视化, 无向图, 图匹配, 质心扩展, 分层布局

Abstract: In order to draw the undirected graph with big and even degrees, we propose a hierarchical layout algorithm based on graph matching (GMH). Firstly, a series of coarser and coarser graphs are generated by graph matching. Secondly, the optimal FR layout for the coarsest graph can be found cheaply. In the end, the layout on the coarser graphs is recursively prolonged to the finer graphs by the mass-center method. The new algorithm can not only advance the efficiency of graph visualization and improve the effect of layout, but also show a series of hierarchical graphs.


Key words: visualization, undirected graph, graph matching, mass-center prolong, hierarchical layout

中图分类号:

TP393

赵玉聪,钟志农,吴烨,景宁. 基于图匹配的分层布局算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2015.08.022.

ZHAO Yu-cong, ZHONG Zhi-nong, WU Ye, JING Ning. A Hierarchical Layout Algorithm Based on Graph Matching[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2015.08.022.

参考文献

［1］杨彦波,刘滨,祁明月,等. 信息可视化研究综述［J］. 河北科技大学学报, 2014,35(1):91-102.
［2］黄竞伟,康立山,陈毓屏. 一个新的无向图画图算法［J］. 软件学报， 2000,11(1):138-142.
［3］黄竞伟. 基于遗传算法的画图算法研究［D］. 武汉:武汉大学, 2001.
［4］ Koren Y, Carmel L, Harel D. Drawing huge graphs by algebraic multigrid optimization［J］. Multiscale Modeling and Simulation, 2003,1(4):645-673.
［5］〖JP2〗Harel D, Koren Y. Graph drawing by high-dimensional embedding［J］. Journal of Graph Algorithms and Application, 2004,8(2):195-214.
［6］〖JP2〗Eades P. A heuristic for graph drawing［J］. Congresses Numerantium, 1984,42:149-160.
［7］ Kamada T, Kawai S. An algorithm for drawing general undirected graphs［J］. Information Processing Letters, 1989,31(1):7-15.
［8］ Davidson R, Harel D. Drawing graphs nicely using simulated annealing［J］. ACM Transactions on Graphics(TOG), 1996,15(4):301-331.
［9］ Fruchterman T M J, Reingold E M. Graph drawing by force-directed placement［J］. Software-Practice and Experience, 1991,21(11):1129-1164.
［10］Davis L. Genetic algorithms and simulated annealing［M］. Morgan Kaufmann Publishers Inc., 1987.
［11］Rodrigues J F, Tong Hanghang, Pan Jiayu, et al. Large graph analysis in the GMine system［J］. IEEE Transactions on Knowledge & Data Engineering, 2013,25(1):106-118.
［12］Hadany R, Harel D. A multi-scale algorithm for drawing graphs nicely［J］. Discrete Applied Mathematics, 2001,113(1):3-21.
［13］Harel D, Koren Y. A fast multi-scale method for drawing large graphs［J］. Journal of Graph Algorithms and Applications, 2002,6(3):179-202.
［14］Walshaw C. A multilevel algorithm for force-directed graph drawing［J］. Journal of Graph Algorithms and Applications, 2003,7(3):253-285.
［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.［16］Hu Yifan, Scott J A. A multilevel algorithm for wavefront reduction［J］. SIAM Journal on Scientific Computing, 2001,23(4):1352-1375.
［17］Hu Yifan. Efficient and high quality force-directed graph drawing［J］. The Mathematica Journal, 2005,10(1):37-71.

[1]	刘聪, 聂芸, 王国伟. 空天三维仿真的实体多元表达方法[J]. 计算机与现代化, 2023, 0(04): 90-94.
[2]	田茂春, 邹显勇, 杨跃, 范光伟, 赖杭. 基于Web的风场三维动态可视化设计与仿真[J]. 计算机与现代化, 2022, 0(04): 97-102.
[3]	刘锟, 曾曦, 邱梓珩, 陈周国, . 基于RoBERTa-WWM 和HDBSCAN的文本聚类算法[J]. 计算机与现代化, 2022, 0(03): 48-52.
[4]	刘羽飞, 张绪美, 梁晓磊. 基于CiteSpace的AGV路径规划研究热点分析[J]. 计算机与现代化, 2021, 0(05): 112-119.
[5]	郭锦平, 边若鹏. MATLAB环境下数据驱动故障检测工具箱设计[J]. 计算机与现代化, 2021, 0(01): 81-86.
[6]	刘嘉昕, 游珍, 黄捷文, 陈家祥, 胡洪文, . 基于庐山三维场景的图算法虚拟仿真系统研究[J]. 计算机与现代化, 2020, 0(12): 90-98.
[7]	王晓宇, 孙卡. 基于osgEarth的三维虚拟校园可视化[J]. 计算机与现代化, 2020, 0(11): 89-93.
[8]	吴忠得, 罗晓芳, 侯增选, 段鹏轩, 李楠楠. 基于三维地球场景的干扰条件雷达探测范围可视化方法[J]. 计算机与现代化, 2020, 0(10): 90-96.
[9]	张骋, 苗新蕊, 牟雪曼. 高精地图车道的三维可视化[J]. 计算机与现代化, 2020, 0(08): 21-25.
[10]	薛伟莲，赵娣，张颖超. 室内定位研究综述[J]. 计算机与现代化, 2020, 0(05): 80-.
[11]	李雨妮，王鹏，肖建力. 一种使用多维度直方图匹配的图像风格迁移算法[J]. 计算机与现代化, 2019, 0(02): 15-.
[12]	王永胜1,2，李晖1,2，陈梅1,2，戴震宇1,2，朱明3. VISDMiner：一个交互式数据挖掘过程可视化系统[J]. 计算机与现代化, 2018, 0(06): 72-.
[13]	曹仲,李付琛,杨皓斐. 基于手机信令数据的城市区域间交通流分析及可视化[J]. 计算机与现代化, 2018, 0(03): 116-.
[14]	栗家棋，郑昊. 基于矢量地图数据的异构混合快速绘制框架[J]. 计算机与现代化, 2018, 0(01): 56-61.
[15]	刘戈1，刘云飞2. 一种环境质量数据可视化与可视分析系统[J]. 计算机与现代化, 2018, 0(01): 62-68.

基于图匹配的分层布局算法

A Hierarchical Layout Algorithm Based on Graph Matching

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价