一种面向交互的渐进式图布局算法

doi:10.3969/j.issn.1006-2475.2014.08.025

计算机与现代化 ›› 2014, Vol. 0 ›› Issue (8): 113-118.doi: 10.3969/j.issn.1006-2475.2014.08.025

一种面向交互的渐进式图布局算法

（国防科学技术大学电子科学与工程学院，湖南长沙410073）

收稿日期:2014-04-14 出版日期:2014-08-15 发布日期:2014-08-19
作者简介:李杰(1989-),男,四川内江人,国防科学技术大学电子科学与工程学院硕士研究生,研究方向：信息可视化；钟志农(1975-),男,副教授，博士,研究方向：数据挖掘与信息处理；吴烨(1986-),男,博士研究生,研究方向：信息系统与信息技术；姜伟(1989-)，男，硕士研究生，研究方向：文本关系提取。

An Interactive Oriented and Incremental Algorithm for Graph Layout

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

Received:2014-04-14 Online:2014-08-15 Published:2014-08-19

摘要/Abstract

摘要：

针对力导引算法缺乏交互性、效率低、美观性不足，提出一种面向交互的渐进式图布局算法IIA（Interaction Oriented and

Incremental Algorithm）。该算法先对一小部分图数据进行可视化，然后根据用户的选择从已可视化的部分渐进式扩展，再利用改进

的算法对扩展部分进行可视化。实验结果表明：IIA算法不仅能与用户交互，而且提高了可视化的效率，在美观性上也有所改善。

关键词: 力导引, 可视化, 交互式, 渐进式, 无向图

Abstract:

Aiming at the force-directed algorithm lacking of interactivity and aesthetics and low efficiency, an

interaction oriented and incremental algorithm for graph visualization is proposed. Firstly, the algorithm

visualizes a small portion of the graph data, secondly, extends the visualized data by user’s selection, and then

draws the extended data with the new algorithm. The new algorithm can not only interact with users, but also

improve the efficiency of visualization and the aesthetics.

Key words: force-directed, visualization, interaction, increment, undirected graph

中图分类号:

TP301.6

李杰，钟志农，吴烨，姜伟. 一种面向交互的渐进式图布局算法[J]. 计算机与现代化, 2014, 0(8): 113-118.

LI Jie, ZHONG Zhi-nong, WU Ye, JIANG Wei. An Interactive Oriented and Incremental Algorithm for Graph Layout[J]. Computer and Modernization, 2014, 0(8): 113-118.

［1］杨彦波,刘滨,祁明月. 信息可视化研究综述［J］. 河北科技大学学报, 2014,35(1):91-102.
［2］黄竞伟,康立山,陈毓屏. 一个新的无向图画图算法［J］. 软件学报, 2000,11(1):138-142.
［3］ Eades P. A heuristci graph drawing［C］// Congressus Numerantium. 1984,42（11）:149-160.
［4］ Kamada T, Kawai S. An algorithm for drawing general undirected graphs［J］. Information Processing Letters,

1989,31(1):7-15.
［5］ Fruchterman T M J, Reingold E M. Graph drawing by force-directed placement［J］. Software-Practice and

Experience, 1991,21(11):1129-1164.
［6］ Walshaw C. A multilevel algorithm for force-directed graph drawing［C］// Proceedings of the 8th

International Symposium on Graph Drawing. 2001,1984:171-182.
［7］ Hadany R, Harel D. A multi-scale algorithm for drawing graphs nicely［J］. Discrete Applied Mathematics,

2001,113(1):3-21.
［8］ Hu Yifan. Efficient and high-quality force-directed graph drawing［J］. The Mathematica Journal,

2005,10:37-71.
［9］ Rodrigues J F, Tong Hanghang, Pan Jiayu, et al. Large graph analysis in the GMine system［J］. IEEE

Transactions on Knowledge and Data Engineering, 2013,25(1):106-118.
［10］张清国,黄竞伟. 一个无向平面图的画图算法［J］. 小型微型计算机系统, 2003,24(6):972-975.
［11］黄竞伟. 基于遗传算法的画图算法研究［D］. 武汉：武汉大学, 2001.
［12］张清国,叶俊民,张维,等. 用遗传算法画无向图［J］. 计算机工程与科学, 2006,28(6):58-61.
［13］Harel D, Koren Y. Graph drawing by high-dimensional embedding［C］// Proceedings of the 9th International

Symposium on Graph Drawing. 2002:207-219.
［14］Becker R A, Eick S G, Wilks A R. Visualizing network data［J］. IEEE Transactions on Visualization and

Computer Graphics, 1995,1(1):16-28.
［15］Lim C P, Wang S L, Tan K S., et al. Use of the circle segments visualization technique for neural network

feature selection and analysis［J］. Neurocomputing, 2010,73(4/6):613-621.
［16］Van Laarhoven P J M, Aarts E H L. Simulated Annealing［M］. Springer Netherlands, 1987.
［17］Davis L. Genetic Algorithms and Simulated Annealing［M］. OSTI, 1987.

[1]	汪显顺, 熊卿智, 万磊, 李祥, 林重汕, 金安安. 基于知识图谱的区域企业关联可视化及关系挖掘[J]. 计算机与现代化, 2024, 0(08): 11-16.
[2]	刘洋1, 黄志2, 徐娟1, 高鹏1, 陈旭辉1. 基于分布式的省级气象数据中心硬件监控告警系统[J]. 计算机与现代化, 2024, 0(07): 41-46.
[3]	张高义1, 徐杨1, 2, 曹斌1, 3, 李毅飞3. 基于数字孪生的铝电解槽三维可视化监控系统[J]. 计算机与现代化, 2024, 0(05): 104-109.
[4]	蔡泗沐, 王立斌. 一种通用可组合安全的非交互式承诺方案[J]. 计算机与现代化, 2024, 0(01): 6-12.
[5]	刘聪, 聂芸, 王国伟. 空天三维仿真的实体多元表达方法[J]. 计算机与现代化, 2023, 0(04): 90-94.
[6]	田茂春, 邹显勇, 杨跃, 范光伟, 赖杭. 基于Web的风场三维动态可视化设计与仿真[J]. 计算机与现代化, 2022, 0(04): 97-102.
[7]	刘锟, 曾曦, 邱梓珩, 陈周国, . 基于RoBERTa-WWM 和HDBSCAN的文本聚类算法[J]. 计算机与现代化, 2022, 0(03): 48-52.
[8]	刘羽飞, 张绪美, 梁晓磊. 基于CiteSpace的AGV路径规划研究热点分析[J]. 计算机与现代化, 2021, 0(05): 112-119.
[9]	郭锦平, 边若鹏. MATLAB环境下数据驱动故障检测工具箱设计[J]. 计算机与现代化, 2021, 0(01): 81-86.
[10]	刘嘉昕, 游珍, 黄捷文, 陈家祥, 胡洪文, . 基于庐山三维场景的图算法虚拟仿真系统研究[J]. 计算机与现代化, 2020, 0(12): 90-98.
[11]	王晓宇, 孙卡. 基于osgEarth的三维虚拟校园可视化[J]. 计算机与现代化, 2020, 0(11): 89-93.
[12]	吴忠得, 罗晓芳, 侯增选, 段鹏轩, 李楠楠. 基于三维地球场景的干扰条件雷达探测范围可视化方法[J]. 计算机与现代化, 2020, 0(10): 90-96.
[13]	张骋, 苗新蕊, 牟雪曼. 高精地图车道的三维可视化[J]. 计算机与现代化, 2020, 0(08): 21-25.
[14]	薛伟莲，赵娣，张颖超. 室内定位研究综述[J]. 计算机与现代化, 2020, 0(05): 80-.
[15]	王永胜1,2，李晖1,2，陈梅1,2，戴震宇1,2，朱明3. VISDMiner：一个交互式数据挖掘过程可视化系统[J]. 计算机与现代化, 2018, 0(06): 72-.

一种面向交互的渐进式图布局算法

An Interactive Oriented and Incremental Algorithm for Graph Layout

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价