Problems to be solved

In the visualization scene of risk control domain map, it is difficult for users to see the association between nodes because there are many nodes in the visualization map and their relationship is complex. Usually, we will use some graph layout algorithms to layout the whole graph, so that the relationship of the whole graph is clearer and easier for users to analyze.

Common graph layout algorithm are circular layout, hierarchical layout, orthogonal layout and force orientation layout, etc., usually, we will be using a certain layout algorithm in a large, or provide a way to switch the picture layout of interaction to help users analyze the problem, but often in a larger single layout is difficult to meet the business demands, Because each layout algorithm has certain advantages and disadvantages, for example, circular layout and concentric circle layout are convenient to find the nodes with the most degree in the graph, but not suitable for the case of more nodes. Hierarchical layout is good for seeing the hierarchy of nodes, but it will cause a waste of space; Force-guided layout can well avoid node overlap, but it often leads to complicated connections, which makes it difficult to analyze node association relations in the graph, and low computing performance in large scene layout. However, by switching the layout of the graph, the node positions of the whole graph need to be recalculated. Since the positions of all nodes have changed, it is not conducive to analysis, but also affects performance.

Generally, users’ urgent demand is to be able to select any node in a large graph to customize the layout. Therefore, this method aims to solve the problem that the traditional single layout method cannot well display the node association in the graph visualization scene.

Technical background

subgraph

The concept of subgraph originated from graph theory, which refers to a graph in which the node set and edge set are subsets of the node set and edge set of a graph respectively. For example: Set G = (V, E > G = (V, E > G = (V, E >, G = ‘<‘ V ‘, E > G ‘= < V’, E ‘>’ G = (V ‘, E ‘> for two figure (with the undirected graph and directed graph), if V’ ⊂ VV ‘\ subset and VV’ ⊂ V G = (V, E > G = (V, E > G = (V, E >, Then GGG is called a subgraph of G’G ‘G ‘.

Force-guided Layout algorithm (Fruchterman-Reingold)

Force-guided layout was first proposed by Peter Eades in his article “Heuristic Drawing Algorithm” in 1982. The purpose is to reduce the cross of edges in layout and keep edge lengths as consistent as possible. The method uses a spring model to simulate the layout process, and uses a spring to simulate the relationship between two nodes. After the node is affected by the elastic force, the node that is too close will be bounced away and the point that is too far will be pulled closer. Through continuous iteration, the whole layout of the map will finally reach dynamic balance and tend to be stable.

Then Thomas Fruchterman and Edward Reingold put forward a new concept of force-guided layout algorithm, namely FR algorithm (Fruchterman-Reingold) in 1991. The algorithm improved the previous spring model, enriched the physical model between nodes, added the electrostatic force between nodes, calculated the total energy of the system and minimized the energy, so as to achieve the purpose of layout. The essence of both the improved energy model and the previous spring model is energy optimization. The difference lies in the composition of the optimization function, and the optimization object includes gravity and repulsion. Different algorithms have different expressions of gravity and repulsion.

For example, for a graph GGG, there are nodes III and JJJ respectively. The euclidian distance (i.e. real distance) of the two points is denoted by s(I,j) S (I, J) S (I, J)s(I, J) is the natural length of the spring, KKK is the elastic coefficient, RRR is the electrostatic constant between the two nodes, and WWW is the weight between the two nodes. Then the formulas of the two algorithms are as follows:

Spring model:

Energy model:

Investigation of similar schemes

A visual layout method based on module decomposition of graph multi-stage task system

Firstly, the multi-stage task system module decomposition algorithm is called to decompose the graph, and a module decomposition tree is generated to represent the inner sub-structure of the graph in the form of a tree. The nodes in the tree are divided into Parallel, Serial and Neighbor according to the link law. Secondly, local layout of subgraphs is carried out from top to bottom according to node types. Different layout algorithms are used for different types of subgraphs. The principle is beautiful, non-overlapping and can reflect node clustering characteristics. Finally, the location of tree nodes is set according to the size and actual demand of the canvas. Then, the overall layout of all nodes in the tree is carried out from top to bottom based on the location of the parent node and the displacement of the child node relative to the parent node, and the final leaf node position is the layout result.

Module decomposition based on graph multi-stage system of visual layout method, through the way of all the nodes can be divided into three types to graph layout, the best means a diagram can support three kinds of layout, and the node through the module decomposition algorithm to decompose, does not provide a user-defined choice node to graph layout methods of interaction, This prevents the user from analyzing any subgraph in the graph.

For example, in a complex diagram, users usually select multiple nodes that they want to analyze, and then select the corresponding layout algorithm to layout the subgraph. Using the advantages of different layout algorithms, features of each node in the subgraph can be quickly identified.

Therefore, aiming at the above two shortcomings, this scheme proposes a visual layout method based on custom subgraph, which allows users to arbitrarily select multiple subgraphs in a large graph to carry out a variety of layout methods, enabling users to quickly and effectively analyze the information contained in the graph.

The implementation process of this scheme

Detailed description of the implementation process of the scheme:

1. Subgraph segmentation

Users can select the subgraph they want to layout from a large graph according to their own requirements. As shown in the figure below, node points with different colors represent different subgraphs. As shown in the figure below

2. Enter subgraph layout parameters

This method can support any existing layout algorithm for subgraph layout, so users need to set the layout parameters of the subgraph layout.

3. Calculate the position of all nodes in the subgraph

Each subgraph calculates the location of all nodes in the subgraph according to layout parameters set by the user. For example, you can calculate the concentric circle layout and grid layout respectively for the subgraphs in the figure above.

4. Check whether there is a definite center position of the subgraph

After computing the layout of nodes in each subgraph, there will be overlap between subgraphs. Therefore, this method allows users to customize the center location of each subgraph. In a scenario with small data volume, it is easy for users to customize the center location due to the simple graph structure. However, in the scenario of large data volume, as the graph structure becomes very complex, it is difficult for users to customize the center position of each subgraph. Therefore, this scheme provides a force-guided layout algorithm to avoid the overlapping of subgraphs after layout. The specific process is as follows

1) Firstly, this method will ignore the solid edges of nodes in all subgraphs, because the existence of solid edges will affect the position of the overall layout in the subsequent force-guided layout calculation.

2) Then each subgraph will be abstracted into a large circular virtual node.

3) A virtual edge is created between each subgraph,

4) At this point, the subgraph will be constructed into another large graph together with other nodes, and then we can calculate the positions of all nodes through the force-guided layout algorithm.

5) Since the position calculated by force-guided layout cannot keep the topological information of the original subgraph, we will record the relative position of each node, and the Laplacian difference between each node and its neighbors can be calculated by the following formula:

6) Finally, the positions of all subgraphs and other nodes are updated in batches, so as to achieve the purpose of customized layout for subgraphs.

The final result

The final layout is as follows:

conclusion

Subgraph layout has always been the focus of research in the field of graph visualization. This method abstracts subgraphs into virtual nodes and creates virtual edges, then calculates the positions of all subgraphs using force derivative algorithm, and finally maintains the original topological properties of the whole graph as far as possible by using Laplace transform. Thus, a graph can be divided into multiple custom subgraphs for different layouts. At present, it is widely used in graph analysis business scenarios.

Author: ES2049 / Kang-kyu Xie

The article can be reproduced at will, but please keep this link to the original text.

You are welcome to join ES2049 Studio. Please send your resume to [email protected]