A Visual Layout Algorithm for Showing Overlapping Community Structure of Networks
ZHANG Mingna1, XIAO Jing1, XU Xiaoke1,2
1. College of Information and Communication Engineering, Dalian Minzu University, Dalian 116600, China; 2. a.Computational Communication Research Center, Zhuhai 519085, China; b.School of Journalism and Communication, Beijing Normal University, Beijing 100875, China
Abstract：Visualization technology can be used to effectively analyze the community structure, help users to understand the network topology, and dig out the hidden information from it, but the traditional network visualization layout algorithm does not consider the overlapping characteristics of nodes in the overlapping communities. Aiming at above problems, firstly, this paper uses the existing overlapping community detection algorithm to divide the community, and then hard partition and determine the node position according to the weighted summation of the membership matrix. Finally, the overlapping nodes are accurately laid out to display the overlapping community structure. The visual results demonstrate that the algorithm can visually display the overlapping community structure, highlight the overlapping nodes and the communities to which the nodes belong. At the same time, the experiment uses indicators such as node deviation, edge length deviation, and point distribution variance to verify that the algorithm can reduce node deviation and point distribution variance. This study can meet the visualization needs of overlapping community structures in complex networks, and can provide certain help for understanding the structure and functions of complex communities.
[1] EADES P. A heuristic for graph drawing[J]. Congressus Numerantium, 1984, 42:149-160. [2] KAMADA T, KAWAI S. An algorithm for drawing general undirected graphs[J]. Information Processing Letters, 1989, 31(1):7-15. [3] FRUCHTERMAN T M J, REINGOLD E M. Graph drawing by force-directed placement[J]. Software Practice & Experience, 2010, 21(11):1129-1164. [4] NEWMAN M E J, PEIXOTO T P. Generalized communities in networks[J]. Physical Review Letters, 2015, 115(8):088701. [5] 周锐,王桂娟,邓皓天,等. 复杂网络聚类特征层次布局算法[J]. 计算机应用研究, 2022, 39 (2):479-484. ZHOU R, WANG G J, DENG H T, et al. Complex network clustering feature multi-level layout algorithm[J]. Computer Application Research, 2022, 39 (2): 479-484. [6] 邓皓天. 大规模社会网络布局算法研究[D]. 绵阳:西南科技大学, 2021. DENG H T. Research on layout algorithms large-scale social networks[D]. Mianyang: Southwest University of Science and Technology, 2021. [7] DAVIDSON R. Drawing graphs nicely using simulated annealing[J]. Acm Trans Graphics, 1996, 15(4):301-331. [8] 朱志良,林森,崔坤,等. 基于复杂网络社区划分的网络拓扑结构可视化布局算法[J]. 计算机辅助设计与图形学学报, 2011, 23(11):1808-1815. ZHU Z L, LIN S, CUI K, et al. Network topology layout algorithm based on community detection of complex networks[J]. Journal of Computer-Aided Design & Computer Graphics, 2011, 23 (11): 1808-1815. [9] 吴渝,李藻旭,李红波,等. 展示复杂网络社团结构的社团引力导引的布局算法[J]. 计算机辅助设计与图形学学报, 2015, 27(8):1460-1467. WU Y, LI Z X, LI H B, et al. A community-cravity-directed algorithm for showing community structure of complex networks[J]. Journal of Computer-Aided Design & Computer Graphics, 2015, 27 (8): 1460-1467. [10] ZHONG S, LIN S, XU G, et al. The expansibility research of K-Means algorithm under the GPU[C]// Proceedings of the International Conference on Software Engineering and Service Science. Beijing: IEEE, 2017. [11] 周弦,黄廷磊,梁霄. 基于社团划分的网络聚类布局算法[J]. 计算机与现代化, 2017(12):1-5,11. ZHOU X, HUANG T L, LIANG X. Network clustering layout algorithm based on detecting community structure[J]. Computer and Modernization, 2017 (12): 1-5,11. [12] HUANG Z, WU J, ZHU W, et al. Visualizing complex networks by leveraging community structures[J]. Physica A: Statistical Mechanics and its Applications, 2021, 565(1):125506. [13] 肖婧,张永建,许小可. 复杂网络模糊重叠社区检测研究进展[J]. 复杂系统与复杂性科学, 2017, 14(3):8-29. XIAO J, ZHANG Y J, XU X K. Research progress of fuzzy overlapping community detection in complex networks[J]. Complex Systems and Complexity Science, 2017, 14 (3): 8-29. [14] KUNDU S, PAL S K. Fuzzy-rough community in social networks[J]. Pattern Recognition Letters, 2015, 67(P2):145-152. [15] VEHLOW C, REINHARDT T, WEISKOPF D. Visualizing fuzzy overlapping communities in networks[J]. IEEE Transactions on Visualization and Computer Graphics, 2013, 19(12):2486-2495. [16] PARK C H, CHANG J H. Robust TOA source localisation algorithm using prior location [J]. IET Radar, Sonar & Navigation, 2019, 13(3): 384-391. [17] 任淑霞,吴涛,张书博. 嵌入社区半径的力引导与径向树混合布局算法[J]. 四川大学学报(自然科学版), 2020, 57(1):73-81. REN S X, WU T, ZHANG S B. Community radius embedded in force-directed and radial tree hybrid layout algorithm[J]. Journal of Sichuan University (Natural Science Edition), 2020, 57 (1): 73-81. [18] 孙扬, 蒋远翔, 赵翔,等. 网络可视化研究综述[J]. 计算机科学, 2010, 37(2):12-18. SUN Y, JIANG Y X, ZHAO Xiang, et al. Survey on the research of network visualization [J]. Computer Science, 2010, 37(2): 12-18. [19] 李海峰. 图布局力导引算法的研究与实现[D]. 镇江:江苏大学, 2012. LI H F. Research and implementation of graph layout force-directed algorithm[D]. Zhenjiang: Jiangsu University, 2012.
