Please wait a minute...
New Technology of Library and Information Service  2014, Vol. 30 Issue (9): 33-43    DOI: 10.11925/infotech.1003-3513.2014.09.05
Current Issue | Archive | Adv Search |
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
Download: PDF(2268 KB)   HTML  
Export: BibTeX | EndNote (RIS)      
Abstract  

[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     
Received: 10 April 2014      Published: 20 October 2014
:  TP391.41  
  G254.29  

Cite this article:

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, 2014, 30(9): 33-43.

URL:

http://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/10.11925/infotech.1003-3513.2014.09.05     OR     http://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/Y2014/V30/I9/33

[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]. http://www.w3.org/TR/2009/REC- 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] Xiufang Xie,Xiaolin Zhang. Integrated Analysis and Visualization of Sci-Tech Roadmaps: Case Study of Renewable Energy[J]. 数据分析与知识发现, 2017, 1(1): 16-25.
[2] Yang Ruyi, Liu Dongsu. A Research on Visualization Algorithm of Hierarchy Information Based on Folksonomy[J]. 现代图书情报技术, 2014, 30(7): 71-76.
[3] Xia Lixin, Cai Xin, Shi Yijin, Sun Danxia, Wang Zhongyi. Organization and Visualization of Web Life Service Information Research[J]. 现代图书情报技术, 2014, 30(4): 85-91.
[4] Qian Li, Zhang Xiaolin, Li Chunwang, Wang Xiaomei, Yang Liying, Chen Ting, Zhang Zhixiong. Research and Application of Science Intelligence Analysis Integrated Services Architecture Using OSGi[J]. 现代图书情报技术, 2014, 30(12): 62-70.
[5] Qiu Junping, Yu Houqiang. The Research Development of Visual Analytics from the Perspective of VAST Conference[J]. 现代图书情报技术, 2014, 30(10): 14-24.
[6] Zhang Yunliang, Zhang Zhaofeng, Zhang Xiaodan, Xu Deshan. Web Dynamic Interactive Visualization of Knowledge Organization Systems with D3.js[J]. 现代图书情报技术, 2013, 29(7/8): 127-131.
[7] Qian Li, Zhang Zhixiong, Zou Yimin, Huang Yongwen. Application of Information Visualization Retrieval in Digital Library[J]. 现代图书情报技术, 2012, 28(4): 74-78.
[8] Zeng Xinhong, Cai Qinghe, Zeng Hanlong, Tang Cheng, Huang Huajun, Lin Weiming. The Research and Implementation of Clustered Graphs Layout Algorithm for OntoThesaurus Visualization[J]. 现代图书情报技术, 2012, (10): 8-15.
[9] Tian Jinfeng, Zeng Xinhong, Huang Huajun, Lin Weiming. Research on Automatic Construction of Definition Notes for Concepts in OntoThesaurus[J]. 现代图书情报技术, 2011, (11): 9-16.
[10] Zhou Ning He Jian. Realization on InfoVisModel Visualization Prototype System[J]. 现代图书情报技术, 2010, 26(7/8): 3-8.
[11] Wu Jiaxin Wang Jianhai. A Visualization Awareness Model Based on Situation Awareness Theory[J]. 现代图书情报技术, 2010, 26(7/8): 9-14.
[12] Zeng Xinhong Huang Huajun Lin Weiming. Research on Retrieval and Reasoning of Ultra-Large-Scale OntoThesaurus[J]. 现代图书情报技术, 2010, 26(7/8): 58-65.
[13] Liu Wei,Zhou Ning,Ma Yingjun . Application of Information Visualization in Audio Documents Management——Study on Spoken Documents Visualization[J]. 现代图书情报技术, 2008, 24(7): 33-37.
[14] Yang Feng. ICV: A Visual Model of Information Communication[J]. 现代图书情报技术, 2008, 24(5): 50-55.
[15] Zeng Xinhong,Lin Weiming,Ming Zhong . Research and Implementation of Consistency Checking Mechanism for OntoThesaurus[J]. 现代图书情报技术, 2008, 24(5): 1-9.
  Copyright © 2016 Data Analysis and Knowledge Discovery   Tel/Fax:(010)82626611-6626,82624938   E-mail:jishu@mail.las.ac.cn