留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

网络图中边集束优化问题

姚中华 吴玲达 宋汉辰

姚中华, 吴玲达, 宋汉辰等 . 网络图中边集束优化问题[J]. 北京航空航天大学学报, 2015, 41(5): 871-878. doi: 10.13700/j.bh.1001-5965.2014.0501
引用本文: 姚中华, 吴玲达, 宋汉辰等 . 网络图中边集束优化问题[J]. 北京航空航天大学学报, 2015, 41(5): 871-878. doi: 10.13700/j.bh.1001-5965.2014.0501
YAO Zhonghua, WU Lingda, SONG Hanchenet al. Problems of network simplification by edge bundling[J]. Journal of Beijing University of Aeronautics and Astronautics, 2015, 41(5): 871-878. doi: 10.13700/j.bh.1001-5965.2014.0501(in Chinese)
Citation: YAO Zhonghua, WU Lingda, SONG Hanchenet al. Problems of network simplification by edge bundling[J]. Journal of Beijing University of Aeronautics and Astronautics, 2015, 41(5): 871-878. doi: 10.13700/j.bh.1001-5965.2014.0501(in Chinese)

网络图中边集束优化问题

doi: 10.13700/j.bh.1001-5965.2014.0501
基金项目: 国家自然科学基金(61103081)
详细信息
    作者简介:

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

    通讯作者:

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

  • 中图分类号: TP391

Problems of network simplification by edge bundling

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

     

  • [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.

  • 加载中
计量
  • 文章访问数:  889
  • HTML全文浏览量:  25
  • PDF下载量:  523
  • 被引次数: 0
出版历程
  • 收稿日期:  2014-04-08
  • 修回日期:  2014-08-11
  • 网络出版日期:  2015-05-20

目录

    /

    返回文章
    返回
    常见问答