Please wait a minute...
Advanced Search
现代图书情报技术  2014, Vol. 30 Issue (9): 33-43    DOI: 10.11925/infotech.1003-3513.2014.09.05
  知识组织与知识管理 本期目录 | 过刊浏览 | 高级检索 |
曾新红1,2, 蔡庆河2, 黄华军1, 林伟明1
1. 深圳大学图书馆 深圳 518060;
2. 深圳大学计算机与软件学院 深圳 518060
Research on Non-uniform Node Clustered Graph Layout Algorithm for Visualization Based on Force Directed Model
Zeng Xinhong1,2, Cai Qinghe2, Huang Huajun1, Lin Weiming1
1. Shenzhen University Library, Shenzhen 518060, China;
2. College of Computer and Software, Shenzhen University, Shenzhen 518060, China
全文: PDF(2268 KB)   HTML  
输出: BibTeX | EndNote (RIS)      

[目的] 提出一种基于力导向模型的非一致节点群组布局算法,以实现直观、生动、美观的信息可视化布局。[方法] 在追溯力导向算法与信息可视化的渊源的基础上,以电荷理论为突破口,借助群组和非一致节点的概念,提出这一算法。该算法利用分层布局思想,各布局单元独立布局,且采用相似但有区别的布局策略。[结果] 利用此算法实现一款面向网络知识组织系统(NKOS)的可视化原型系统,可广泛应用于NKOS(尤其是中文NKOS)中概念实例的可视化展示。[局限] 所提出的算法收敛条件效果还不够显著,以至于在布局过程中存在冗余节点抖动现象,今后可引入温度等神经计算的相关概念加以解决。[结论] 发现一种将图结构结合语义信息转换为树结构,并结合群组概念,利用力导向算法解决其布局问题的方法。该算法可以很好地解决中文叙词表本体等NKOS 的概念实例可视化问题,对画图社区解决其他类似问题也具有参考作用。

E-mail Alert
关键词 信息可视化力导向算法非一致节点群组布局中文叙词表本体网络知识组织系统    

[Objective] This paper presents a non-uniform node clustered graph layout algorithm in order to realize intuitive, lively and beautiful information visualization. [Methods] After insight into the relationship between forcedirected algorithm and information visualization, the paper puts forward this algorithm based on force-directed model with the help of cluster and non-uniform node concepts, using charge theory as a breakthrough. The algorithm employs the hierarchical layout ideas, and every layout unit is produced independently by similar but different layout strategies. [Results] A visualization prototype system for the NKOS is implemented with it, and can be widely applied to visualizing the instances of concept class in the NKOS (especially the Chinese NKOS). [Limitations] The result of the proposed algorithm convergence conditions is not significant, so that in the process of layout, there is redundant node vibrating. Temperature and other related concepts of neural computation can be introduced to solve it in the future. [Conclusions] The paper finds a way to transfer a graph structure with semantic information into a tree structure, and based on the cluster concept, using the force directed algorithms to solve its layout problems. This algorithm can deal with the visualization for instances of concepts in Chinese NKOS, such as OntoThesaurus, and the drawing community can solve other similar problems by using it as a reference.

Key wordsInformation visualization    Force-directed algorithm    Non-uniform node    Cluster layout    OntoThesaurus    NKOS
收稿日期: 2014-04-10     
:  TP391.41  

本文系国家社会科学基金项目“中文知识组织系统形式化语义描述标准体系研究” (项目编号:12BTQ045)、广东省哲学社会科学“十一五”规划项目“中文知识组织系统形式化语义描述标准体系研究”(项目编号:GD10CTS02)和广东省自然科学基金团队项目“新型计算模式及其软件开发方法研究” (项目编号:10351806001000000)的研究成果之一。

通讯作者: 曾新红     E-mail:
作者简介: 作者贡献声明:曾新红:确定系统需求,提出研究思路,系统测试,论文修订和最终定稿;蔡庆河:研究方案的具体设计,系统实现,论文撰写;黄华军:系统整合和系统测试;林伟明:系统整合。
曾新红, 蔡庆河, 黄华军, 林伟明. 基于力导向模型的非一致节点群组布局可视化算法研究[J]. 现代图书情报技术, 2014, 30(9): 33-43.
Zeng Xinhong, Cai Qinghe, Huang Huajun, Lin Weiming. Research on Non-uniform Node Clustered Graph Layout Algorithm for Visualization Based on Force Directed Model. New Technology of Library and Information Service, DOI:10.11925/infotech.1003-3513.2014.09.05.

[1] Gruber T. A Translation Approach to Portable Ontology Specifications [J]. Knowledge Acquisition, 1993, 5(2): 199-220.
[2] 曾新红. 中文叙词表本体——叙词表与本体的融合[J]. 现代图书情报技术, 2009(1): 34-43. (Zeng Xinhong. Onto-Thesaurus (Chinese-Thesaurus-Ontology) ——An Integration of Thesaurus and Ontology [J]. New Technology of Library and Information Service, 2009(1): 34-43.)
[3] W3C. OWL 2 Web Ontology Language Document Overview [EB/OL]. [2013-03-19]. owl2-overview-20091027/.
[4] 曾新红, 明仲, 蒋颖, 等. 中文叙词表本体共建共享系统研究[J]. 情报学报, 2008, 27(3): 386-394. (Zeng Xinhong, Ming Zhong, Jiang Ying, et al. Research on OntoThesaurus Co-construction and Sharing System (OTCSS) [J]. Journal of the China Society for Scientific and Technical Information, 2008, 27(3): 386-394.)
[5] 曾新红, 蔡庆河, 曾汉龙, 等.中文叙词表本体可视化群组布局算法研究与实现[J].现代图书情报技术, 2012(10): 8-15. (Zeng Xinhong, Cai Qinghe, Zeng Hanlong, et al. The Research and Implementation of Clustered Graphs Layout Algorithm for OntoThesaurus Visualization [J]. New Technology of Library and Information Service, 2012(10): 8-15.)
[6] 袁晓如, 张昕, 肖何, 等.可视化研究前沿及展望[J].科研信息化技术与应用, 2011,2(4): 3-13. (Yuan Xiaoru, Zhang Xin, Xiao He, et al. Visualization Research Frontier and Prospects [J]. E-Science Technology & Application, 2011, 2(4): 3-13.)
[7] Tollis I G. Graph Drawing and Information Visualization [J]. ACM Computing Surveys, 1996, 28(4es): Article No. 19.
[8] Battista G D, Eades P, Tamassia R, et al. Algorithms for Drawing Graphs: An Annotated Bibliography [J]. Computa-tional Geometry: Theory and Applications, 1994, 4(5): 235-282.
[9] Purchase H C. Metrics for Graph Drawing Aesthetics [J]. Journal of Visual Languages and Computing, 2002, 13(5): 501-516.
[10] Noack A. Energy Models for Graph Clustering [J]. Journal of Graph Algorithms and Applications, 2007, 11(2): 453-480.
[11] Frishman Y, Tal A. Dynamic Drawing of Clustered Graphs [C]. In: Proceedings of the IEEE Symposium on Information Visualization, Austin, TX, US. IEEE Computer Society, 2004: 191-198.
[12] Herman I, Melançon G, Marshall M S. Graph Visualization and Navigation in Information Visualization: A Survey [J]. IEEE Transactions on Visualization and Computer Graphics, 2000, 6(1): 24-43.
[13] Tutte W T. How to Draw a Graph [J]. Proceedings of the London Mathematical Society, 1963, 13(3): 743-767. DOI: 10.1112/ plms/s3-13.1.733.
[14] Eades P A. A Heuristic for Graph Drawing [J]. Congressus Numerantium, 1984, 42(11): 149-160.
[15] Kobourov S G. Spring Embedders and Force Directed Graph Drawing Algorithms [EB/OL]. [2013-03-19]. http://arxiv. org/pdf/1201.3011v1.
[16] Lin C C, Yen H C, Chuang J H. Drawing Graphs with Nonuniform Nodes Using Potential Fields [J]. Journal of Visual Languages and Computing, 2009, 20(6): 385-402.
[17] Harel D, Koren Y. Drawing Graphs with Non-Uniform Vertices[C]. In: Proceedings of the Working Conference on Advanced Visual Interfaces. New York: ACM Press, 2002: 157-166.
[18] Kumar G, Garland M. Visual Exploration of Complex Time- Varying Graphs [J]. IEEE Transactions on Visualization and Computer Graphics, 2006, 12(5): 805-812.
[19] Frishman Y, Tal A. Online Dynamic Graph Drawing [J]. IEEE Transactions on Visualization and Computer Graphics, 2008, 14(4): 727-740.
[20] Hachul S, Jünger M. Drawing Large Graphs with a Potential Field-Based Multilevel Algorithm [C]. In: Proceedings of the 12th International Conference on Graph Drawing. Berlin: Springer-Verlag, 2004:285-295.
[21] Duncan C A, Eppstein D, Goodrich M T, et al. Lombardi Drawings of Graphs [C]. In: Proceedings of the 18th International Symposium on Graph Drawing. Berlin: Springer-Verlag, 2011: 195-207.
[22] Chernobelskiy R, Cunningham K I, Goodrich M T, et al. Force-Directed Lombardi-Style Graph Drawing [C]. In: Proceedings of the 19th International Symposium on Graph Drawing. Berlin: Springer-Verlag, 2012: 320-331.
[23] Kobourov S G, Wampler K. Non-Euclidean Spring Embedders [J]. IEEE Transactions on Visualization and Computer Graphics, 2005, 11(6): 757-767.
[24] 曾汉龙. 中文叙词表本体可视化群组布局算法研究与实现[D]. 深圳: 深圳大学, 2010. (Zeng Hanlong. The Research and Implementation of Clustered Graphs Layout Algorithm for OTCSS Visualization [D]. Shenzhen: Shenzhen University, 2010).
[25] 唐铖.基于图像语义搜索的中文叙词表本体可视化研究[D].深圳: 深圳大学, 2012. (Tang Cheng. The Research of Visualization for OntoThesaurus Based on Image Semantic Search [D]. Shenzhen: Shenzhen University, 2012.)

[1] 谢秀芳,张晓林. 针对科技路线图的文本挖掘研究: 集成分析及可视化*[J]. 数据分析与知识发现, 2017, 1(1): 16-25.
[2] 夏立新, 蔡昕, 石义金, 孙丹霞, 王忠义. Web生活服务信息的组织与可视化研究[J]. 现代图书情报技术, 2014, 30(4): 85-91.
[3] 钱力, 张晓林, 李春旺, 王小梅, 杨立英, 陈挺, 张智雄. 利用OSGi的科技情报分析集成服务架构研究与应用[J]. 现代图书情报技术, 2014, 30(12): 62-70.
[4] 邱均平, 余厚强. 从VAST会议解读可视分析学新进展[J]. 现代图书情报技术, 2014, 30(10): 14-24.
[5] 黄华军, 曾新红, 林伟明. OTCSS关联数据服务的研究与实现[J]. 现代图书情报技术, 2012, 28(7): 40-47.
[6] 钱力, 张智雄, 邹益民, 黄永文. 信息可视化检索在数字图书馆中的应用实践[J]. 现代图书情报技术, 2012, 28(4): 74-78.
[7] 曾新红, 蔡庆河, 曾汉龙, 唐铖, 黄华军, 林伟明. 中文叙词表本体可视化群组布局算法研究与实现[J]. 现代图书情报技术, 2012, (10): 8-15.
[8] 田金凤, 曾新红, 黄华军, 林伟明. 中文叙词表本体概念定义注释的自动构建研究[J]. 现代图书情报技术, 2011, (11): 9-16.
[9] 乔建忠. 基于业务关联的政务信息资源分类系统的研究与实现[J]. 现代图书情报技术, 2010, 26(9): 28-36.
[10] 周宁 何坚. 可视化原型系统的实现*[J]. 现代图书情报技术, 2010, 26(7/8): 3-8.
[11] 吴佳鑫 王健海. 基于态势感知理论的可视化感知模型[J]. 现代图书情报技术, 2010, 26(7/8): 9-14.
[12] 曾新红 黄华军 林伟明. 超大型中文叙词表本体的检索与推理研究[J]. 现代图书情报技术, 2010, 26(7/8): 58-65.
[13] 刘玮,周宁,马莹珺. 信息可视化在音频管理领域的应用*——语音信息可视化研究[J]. 现代图书情报技术, 2008, 24(7): 33-37.
[14] 杨峰 . ICV:信息交流的可视化模型*[J]. 现代图书情报技术, 2008, 24(5): 50-55.
[15] 曾新红,林伟明,明仲. 中文叙词表本体一致性检测机制研究与实现*[J]. 现代图书情报技术, 2008, 24(5): 1-9.
Full text



版权所有 © 2015 《数据分析与知识发现》编辑部
地址:北京市海淀区中关村北四环西路33号 邮编:100190