基于同源控制点的边缘绑定方法

doi:10.11896/jsjkx.220300066

计算机科学 ›› 2022, Vol. 49 ›› Issue (10): 96-102.doi: 10.11896/jsjkx.220300066

• 数据库＆大数据＆数据科学 • 上一篇下一篇

基于同源控制点的边缘绑定方法

刘梦欣¹, 张凡^1,2,3, 李天瑞^1,2,3

1 西南交通大学计算机与人工智能学院成都 611756
2 四川省制造业产业链协同与信息化支撑技术重点实验室成都 611756
3 综合交通大数据应用技术国家工程实验室成都 611756

收稿日期:2022-03-07 修回日期:2022-07-15 出版日期:2022-10-15 发布日期:2022-10-13
通讯作者: 李天瑞(trli@swjtu.edu.cn)
作者简介:(mxinl@my.swjtu.edu.cn)
基金资助:
国家自然科学基金(62176221)

Edge Bundling Method Based on Homologous Control Points

LIU Meng-xin¹, ZHANG Fan^1,2,3, LI Tian-rui^1,2,3

1 School of Computing and Artificial Intelligence,Southwest Jiaotong University,Chengdu 611756,China
2 Manufacturing Industry Chains Collaboration and Information Support Technology Key Laboratory of Sichuan Province,Chengdu 611756,China
3 National Engineering Laboratory of Integrated Transportation Big Data Application Technology,Chengdu 611756,China

Received:2022-03-07 Revised:2022-07-15 Online:2022-10-15 Published:2022-10-13
About author:LIU Meng-xin,born in 1996,postgra-duate,is a member of China Computer Federation.Her main research interests include big data analysis and techno-logy.
LI Tian-rui,born in 1969,Ph.D,professor,Ph.D supervisor,is a distinguished member of China Computer Federation.His main research interests include big data intelligence,rough sets and granular computing.
Supported by:
National Natural Science Foundation of China(62176221).

摘要/Abstract

摘要： 对含有大量复杂连接关系的节点连接图进行可视化会造成视觉上的严重混乱,边缘绑定是一种有效降低视觉混乱的方法。以往基于空间邻近性进行边缘绑定的方法会导致独立边缘产生模糊性歧义,给予用户错误的认知,而只专注于图的拓扑结构无法有效解决密集连接造成的视觉干扰问题。基于边缘路径的方法能够较好地利用图中原始节点信息对边缘进行控制绑定,从而避免独立边缘产生模糊性歧义,同时展现数据的高级模式。因此,在边缘路径方法的基础上进行了改进,提出了一种基于同源控制点的边缘绑定方法。该方法结合图的拓扑结构信息计算同源控制点,并以此为基础利用最短路径算法选取边缘控制点,然后结合分级思想对边缘聚合程度进行优化,最后通过Bézier曲线对边缘进行平滑处理。将基于同源控制点的边缘绑定方法用于美国迁移数据集和中国铁路线路数据集中,实验结果表明,该方法在改善过度绑定的问题上起到了较好的效果,相比原方法,此方法保留了更多局部数据细节,平衡了整体与局部边缘的绑定程度,可以有效地用于复杂连接图的可视化。

关键词: 节点连接图, 同源控制点, 最短路径, 边缘绑定, 图可视化

Abstract: Edge bundling is an effective method to reduce the visual clutter caused by the visualization of the node-link diagram with a large number of complex connections.Generally,the edge bundling based on spatial proximity will lead to independent edge ambiguity and give users a wrong perception.However,focusing only on topological structure of graphs cannot reduce visual clutter caused by dense connections to a large extent.The method based on edge path can control and bundle the edges by using the original nodes in the graph,avoid independent edge ambiguity,and show the advanced mode of data.Therefore,an edge bundling method based on homologous control points is proposed to improve the edge path method.Based on the topology structure information of the graph,the method can calculate homologous control points and select edge control points by using the shortest path algorithm.Then the degree of edge aggregation is optimized with the thinking of gradation.Finally,the edges are smoothed through Bezier curves and colored according to the direction of the edges.The edge bundling method based on homologous control points is used in the US migration dataset and the Chinese railway line dataset.Experimental results show that this method has a good effect on improving the problem of over-bundling.Compared with the original method,this method retains more local data details,balances the bundling degree between the whole and local edges,and can be effectively used for the visualization of complex connected graphs.

Key words: Node-link diagrams, Homologous control points, Shortest path, Edge bundling, Graph visualization

中图分类号:

TP391.41

刘梦欣, 张凡, 李天瑞. 基于同源控制点的边缘绑定方法[J]. 计算机科学, 2022, 49(10): 96-102. https://doi.org/10.11896/jsjkx.220300066

LIU Meng-xin, ZHANG Fan, LI Tian-rui. Edge Bundling Method Based on Homologous Control Points[J]. Computer Science, 2022, 49(10): 96-102. https://doi.org/10.11896/jsjkx.220300066

参考文献

[1]AUBER D.Tulip-a huge graph visualization framework,inGraph drawing software[M].Cham:Springer,2004:105-126.
[2]ZHANG H.Design of visual art elements in a sustainable urban transportation system information platform[J].Aggression and Violent Behavior,2021,12:101719.
[3]DODGE S,TOKA M,BAE C J.DynamoVis 1.0:An exploratory data visualization software for mapping movement in relation to internal and external factors[J].Movement Ecology,2021,9(1):1-17.
[4]DODGE S,NOI E.Mapping trajectories and flows:facilitating a human-centered approach to movement data analytics[J].Cartography and Geographic Information Science,2021,48(4):353-375.
[5]SCHÖTTLER S,YANG Y,PFISTER H,et al.Visualizing and interacting with geospatial networks:A survey and design space[J].Computer Graphics Forum,2021,40(6):5-33.
[6]LYU Y,LIU X,CHEN H,et al.OD Morphing:Balancing simplicity with faithfulness for OD bundling[J].IEEE Transactions on Visualization and Computer Graphics,2019,26(1):811-821.
[7]LI Y,LI T,DU S,et al.Clutter reduction of parallel coordinates based on an approximate measure of line crossing[C]//Data Science and Knowledge Engineering for Sensing Decision Support:Proceedings of the 13th International FLINS Conference (FLINS 2018).2018:492-499.
[8]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.
[9]HOLTEN D,VAN WIJK J J.Force-directed edge bundling for graph visualization[J].Computer Graphics Forum,2009,28(3):983-990.
[10]YANG H B,ZHOU H.A Distance-Based Edge-Bundling Me-thod[J].Journal of Graphics,2016,37(3):296-301.
[11]WALLINGER M,ARCHAMBAULT D,AUBER D,et al.Edge-Path Bundling:A Less Ambiguous Edge Bundling Approach[J].IEEE Transactions on Visualization and Computer Graphics,2021,28(1):313-323.
[12]DICKERSON M,EPPSTEIN D,GOODRICH M T,et al.Confluent drawings:Visualizing non-planar diagrams in a planar way[C]//International Symposium on Graph Drawing.2003:1-12.
[13]PHAN D,XIAO L,YEH R,et al.Flow map layout[C]//IEEE Symposium on Information Visualization.2005:219-224.
[14]HOLTEN D.Hierarchical edge bundles:Visualization of adja-cency relations in hierarchical data[J].IEEE Transactions on Visualization and Computer Graphics,2006,12(5):741-748.
[15]ZHOU H,YUAN X,CUI W,et al.Energy-based hierarchical edge clustering of graphs[C]//2008 IEEE Pacific Visualization Symposium.2008:55-61.
[16]LAMBERT A,BOURQUI R,AUBER D.Winding roads:Routing edges into bundles[J].Computer Graphics Forum,2010,29(3):853-862.
[17]LUO S J,LIU C L,CHEN B Y,et al.Ambiguity-free edge-bundling for interactive graph visualization[J].IEEE Transactions on Visualization and Computer Graphics,2011,18(5):810-821.
[18]WU J,YU L,YU H.Texture-based edge bundling:A web-based approach for interactively visualizing large graphs[C]//2015 IEEE International Conference on Big Data(Big Data).2015:2501-2508.
[19]ZIELASKO D,WEYERS B,HENTSCHEL B,et al.Interactive 3D force-directed edge bundling[J].Computer Graphics Forum,2016,35(3):51-60.
[20]WU B,CAO W Q.A Force-Directed Skeleton-Based Bundling with Clustering in Parallel Coordinates[J].Journal of Computer-Aided Design & Computer Graphics,2017,29(10):1807-1815.
[21]NGUYEN Q,HONG S H,EADES P.TGI-EB:A new framework for edge bundling integrating topology,geometry and importance[C]//International Symposium on Graph Drawing.2011:123-135.
[22]HURTER C,PUECHMOREL S,NICOL F,et al.Functional decomposition for bundled simplification of trail sets[J].IEEE Transactions on Visualization and Computer Graphics,2017,24(1):500-510.
[23]EPPSTEIN D,HOLTEN D,LöFFLER M,et al.Strict confluent drawing[C]//International Symposium on Graph Drawing.2013:352-363.
[24]BACH B,RICHE N H,HURTER C,et al.Towards unambiguous edge bundling:Investigating confluent drawings for network visualization[J].IEEE Transactions on Visualization and Computer Graphics,2016,23(1):541-550.
[25]ZHENG J X,PAWAR S,GOODMAN D F.Further towards unambiguous edge bundling:Investigating power-confluent dra-wings for network visualization[J].IEEE Transactions on Visualization and Computer Graphics,2019,27(3):2244-2249.
[26]WEI Z,DING S,WANG Y,et al.From river flow to spatial flow:Flow map via river flow directions assignment algorithm[J].arXiv:2110.09395,2021.
[27]ZHU L X,LIU T R,TENG F,et al.Edge Bundling Method of Spiral Graph Based on Interval Classification[J].Computer Science,2019,46(1):107-111.

相关文章 15

[1]	王永, 崔源. 基于四边形最优圈内最短路径的旅行商问题割边方法 Cutting Edge Method for Traveling Salesman Problem Based on the Shortest Paths in Optimal Cycles of Quadrilaterals 计算机科学, 2022, 49(6A): 199-205. https://doi.org/10.11896/jsjkx.210400065
[2]	陈钧吾, 余华山. 面向无尺度图的Δ-stepping算法改进策略 Strategies for Improving Δ-stepping Algorithm on Scale-free Graphs 计算机科学, 2022, 49(6A): 594-600. https://doi.org/10.11896/jsjkx.210400062
[3]	赵晓薇, 朱小军, 韩周卿. 面向定位应用的无人机的悬停位置和飞行路径优化 Hover Location Selection and Flight Path Optimization for UAV for Localization Applications 计算机科学, 2021, 48(11): 345-355. https://doi.org/10.11896/jsjkx.201000105
[4]	周建新, 张志鹏, 周宁. 基于CKSP的分段路由负载均衡技术 Load Balancing Technology of Segment Routing Based on CKSP 计算机科学, 2020, 47(4): 256-261. https://doi.org/10.11896/jsjkx.190500122
[5]	耿海军, 尹霞. 基于增量最短路径优先的域内高效路由保护算法 Efficient Intra-domain Routing Protection Algorithm Based on i-SPF 计算机科学, 2019, 46(8): 116-120. https://doi.org/10.11896/j.issn.1002-137X.2019.08.019
[6]	耿海军. 基于优化链路权值的域内路由保护方案 Intra-domain Routing Protection Scheme by Optimizing Link Weight 计算机科学, 2019, 46(1): 143-147. https://doi.org/10.11896／j.issn.1002-137X.2019.01.022
[7]	满振祯,余世明,何德峰. 基于改进伊藤算法的最短路径网络路由优化算法 Shortest Path Network Routing Optimization Algorithm Based on Improved ITO Algorithm 计算机科学, 2017, 44(7): 215-220. https://doi.org/10.11896/j.issn.1002-137X.2017.07.038
[8]	李兵奎,庄雷,马丁,胡颖,王国卿,景晨凯. SDN网络中基于业务划分的路由选择机制 Routing Mechanism Based on Business Differentiating in Software Defined Network 计算机科学, 2017, 44(3): 118-122. https://doi.org/10.11896/j.issn.1002-137X.2017.03.026
[9]	高法钦. 一种基于概率的路径预测与查询算法 Path Prediction and Query Algorithm Based on Probability 计算机科学, 2016, 43(8): 207-211. https://doi.org/10.11896/j.issn.1002-137X.2016.08.042
[10]	顾明皓,徐明. 路网中基于地理位置和区域封闭性的最短路径的查询算法 Shortest Path Searching Algorithm Based on Geographical Coordinates and Closed Attribute in Road Network 计算机科学, 2016, 43(6): 188-193. https://doi.org/10.11896/j.issn.1002-137X.2016.06.038
[11]	龙其,叶晨,张亚英. 动态路网中基于实时路况信息的分布式路径生成算法 Distributed Path Generation Algorithm Based on Real-time Traffic Information in Dynamic Road Network 计算机科学, 2014, 41(9): 259-262. https://doi.org/10.11896/j.issn.1002-137X.2014.09.049
[12]	马慧,李建国,梁瑞仕. 采用双向搜索在多权值路网中查找较优长路径 Finding Optimal Long Paths over Multi-cost Road Networks Using Bidirectional Searches 计算机科学, 2014, 41(7): 242-245. https://doi.org/10.11896/j.issn.1002-137X.2014.07.050
[13]	邓冬梅,王冠楠,朱建,高辉,陈端兵. 时序最短路径算法 Temporal Shortest Path Algorithm 计算机科学, 2014, 41(6): 185-187. https://doi.org/10.11896/j.issn.1002-137X.2014.06.036
[14]	夏正冬,卜天明,张居阳. SPFA算法的分析及改进 Analysis and Improvement of SPFA Algorithm 计算机科学, 2014, 41(6): 180-184. https://doi.org/10.11896/j.issn.1002-137X.2014.06.035
[15]	王树西,李安渝. Dijkstra算法中的多邻接点与多条最短路径问题 Multi-adjacent-vertexes and Multi-shortest-paths Problem of Dijkstra Algorithm 计算机科学, 2014, 41(6): 217-224. https://doi.org/10.11896/j.issn.1002-137X.2014.06.043

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于同源控制点的边缘绑定方法

Edge Bundling Method Based on Homologous Control Points

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0