北京航空航天大学学报 ›› 2015, Vol. 41 ›› Issue (5): 871-878.doi: 10.13700/j.bh.1001-5965.2014.0501

• 论文 • 上一篇    下一篇

网络图中边集束优化问题

姚中华1, 吴玲达1,2, 宋汉辰2   

  1. 1. 装备学院 复杂电子系统仿真实验室, 北京 101416;
    2. 国防科学技术大学 信息系统工程重点实验室, 长沙 410073
  • 收稿日期:2014-04-08 修回日期:2014-08-11 出版日期:2015-05-20 发布日期:2015-06-02
  • 通讯作者: 吴玲达(1962—),女,上海人,教授,wld@nudt.edu.cn,研究方向为多媒体信息系统与虚拟现实技术、系统集成、网络可视化、信息可视化. E-mail:wld@nudt.edu.cn
  • 作者简介:姚中华(1989—),男,安徽阜阳人,博士研究生,visworker07@163.com
  • 基金资助:

    国家自然科学基金(61103081)

Problems of network simplification by edge bundling

YAO Zhonghua1, WU Lingda1,2, SONG Hanchen2   

  1. 1. Science and Technology on Complex Electronic System Simulation Laboratory, Equipment Academy, Beijing 101416, China;
    2. Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha 410073, China
  • Received:2014-04-08 Revised:2014-08-11 Online:2015-05-20 Published:2015-06-02

摘要:

网络规模增大和复杂度提高造成的节点遮挡覆盖和边交叉阻塞等问题成为网络可视化研究的热点.针对网络中出现的视觉凌乱问题,以空间位置和群组关系为出发点,从网络中独立的边和群组两个层次,以边汇合的角度研究边集束技术,将网络中临近的边集聚成束以降低视觉复杂度,提出和改进了分段力导引算法(FDA)简化模型和群组边相容的网络图边集束模型.其中分段集束模型,提出以二次样条曲线表示网络边,通过样条控制点进行迭代汇聚的方法,实现了网络中边的集束;针对分段集束模型中部分连线过度弯曲问题,提出通过CNM聚类算法将网络进行群组划分,在群组结构的基础上对组内连线应用边相容原则,根据连线的匹配系数计算其集束程度的方法,网络图集束后曲线扭曲变形减少,曲线过渡更加平滑.选取国内航空网络作为案例,通过两种边集束模型进行网络图简化,分析结果表明,国内机场的群组结构具有地理属性的相近性,航空网络在整体上呈现出明显的十字脉络,东西走向和南北走向的航线分别汇聚集结成束,表现了航空网络建设在南北和东西方向的总体趋势.本集束简化算法适用性广,绘制的网络图具有良好的视觉效果和可读性.

关键词: 网络可视化, 边集束, 分段力导引算法, 聚类算法, 集束简化算法

Abstract:

Node occlusion and edge congestion problems, which are caused by the increment of network scale and complexity, had become a hot spot in network visualization research. To solve the visual clutter problem in network, edges close to each other in network were bundled by curving them. The bundling started from node position and group division, laying emphasis on edge bundling technique through edge convergence, edges bundled close to each other in network to reduce visual complexity. A segmental forced directed algorithm (FDA) simplification model and a group based consistent edge bundling network model were proposed and improved. In segmental FDA bundling model, quadratic spline was used to display line in network, control points of spline were produced by iteration to implement edge bundling. To solve the problem of excessive bending of some edges in segmental FDA bundling model, network was divided into different groups by CNM cluster algorithm. Lines in the same group were applied with edge consistent principle on basement of network group structure, and bundling level was calculated by the matching coefficient of edges. After edge bundling, the phenomena of curve's distortion decreased and curves became smoother. Domestic airline network data was chosen as experimental subject, and the network was simplified by two bundling models, and then the simplification result was analyzed. Experimental result shows that positions of nodes in the same group stand close to each other, and airline network shows distinct crossing skeleton. Airlines have north-south and west-east orientation bundle independently, which reveals the whole trends of airline network construction in these two directions. The bundling simplification algorithm introduced mentioned above has a wide applicability, and network visualized by this algorithm has good visual effect and readability.

Key words: network visualization, edge bundling, segmental force directed algorithm, cluster algorithm, bundling simplification algorithm

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发