| Citation: | WU Lingda, ZHANG Xitao, MENG Xiangliet al. Compression layout for network visualization based on node importance for community structure[J]. Journal of Beijing University of Aeronautics and Astronautics, 2019, 45(12): 2423-2430. doi: 10.13700/j.bh.1001-5965.2019.0385(in Chinese)
|
In order to effectively display the mesoscale structure of the network, the force-directed layout algorithm is combined with the network community structure features, and a network visualization compression layout method based on the importance of the node in the community structure is proposed. First, the Louvain algorithm is used to divide the network into multi-granular community structure. Then, the importance of the nodes is evaluated by calculating the topological potential of the nodes in the community structure. Through preserving the important nodes, the community is compressed, while the boundary nodes are merged. Finally, the force-directed layout algorithm is adopted to layout the network to achieve a visual compression layout. The experimental results show that the proposed method can completely preserve the original network community structure on the basis of compression nodes and connected edges, and can clearly display the internal structure of the community by retaining the representative points of the community structure, highlighting the position and role of the community and important nodes in the network structure.
| [1] |
张喜涛, 吴玲达, 于少波.面向多层网络可视化的多力导引节点自动布局算法[J].计算机辅助设计与图形学学报, 2019, 31(4):639-646. http://d.old.wanfangdata.com.cn/Periodical/jsjfzsjytxxxb201904015
ZHANG X T, WU L D, YU S B.A multi-force directed layout algorithm for multilayer networks visualization[J].Journal of Computer-Aided Design & Computer Graphics, 2019, 31(4):639-646(in Chinese). http://d.old.wanfangdata.com.cn/Periodical/jsjfzsjytxxxb201904015
|
| [2] |
姚中华, 吴玲达, 宋汉辰.网络图中边集束优化问题[J].北京航空航天大学学报, 2015, 41(5):871-878. https://bhxb.buaa.edu.cn/CN/abstract/abstract13248.shtml
YAO Z H, WU L D, SONG H C.Problems of network simplification by edge bundling[J].Journal of Beijing University of Aeronautics and Astronautics, 2015, 41(5):871-878(in Chinese). https://bhxb.buaa.edu.cn/CN/abstract/abstract13248.shtml
|
| [3] |
LESKOVEC J, FALOUTSOS C.Sampling from large graphs[C]//Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York: ACM, 2006: 631-636.
|
| [4] |
杜晓林.大规模社会网络可视化若干问题及算法研究[D].哈尔滨: 哈尔滨工业大学, 2015: 18-35. http://cdmd.cnki.com.cn/Article/CDMD-10213-1015957412.htm
DU X L.Research on visualization problems and algorithms for large scale social network[D].Harbin: Harbin Institute of Technology, 2015: 18-35(in Chinese). http://cdmd.cnki.com.cn/Article/CDMD-10213-1015957412.htm
|
| [5] |
GILBERT A C, LEVCHENKO K.Compressing network graphs[C]//Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York: ACM, 2004: 1-10.
|
| [6] |
ALMENDRAL J A, CRIADO R, LEYVA I, et al.Introduction to focus issue:Mesoscales in complex networks[J]. Chaos, 2011, 21(1):016101. doi: 10.1063/1.3570920
|
| [7] |
EADES P.A heuristic for graph drawing[J].Congressus Numerantium, 1984, 42:149-160. http://d.old.wanfangdata.com.cn/OAPaper/oai_arXiv.org_cs%2f0212046
|
| [8] |
KAMADA T, KAWAI S.An algorithm for drawing general undirected graphs[J].Information Processing Letters, 1989, 31(1):7-15. doi: 10.1016-0020-0190(89)90102-6/
|
| [9] |
DAVIDSON R, HAREL D.Drawing graphs nicely using simulated annealing[J].ACM Transactions on Graphics, 1996, 15(4):301-331. doi: 10.1145/234535.234538
|
| [10] |
FRUCHTERMAN T M J, REINGOLD E M.Graph drawing by force-directed placement[J].Software-Practice and Experience, 1991, 21(11):1129-1164. doi: 10.1002/spe.4380211102
|
| [11] |
水超, 陈洪辉, 陈涛, 等.力导向模型的复杂网络社区挖掘算法[J].国防科技大学学报, 2014, 36(4):163-168. http://d.old.wanfangdata.com.cn/Periodical/gfkjdxxb201404028
SHUI C, CHEN H H, CHEN T, et al.A community detect algorithm on force-directed model[J].Journal of National University of Defense Technology, 2014, 36(4):163-168(in Chinese). http://d.old.wanfangdata.com.cn/Periodical/gfkjdxxb201404028
|
| [12] |
ZHANG X T, WU L D, YU S B.Layer-edge patterns exploration and presentation in multiplex networks:From detail to overview via selections and aggregations[J].Electronics, 2019, 8(4):387. doi: 10.3390/electronics8040387
|
| [13] |
王晓华, 杨新艳, 焦李成.基于多尺度几何分析的复杂网络压缩策略[J].电子与信息学报, 2009, 31(4):968-972. http://d.old.wanfangdata.com.cn/Periodical/dzkxxk200904048
WANG X H, YANG X Y, JIAO L C.Compression of complex networks based on multiscale geometric analysis[J].Journal of Electronics & Information Technology, 2009, 31(4):968-972(in Chinese). http://d.old.wanfangdata.com.cn/Periodical/dzkxxk200904048
|
| [14] |
李甜甜, 卢罡, 许南山, 等.基于k-core的大规模复杂网络压缩布局算法[J].计算机工程, 2016, 42(5):308-312. doi: 10.3969/j.issn.1000-3428.2016.05.054
LI T T, LU G, XU N S, et al.Compressing layout algorithm for large complex network based on k-core[J].Computer Engineering, 2016, 42(5):308-312(in Chinese). doi: 10.3969/j.issn.1000-3428.2016.05.054
|
| [15] |
肖俐平, 孟晖, 李德毅.基于拓扑势的网络节点重要性排序及评价方法[J].武汉大学学报(信息科学版), 2008, 33(4):379-383. http://d.old.wanfangdata.com.cn/Periodical/whchkjdxxb200804011
XIAO L P, MENG H, LI D Y.Approach to node ranking in a netwrok based on topology potential[J].Geomatics and Information Science of Wunan University, 2008, 33(4):379-383(in Chinese). http://d.old.wanfangdata.com.cn/Periodical/whchkjdxxb200804011
|
| [16] |
王戬.一种基于拓扑势的社会网络节点重要性评估方法[D].哈尔滨: 哈尔滨工程大学, 2015: 18-30. http://cdmd.cnki.com.cn/Article/CDMD-10217-1018047823.htm
WANG J.Evaluating the importance of nodes in social networks based on topology potential[D].Harbin: Harbin Engineering University, 2015: 18-30(in Chinese). http://cdmd.cnki.com.cn/Article/CDMD-10217-1018047823.htm
|
| [17] |
GACH O, HAO J K.Improving the Louvain algorithm for community detection with modularity maximization[C]//International Conference on Artificial Evolution (Evolution Artificielle).Berlin: Springer, 2013: 145-156.
|
Figures(5) / Tables(1)
Copyright © Journal of Beijing University of Aeronautics and Astronautics
Address: Editorial Department of Journal of Beijing University of Aeronautics and Astronautics, 37 Xueyuan Road, Haidian District, Beijing Post Code: 100191 Email: jbuaa@buaa.edu.cn
Supported by:
Beijing Renhe Information Technology Co., Ltd.
DownLoad:
