﻿ 基于社团结构节点重要性的网络可视化压缩布局<sup>*</sup>
 文章快速检索 高级检索

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

Compression layout for network visualization based on node importance for community structure
WU Lingda1, ZHANG Xitao1,2, MENG Xiangli1
1. School of Space Information, Space Engineering University, Beijing 101416, China;
2. Department of Space Command, Space Engineering University, Beijing 101416, China
Received: 2019-07-09; Accepted: 2019-08-12; Published online: 2019-08-20 14:01
Foundation item: Fund for Weapons and Equipment Pro-Research (6142010010301)
Corresponding author. ZHANG Xitao, E-mail: zxthl0707@163.com
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.
Keywords: network visualization     compression layout     force-directed layout     topological potential     node importance

1 相关工作

2 网络可视化压缩布局方法 2.1 多粒度社团结构探测

 图 1 Louvain算法示意图 Fig. 1 Schematic diagram of Louvain algorithm
2.2 基于拓扑势的社团结构节点重要性评估

 (1)

 图 2 社团节点分类与社团压缩示意图 Fig. 2 Schematic diagram of community node classification and community compression
2.3 压缩布局算法

 (2)

1   创建广度优先访问列表L(vi), L(vi).PUSH(VN(vi))

2   WHILE L(vi).size>0 DO

3     vj=L(vi).POP()

4     IF (vjV′CA)

5       replace(vi)=vj

6       IfReplaced(vi)=1

7       BREAK WHILE

8     END IF

9     ELSE

10       L(vi).PUSH(VN(vj))

11     END ELSE

12   END WHILE

VCC中的所有节点设置替代节点，生成新的社团结构代表节点集合V′C。如算法1所示，VCC中的任一节点vi，其替代节点的设置可分为2步：

1) 如果节点vi的邻居节点vj属于社团结构代表点集合V′CA，则把节点vj设置为节点vi的替代节点。

2) 如果节点vj不是社团结构代表节点，则将节点vj的所有邻居节点添加到访问列表中，遍历查找直到找到节点vi的替代节点。

3 实验结果与分析

 数据集 方法 节点数 连边数 平均聚类系数 社团数 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

 图 3 dolphin网络压缩前后布局效果 Fig. 3 Layout effect of dolphin network before and after compression
 图 4 football网络压缩前后布局效果 Fig. 4 Layout effect of football network before and after compression
 图 5 采用本文方法对karat网络进行多粒度压缩前后布局效果 Fig. 5 Layout effect of karat network before and after multi-granularity compression by proposed method

1) 基于社团结构进行压缩，能够保留网络的社团构成，突出中观尺度结构特征。

2) 采用多粒度社团结构划分算法，展示社团基本结构，并实现网络的多粒度压缩布局。

4 结论

1) 有效压缩节点和连边数量，降低视觉杂乱现象。

2) 比较完整地从中观尺度反映网络的结构构成与交互，便于分析不同社团或节点在网络拓扑中的不同作用。

3) 基于多粒度的社团结构探测和不同的节点压缩比可以实现多粒度的压缩展示。本文方法主要通过将网络压缩方法和力导引布局算法结合，从社团构成和社团结构上展示了网络的中观尺度结构，下一步将考虑与其他节点布局算法和交互方法结合，进一步优化布局结果。

 [1] 张喜涛, 吴玲达, 于少波. 面向多层网络可视化的多力导引节点自动布局算法[J]. 计算机辅助设计与图形学学报, 2019, 31(4): 639-646. 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) [2] 姚中华, 吴玲达, 宋汉辰. 网络图中边集束优化问题[J]. 北京航空航天大学学报, 2015, 41(5): 871-878. 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) [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. 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. [8] KAMADA T, KAWAI S. An algorithm for drawing general undirected graphs[J]. Information Processing Letters, 1989, 31(1): 7-15. [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. 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) [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. 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) [14] 李甜甜, 卢罡, 许南山, 等. 基于k-core的大规模复杂网络压缩布局算法[J]. 计算机工程, 2016, 42(5): 308-312. 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. DOI:10.3969/j.issn.1000-3428.2016.05.054 (in Chinese) [15] 肖俐平, 孟晖, 李德毅. 基于拓扑势的网络节点重要性排序及评价方法[J]. 武汉大学学报(信息科学版), 2008, 33(4): 379-383. 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) [16] 王戬.一种基于拓扑势的社会网络节点重要性评估方法[D].哈尔滨: 哈尔滨工程大学, 2015: 18-30. 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.

#### 文章信息

WU Lingda, ZHANG Xitao, MENG Xiangli

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

Journal of Beijing University of Aeronautics and Astronsutics, 2019, 45(12): 2423-2430
http://dx.doi.org/10.13700/j.bh.1001-5965.2019.0385