计算机应用 ›› 2016, Vol. 36 ›› Issue (5): 1347-1351.DOI: 10.11772/j.issn.1001-9081.2016.05.1347

• 虚拟现实与数字媒体 • 上一篇    下一篇

MSNV:基于多层次社团划分的网络结构可视化方法

王贤刚1, 姚中华2, 宋汉辰1   

  1. 1. 国防科学技术大学 信息系统工程重点实验室, 长沙 410073;
    2. 装备学院 复杂电子系统仿真实验室, 北京 101416
  • 收稿日期:2015-10-27 修回日期:2015-12-23 出版日期:2016-05-10 发布日期:2016-05-09
  • 通讯作者: 王贤刚
  • 作者简介:王贤刚(1990-),男,云南保山人,硕士研究生,CCF会员,主要研究方向:数据可视化;姚中华(1989-),男,安徽阜阳人,博士研究生,CCF会员,主要研究方向:网络可视化、多媒体、虚拟现实;宋汉辰(1977-),男,河南唐河人,副教授,博士,CCF会员,主要研究方向:数据可视化。

MSNV:network structure visualization method based on multi-level community detection

WANG Xiangang1, YAO Zhonghua2, SONG Hanchen1   

  1. 1. Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha Hunan 410073, China;
    2. Science and Technology on Complex Electronic System Simulation Laboratory, Equipment Academy, Beijing 101416, China
  • Received:2015-10-27 Revised:2015-12-23 Online:2016-05-10 Published:2016-05-09

摘要: 针对大规模网络节点数目庞大、结构复杂性高,有限的屏幕空间难以展示其结构特征的问题,提出了一种基于社团划分的多层次网络可视化方法。首先,使用基于网络模块度的社团划分算法对网络节点进行划分,并采用贪婪算法寻找最大模块度的社团划分,得到不同层次粒度的社团;其次,通过设置层次约束力以改进经典力导引算法(FDA),使改进的算法能对不同层次粒度的社团实现分层布局,解决FDA无法展示网络节点层次性的问题;最后,使用多窗口视图、Overview+Detail等交互方法分别展示高层社团和底层节点,实现兼顾网络高层次宏观结构和低层次局部细节的显示。仿真实验中,该算法的社团划分相较于自包含GN算法在效率和准确率上有所提高。案例分析表明,所提方法在大规模网络结构的显示和交互方面具有良好的效果和性能。

关键词: 大规模网络, 多层次, 可视化, 社团划分, 力导引算法

Abstract: Focused on the issue that large-scale network has characteristics of huge number of nodes, high structural complexity and difficulty to demonstrate its structural characteristics by the limited screen space, a multi-level network visualization method based on community detection was proposed. Firstly, a community detection algorithm based on network modularity was used to detect the network node and a greedy algorithm was used to find the community detection with maximum modularity to get different level of granularity communities. Then, in order to solve the problem that the Force-Directed Algorithm (FDA) could not display network nodes hierarchically, the classic FDA was improved by setting the level blinding force to achieve hierarchical layout of different level of granularity communities. Finally, high level communities and low level nodes were displayed respectively by using the interactive method such as multi-window view and Overview+Detail, meeting the requirement of both network high-level macrostructure and low-level details of the display. In the simulation test, the community detection algorithm is faster and more accurate compared to self-contained GN (Girvan-Newman) algorithm. The theoretical analysis and simulation results show that the proposed method has good effect and performance in display and interaction of large-scale network structure.

Key words: large-scale network, multi-level, visualization, community detection, Force-Directed Algorithm (FDA)

中图分类号: