|
|
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 |
|
|
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.
|
Received: 10 April 2014
Published: 20 October 2014
|
|
[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.) |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|