Computer Science

Computer Science ›› 2022, Vol. 49 ›› Issue (10): 96-102.doi: 10.11896/jsjkx.220300066

• Database & Big Data & Data Science • Previous Articles     Next Articles

Edge Bundling Method Based on Homologous Control Points

LIU Meng-xin1, ZHANG Fan1,2,3, LI Tian-rui1,2,3   

  1. 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).

PDF (PC)

406

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

CLC Number: 

  • TP391.41
[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.
[1] WANG Yong, CUI Yuan. Cutting Edge Method for Traveling Salesman Problem Based on the Shortest Paths in Optimal Cycles of Quadrilaterals [J]. Computer Science, 2022, 49(6A): 199-205.
[2] CHEN Jun-wu, YU Hua-shan. Strategies for Improving Δ-stepping Algorithm on Scale-free Graphs [J]. Computer Science, 2022, 49(6A): 594-600.
[3] ZHAO Xiao-wei, ZHU Xiao-jun, HAN Zhou-qing. Hover Location Selection and Flight Path Optimization for UAV for Localization Applications [J]. Computer Science, 2021, 48(11): 345-355.
[4] GENG Hai-jun, YIN Xia. Efficient Intra-domain Routing Protection Algorithm Based on i-SPF [J]. Computer Science, 2019, 46(8): 116-120.
[5] ZHU Li-xia, LI Tian-rui, TENG Fei, PENG Bo. Edge Bundling Method of Spiral Graph Based on Interval Classification [J]. Computer Science, 2019, 46(1): 107-111.
[6] MAN Zhen-zhen, YU Shi-ming and HE De-feng. Shortest Path Network Routing Optimization Algorithm Based on Improved ITO Algorithm [J]. Computer Science, 2017, 44(7): 215-220.
[7] ZUO Xiu-feng and SHEN Wan-jie. Improved Algorithm about Muti-shortest Path Problem Based on Floyd Algorithm [J]. Computer Science, 2017, 44(5): 232-234.
[8] LI Bing-kui, ZHUANG Lei, MA Ding, HU Ying, WANG Guo-qing and JING Chen-kai. Routing Mechanism Based on Business Differentiating in Software Defined Network [J]. Computer Science, 2017, 44(3): 118-122.
[9] GAO Fa-qin. Path Prediction and Query Algorithm Based on Probability [J]. Computer Science, 2016, 43(8): 207-211.
[10] GU Ming-hao and XU Ming. Shortest Path Searching Algorithm Based on Geographical Coordinates and Closed Attribute in Road Network [J]. Computer Science, 2016, 43(6): 188-193.
[11] LONG Qi,YE Chen and ZHANG Ya-ying. Distributed Path Generation Algorithm Based on Real-time Traffic Information in Dynamic Road Network [J]. Computer Science, 2014, 41(9): 259-262.
[12] MA Hui,LI Jian-guo and LIANG Rui-shi. Finding Optimal Long Paths over Multi-cost Road Networks Using Bidirectional Searches [J]. Computer Science, 2014, 41(7): 242-245.
[13] WANG Shu-xi and LI An-yu. Multi-adjacent-vertexes and Multi-shortest-paths Problem of Dijkstra Algorithm [J]. Computer Science, 2014, 41(6): 217-224.
[14] DENG Dong-mei,WANG Guan-nan,ZHU Jian,GAO Hui and CHEN Duan-bing. Temporal Shortest Path Algorithm [J]. Computer Science, 2014, 41(6): 185-187.
[15] XIA Zheng-dong,BU Tian-ming and ZHANG Ju-yang. Analysis and Improvement of SPFA Algorithm [J]. Computer Science, 2014, 41(6): 180-184.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.