Force-Directed Graph Layout Based On The T-Distribution And Its Approximate Solution Method

Graph data is a data type that represents relationships between entities,and is widely found in finance,healthcare,and social networks.In the field of information visualization,researchers have proposed many graph visualization methods.These methods present complex graph data in an intuitive and understandable form to users,allowing them to explore,analyze,and mine structural information and hidden patterns in graph data.Graph layout algorithms are the core technology of graph visualization.An ideal graph layout algorithm should be able to quickly generate clear and accurate layout results,making it easy for users to obtain useful information and make more accurate decisions.At the same time,it should maintain readability and aesthetics as much as possible to enhance the attractiveness and information expression efficiency of the visualization results.Force-directed placement layouts are currently the most widely applied graph layout methods.These methods analogizes nodes and edges to springs and electrons,respectively,constructing a physical model.This model is simple,intuitive,and easy to implement,and it performs well on most small-scale graph data.However,for larger-scale graph data,existing forcedirected models still suffer from poor layout quality and low efficiency.First,in terms of layout quality,our study found that the design principles of force-directed models do not explicitly require the preservation of neighborhood structure,resulting in poor performance in maintaining neighbor and cluster structures.On the other hand,existing force-directed model’s approximate solutions still have shortcomings in efficiency or accuracy,making it impossible to quickly generate layout results.To address the above issues of layout quality and efficiency,this thesis proposes a new force-directed model and introduces an advanced approximate solution method.First,this thesis revisited the classic force-directed model and analyzes its shortcomings in capturing neighbor and cluster structures in graph data through two typical case studies.To this end,a new design principle is added to the classic force-directed model to maintain the neighborhood structure.Subsequently,combining the new design principle,this thesis summarizes some basic requirements for finding new force functions.Guided by the new design principle and basic requirements,this thesis proposes a new short-range force called t-force,which takes the form of a negative gradient of the probability density function of the t-distribution.It can replace the original repulsive force or act as a short-range attractive force as part of the attractive force,allowing the attractive force to decouple over long and short ranges.Based on t-force,a new force-directed model called t-FDP is constructed to better maintain the global structure,local structure,and cluster information of the graph.To improve the solving efficiency of the t-FDP model,this thesis introduces an efficient approximation method based on interpolation and fast Fourier transform from the dimensionality reduction field.This method reduces the time complexity of the algorithm from the traditional Barnes-Hut approximation method’s O(n log n)to near-linear complexity while ensuring a small error.To validate the effectiveness of the t-FDP model and its approximate solution method,this thesis employs a series of quantitative indicators and compares them with the most relevant graph layout methods and approximation methods.Quantitative evaluation results confirm that,in terms of layout quality,the t-FDP model has a significant advantage in maintaining neighbor structures while maintaining global structures and cluster structures well,and it is on par or better than other methods in other readability and aesthetics evaluations.In terms of layout efficiency,the CPU version of the approximation method is an order of magnitude faster than existing graph layout methods on large-scale graph data,while the GPU version is an additional order of magnitude faster.This thesis also presents two extended applications of t-FDP to shows its flexibility and practicality.