Constrained Graph Visualization And Interactive Exploration

With the development of computer technology and the arrival of the era of big data,artificial intelligence and machine learning are very popular now.Even though machine intelligence has begun to benefit humanity,we still have to admit that human brain intelligence still far exceeds machine intelligence.Especially when human beings explore unknown data and fields,the tasks are also unclear or unknown.In these cases,human brain intelligence can discover more information that machine intelligence cannot find.Visualization provides intuitive presentation of data for human brain,assisting the human brain to explore and understand data,and helping the human brain analyze data.Another big point of visualization is to present data to end users.Graph is a basic data structure.It is suitable for relational data,such as social networks,transportation networks,and the Internet.Graph visualization combines mathematics,graph theory,and other fields.It tries to visualize complex graph data to the human brain and provide assistance for human to analysis and explore data.Matrix,arc graph and node-link diagram are the methods for graph visualization.Among them,the node-link diagram is most widely used.An high-quality layout help users to understand the data.Existing graph layout algorithms cannot produce a layout that conforms to users'perception and aesthetics,and it is still difficult for users to find hidden information and structures in the graph.All the existing issues about graph visualization motivate us to propose an improved algorithm for existing stress majorization method.Our algorithm supports multiple constraints,including direction constraints.We can achieve the purpose of controlling both the length and direction of the edge simultaneously by this method,and the previous methods only control the length of the edge or the distance between the node pair.We have integrated this algorithm into a constrained graph visualization framework,under which we can complete most of constraints of existing layout algorithms and develop new constraints.Based on this framework,we extend to a structure-aware fisheye view,to preserve the layout structure and enhance the readability of the focus area.These improvements allow us to use efficient GPU parallel computing to work with conjugate gradient solver.Our method could produce stable results quickly on large graphs.We support real-time computing and interactive exploration of large-scale graph data of 10,000 nodes,which was not possible with previous methods.In summary,the main contributions of this thesis are:we propose an unified optimization framework for graph visualization based on constraints with vector form.Then,we design a series of task-driven constraints for graph layout,and extend them to more explorative applications.There are five chapters in this thesis.In the first two chapters,we introduce the background and related works of this research.We deduce the algorithm and its extension in the chapter three.Then,the results and evaluation are introduced in the chapter four.The last chapter is about the summary and expectation of this work.