Research On Node Layout And Edge Bundling Optimization Problem In Graph Visualization

Graph data is a common abstract type of data,commonly used in social networks,finance,biology,and other fields.Graph visualization is an important research problem in the field of information visualization.After decades of research,there have been many different visualization methods in the field of graph visualization,each presenting graph data in different forms.One of the most popular graph visualization methods is the node-linked diagram,in which nodes are drawn on the screen to represent entities in the data,and a line is drawn between the nodes to indicate the existence of relationships between the entities.Due to its simplicity and directness,ease to understand,and other characteristics,the node-linked diagram is the most widely used graph visualization method.The key to drawing node-link diagrams is to design a suitable node layout method that effectively represents the structure of the graph data.Researchers have designed a large number of graph layout methods for node layout,however,there is no theory to explain the deep connection between these methods in principle,which makes it difficult for users to choose the most suitable graph layout method for their data.Meanwhile,for large-scale graph data,the layout results for the whole graph layout usually cannot effectively present all its local structures.For this reason,researchers have proposed various methods for interactive exploration of local subgraphs.However,existing graph local exploration methods cannot both highlight the neighbor relationships of the important node and show the clustering and connectivity relationships among the neighbors of the important node,making it difficult for users to understand the structure of local subgraphs accurately.In addition,when the edge density of graph data is too high,the dense edges will prevent users from observing the connectivity relationships between nodes,and researchers have proposed edge bundling methods to reduce the visual complexity of graph visualization results by aggregating edges with similar trends.However,the existing edge bundling methods often have difficulty in balancing the global and local bundling results,and the interaction tools are single,which cannot meet the data analysis needs of users.To address the above shortcomings of node-linked diagrams,this dissertation proposes new methods for the three problems of how to optimize the overall node layout,local subgraph layout and edge bundling of node-linked graphs,respectively.Specifically,the main contributions of this dissertation are as follows:(1)Aiming at the problem of difficult user understanding and selection on the large variety of node-relationship graph layout methods with different mechanisms,a layout framework based on a unified force model representation and an Augmented Stochastic Gradient Descent layout solver,Taurus,is proposed,which provides a unified understanding and comparison of most existing graph layout methods.It provides a unified computational model and optimization method for understanding and comparing most existing graph layout methods,and also provides a guiding principle for designing new graph layout methods.(2)To address the problem that the traditional radial layout method is difficult to show the cluster structure and neighbor structure in subgraphs,an important node-centered radial graph layout method,the Target Netgram,is proposed by extending the unified force model representation from the force direction perspective,and variety of interaction methods is designed to better support the important node-centered subgraph exploration.(3)To address the problem that edge bundling algorithms are difficult to adjust the parameters and take into account the global structure and local details of the bundling,an interactive edge bundling seamless blending algorithm for edge-dense graphs is proposed by extending the unified force model representation from the graph layout problem to the edge bundling problem,which allows users to freely choose different edge bundling algorithms to visually simplify the edges in any region of the graph visualization results.A rendering method based on edge density and edge attributes is also designed to improve the visualization of the edge bundle results.In summary,this dissertation proposes three methods for optimizing node-linked diagrams in graph visualization and designs flexible and diverse interaction methods to effectively improve the visualization and interaction flexibility of node-linked diagrams.