网络图中边集束优化问题

姚中华; 吴玲达; 宋汉辰

doi:10.13700/j.bh.1001-5965.2014.0501

网络图中边集束优化问题

doi: 10.13700/j.bh.1001-5965.2014.0501

1.
装备学院复杂电子系统仿真实验室, 北京 101416
2. 国防科学技术大学信息系统工程重点实验室, 长沙 410073

基金项目: 国家自然科学基金(61103081)

详细信息

作者简介:
姚中华(1989—),男,安徽阜阳人,博士研究生,visworker07@163.com

通讯作者:
吴玲达(1962—),女,上海人,教授,wld@nudt.edu.cn,研究方向为多媒体信息系统与虚拟现实技术、系统集成、网络可视化、信息可视化.

中图分类号: TP391
计量
- 文章访问数: 971
- HTML全文浏览量: 39
- PDF下载量: 525
- 被引次数: 0
出版历程
- 收稿日期: 2014-04-08
- 修回日期: 2014-08-11
- 网络出版日期: 2015-05-20

Problems of network simplification by edge bundling

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

摘要

摘要: 网络规模增大和复杂度提高造成的节点遮挡覆盖和边交叉阻塞等问题成为网络可视化研究的热点.针对网络中出现的视觉凌乱问题,以空间位置和群组关系为出发点,从网络中独立的边和群组两个层次,以边汇合的角度研究边集束技术,将网络中临近的边集聚成束以降低视觉复杂度,提出和改进了分段力导引算法(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.
- network visualization /
- edge bundling /
- segmental force directed algorithm /
- cluster algorithm /
- bundling simplification algorithm

HTML全文

参考文献(25)

[1]	Eades P. A heuristic for graph drawing[J].Congressus Numerantium,1984,42(1):149-160.
[2]	Kamada T,Kawai S.An algorithm for drawing general undirected graphs[J].Information Processing Letters,1989,31(1):7-15.
[3]	Davidson R,Harel D.Drawing graphs nicely using simulated annealing[J].ACM Transactions on Graphics,1996,15(4):301-331.
[4]	Fruchterman T M J,Reingold E M.Graph drawing by force-directed placement[J].Software:Practice and Experience,1991,21(11):1129-1164.
[5]	Ellis G,Dix A.A taxonomy of clutter reduction for information visualization[J].IEEE Transactions on Visualization and Computer Graphics,2007,13(6):1216-1223.
[6]	Holten D. Hierarchical edge bundles:visualization of adjacency relations in hierarchical data[J].IEEE Transactions on Visualization and Computer Graphics,2006,12(5):805-812.
[7]	Chung P J,Deek J,Feinstein H E,et al.A structure-function study of map Tau:analyzing distinct map Tau domains in mediating microtubule assembly and bundling using synchrotron SAXS[J].Biophysical Journal,2012,102(3):700a.
[8]	Gansner E R,Koren Y.Improved circular layouts[C]//Graph Drawing,14th International Symposium,GD 2006.Berlin:Springer-Verlag,2006:386-398.
[9]	Gansner E R,Hu Y F,North S,et al.Multilevel agglomerative edge bundling for visualizing large graphs[C]//Proceedings of the 2011 IEEE Pacific Visualization Symposium.Piscataway,NJ:IEEE Press,2011:187-194.
[10]	Phan D,Xiao L,Yeh R,et al.Flow map layout[C]//Proceedings of IEEE Information Visualization Symposium.Piscataway,NJ:IEEE Press,2005:219-224.
[11]	Holten D,Van J J W. Force-directed edge bundling for graph visualization[J].Computer Graphics Forum,2009,28(3): 983-990.
[12]	Cui W,Zhou H,Qu H,et al.Geometry based edge clustering for graph visualization[J].IEEE Transactions on Visualization and Computer Graphics,2008,14(6):1277-1284.
[13]	Lambert A,Bourqui R,Auber D.Winding roads:routing edges into bundles[J].Computer Graphics Forum,2010,29(3):853-862.
[14]	Ozan E,Christophe H,Fernando P,et al.Graph edge bundling by medial axes[J].Visualization and Computer Graphics,2011,17(12):2364-2383.
[15]	Wong N,Carpendale S.Using edge plucking for interactive graph exploration[C]//IEEE Information Visualization Symposium,Poster Compendium.Piscataway,NJ:IEEE Press,2005:51-52.
[16]	Wong N,Carpendale S,Greenberg S.EdgeLens:an interactive method for managing edge congestion in graphs[C]//IEEE Information Visualization Symposiu.Piscataway,NJ:IEEE Press,2003:51-58.
[17]	Zhou H,Xu P P,Yuan X R,et al.Edge bundling in information visualization[J].Tsinghua Science and Technology,2013,18(2): 145-156.
[18]	李树彬,吴建军,高自友,等.基于复杂网络的交通拥堵与传播动力学分析[J].物理学报,2011,60(5):1-9. Li S B,Wu J J,Gao Z Y,et al.The analysis of traffic congestion and dynamic propagation properties based on complex network[J].Acta Physica Sinica,2011,60(5):1-9(in Chinese).
[19]	Bagler G. Analysis of the airport network of India as a complex weighted network[J].Elsevier,2008,387(12):2972-2980.
[20]	Li W,Cai X. Statistical analysis of airport network of China[J].Physical Review E,2004,69(2):1-6.
[21]	Guo D. Flow mapping and multivariate visualization of large spatial interaction data[J].IEEE,2009,15(6):1041-1048.
[22]	汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006:162-163. Wang X F,Li X,Chen G R.Complex network theory and application[M].Beijing:Tsinghua University Press,2006:162-163(in Chinese).
[23]	Clauset A,Newman M E J,Moore C.Finding community structure in very large networks[J].Physical Review E,2004,70(6): 66111.
[24]	Newman M E J. Fast algorithm for detecting community structure in networks[J].Physical Review E-Statistical,Nonlinear,and Soft Matter Physics,2004,69(6):066133-1-5.
[25]	Zhou H,Yuan X R,Cui W W,et al.Energy-based hierarchical edge clustering of graphs[C]//IEEE Pacific Visualisation Symposium 2008.Piscataway,NJ:IEEE Press,2008:55-62.