基于社团结构节点重要性的网络可视化压缩布局

吴玲达; 张喜涛; 孟祥利

doi:10.13700/j.bh.1001-5965.2019.0385

基于社团结构节点重要性的网络可视化压缩布局

doi: 10.13700/j.bh.1001-5965.2019.0385

吴玲达¹,
张喜涛^{1, 2, ,},
孟祥利¹

1.
航天工程大学航天信息学院, 北京 101416
2.
航天工程大学航天指挥系, 北京 101416

基金项目:

武器装备预研基金 6142010010301

详细信息

作者简介:
吴玲达  女, 研究员, 博士生导师。主要研究方向:虚拟战场环境构建、信息系统建模与仿真、多媒体与虚拟现实技术

张喜涛  男, 博士, 讲师。主要研究方向:网络可视化

孟祥利  男, 博士研究生。主要研究方向:信息系统建模与仿真

通讯作者:
张喜涛, E-mail: zxthl0707@163.com

中图分类号: TP391.9
计量
- 文章访问数: 736
- HTML全文浏览量: 61
- PDF下载量: 309
- 被引次数: 0
出版历程
- 收稿日期: 2019-07-09
- 录用日期: 2019-08-12
- 网络出版日期: 2019-12-20

Compression layout for network visualization based on node importance for community structure

1.
School of Space Information, Space Engineering University, Beijing 101416, China
2.
Department of Space Command, Space Engineering University, Beijing 101416, China

Funds:

Fund for Weapons and Equipment Pro-Research 6142010010301

More Information

Corresponding author: ZHANG Xitao, E-mail: zxthl0707@163.com

摘要

摘要:
为有效展示网络的中观尺度结构，将力导引布局算法与网络社团结构特征相结合，提出了一种基于社团结构节点重要性的网络可视化压缩布局方法。首先，采用Louvain算法对网络进行多粒度社团结构划分；然后，通过计算社团结构中节点的拓扑势评估节点的重要性，保留社团结构中的重要节点，合并边缘节点，实现社团结构压缩；最后，采用力导引布局算法布局压缩网络节点，实现网络可视化的压缩布局。实验结果表明：所提方法在压缩节点和连边规模的基础上，能够完整保留原始网络的社团构成，并且通过保留社团结构代表点可以清晰展示社团内部结构，突出社团和重要节点在网络结构中的位置和作用。
- 网络可视化 /
- 压缩布局 /
- 力导引布局 /
- 拓扑势 /
- 节点重要性
Abstract:
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.
- network visualization /
- compression layout /
- force-directed layout /
- topological potential /
- node importance

HTML全文

图 1 Louvain算法示意图

Figure 1. Schematic diagram of Louvain algorithm

下载: 全尺寸图片幻灯片

图 2 社团节点分类与社团压缩示意图

Figure 2. Schematic diagram of community node classification and community compression

下载: 全尺寸图片幻灯片

图 3 dolphin网络压缩前后布局效果

Figure 3. Layout effect of dolphin network before and after compression

下载: 全尺寸图片幻灯片

图 4 football网络压缩前后布局效果

Figure 4. Layout effect of football network before and after compression

下载: 全尺寸图片幻灯片

图 5 采用本文方法对karat网络进行多粒度压缩前后布局效果

Figure 5. Layout effect of karat network before and after multi-granularity compression by proposed method

下载: 全尺寸图片幻灯片

表 1 压缩结果对比

Table 1. Comparison of compression results

数据集	方法	节点数	连边数	平均聚类系数	社团数
dolphin	压缩前	62	159	0.303	5
	方法1	12	29	0.716	3
	方法2	12	29	0.716	3
	本文方法	13	33	0.674	5
football	压缩前	115	613	0.403	10
	方法1	23	100	0.515	9
	方法2	23	96	0.570	8
	本文方法	26	97	0.534	10
karat	压缩前	34	78	0.588	4
	方法1	7	17	0.867	3
	方法2	7	17	0.867	3
	本文方法	8	18	0.733	4

下载: 导出CSV

参考文献(17)

[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.