CN114036700A - A Layout Method of Network Assets Graph - Google Patents
A Layout Method of Network Assets Graph Download PDFInfo
- Publication number
- CN114036700A CN114036700A CN202111256942.2A CN202111256942A CN114036700A CN 114036700 A CN114036700 A CN 114036700A CN 202111256942 A CN202111256942 A CN 202111256942A CN 114036700 A CN114036700 A CN 114036700A
- Authority
- CN
- China
- Prior art keywords
- layout
- cluster
- nodes
- node
- bridge
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/10—Geometric CAD
- G06F30/18—Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Geometry (AREA)
- Theoretical Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Analysis (AREA)
- Computational Mathematics (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Computer Hardware Design (AREA)
- Evolutionary Computation (AREA)
- General Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
The invention discloses a layout method of a network asset graph, which comprises the following steps: s01, importing nodes and connection edge data of the network asset graph; s02, optimizing the layout speed based on the reuse of the quad-tree information; s03, optimizing the spring force of the cluster inner edge; s04, optimizing the spring force of the inner side of the bridge; s05, spring force optimization of the inter-cluster edges and layout display of the network asset map. Compared with the traditional SE-BH layout method, the layout speed can be improved by about 80%, the cluster identification degree is improved in the visual effect, and a large enough space is reserved for the inter-cluster structure, so that the bridge structure is highlighted, an observer can conveniently and quickly and accurately capture the core information and the overall topological condition of the asset map, and the method is suitable for popularization and application.
Description
Technical Field
The invention belongs to the technical field of knowledge graph processing, and particularly relates to a layout method of a network asset graph.
Background
A network asset graph is a complex heterogeneous network composed of multiple types of network assets and their associations. The assets in a network asset map are of varying sizes, and even large-scale network asset maps exist that consist of thousands of assets. In view of the situation, in the face of a heterogeneous network formed by network asset maps with different scales and generally higher complexity, a proper layout method is designed to intuitively and efficiently display the network asset maps, so that an observer can quickly and accurately capture the core information and the overall topology condition of the asset maps to form correct psychological cognition, and the problem to be solved is always solved.
In the past 50 years, the most representative graph layout algorithm was the force guidance algorithm. Force-directed algorithms, which solve the problem of map layout using a physical model of the force action between nodes, are referred to as classical force-directed algorithms. This classical force guidance algorithm, while simple and easy to implement, has some drawbacks. The layout speed of the classic force guidance algorithm is slow, the cluster structure is loose, the bridge structure is not outstanding, and in order to reduce the influence of the defects on the layout, an improved algorithm of the classic force guidance algorithm appears, such as: a force guidance algorithm for optimizing repulsion calculation, a force guidance algorithm for avoiding non-convergence of force iterative calculation, a force guidance algorithm based on an energy function model, and the like. With the increasing data volume and the increasing complexity of the network, some dimension reduction-based layout algorithms are used as a substitute method of the force-guided algorithm, so that the layout speed can be greatly increased to meet the efficient layout requirement of the large-scale network.
The above alternative methods also have some disadvantages and are not suitable for use in heterogeneous networks formed by network asset maps of varying sizes and generally higher complexity. Therefore, a new layout method of the network asset map is needed to be designed, the method can visually and efficiently display the network asset map algorithm, and an observer can quickly and accurately capture the core information and the overall topological situation of the asset map, so that correct psychological cognition is formed.
Disclosure of Invention
In order to solve the defects of the prior art and overcome the defects of the traditional force guidance layout, the invention aims to provide a layout method of a network asset map. The layout method is based on the SE-BH traditional force-guided novel network asset map for layout, the layout speed of a layout algorithm can be improved by about 80%, the cluster identification degree is improved in the visual effect, and a large enough space is reserved for an inter-cluster structure, so that the bridge structure is highlighted.
The purpose of the invention is realized by the following technical scheme:
a layout method of a network asset map comprises the following steps:
step 1, initializing layout related parameters: setting a random initial position for each node, and then respectively determining a specific calculation formula of the edge connecting spring force and the node repulsive force;
step 2, optimizing the layout speed based on the information reuse of the quadtree: the first stage, firstly, constructing a quadtree; in the second stage, the repulsive force between the node and other nodes and between the node and the center of mass is calculated; in the third stage, judging whether to reconstruct the quadtree;
step 3, spring force optimization of the cluster inner edge: identifying cluster inner edges and reducing the distance of the cluster inner edges; the inner side of the cluster is a connecting side, one end of the connecting side is connected with the center of the cluster, and the other end of the connecting side is a non-bridge node;
step 4, optimizing the spring force of the inner side of the bridge: marking the inner bridge edge, dividing the inner bridge edge into a first class inner bridge edge and a second class inner bridge edge, and setting corresponding connecting edge distance elongation strength; wherein, the distance between the inner edges of the first class of bridges is larger than the distance between the inner edges of the second class of bridges; the inner side of the first class bridge is a connecting edge connecting the center of the cluster and the bridge node, and the inner side of the second class bridge is a connecting edge connecting the two bridge nodes;
step 5, spring force optimization of the inter-cluster edges and layout display of the network asset map: enlarging the ideal distance of the inter-cluster edges, then reducing the centripetal force intensity of nodes at two ends of the inter-cluster edges, and carrying out layout display on the network asset map; the inter-cluster edge is 1/3 connected edge whose shortest path betweenness centrality is higher than the average value.
Further, in the step 1,
the initialization of the layout-related parameters comprises the following steps:
step 1.1, setting random initial positions for all nodes according to a formula I; all nodes are surrounded on a circle with a certain radius, and the initial positions of different nodes are different due to different rotation angles;
node a (x, y) ═ (r × cos (anglea), r × sin (anglea)) (formula one)
Wherein r is the radius, the default radius is 10, and angleA is the rotation angle of the node A;
step 1.2, setting spring force between nodes according to a second formula; the connecting edges between the nodes have the force similar to a spring, and in a specific implementation process, the distance between the nodes (A and B) can change along with the change of the spring force;
wherein l is an ideal distance of the connecting edge, alpha is an attenuation coefficient of the layout, and strengthh is the strength of the connecting edge (default is the minimum value of degrees of nodes at two ends of the connecting edge); particularly, the stress of the connecting edge is zero when the distance of the connecting edge is equal to the ideal distance of the connecting edge;
step 1.3, setting repulsive force between nodes according to a third formula and a fourth formula; in a specific implementation process, the calculation of the repulsive force between the nodes (a, B) is mainly implemented by the following equations three and four (i.e. the electric field strength formula), and the components of the repulsive force on the x and y axes are respectively:
Fx＝[disx(A,B)×Q(A)×Q(B)×alpha]/dis(A,B)2(III)
Fy＝[disy(A,B)×Q(A)×Q(B)×alpha]/dis(A,B)2(formula IV)
Wherein disx(A, B) is the distance, dis, of the node (A, B) on the x-axisy(A, B) is the distance of the node (A, B) on the y-axis, dis (A, B)2Is the Euclidean distance between nodes (A, B), Q (A) is a nodeA charge amount charged.
Further, in the step 2,
and the reconstruction of the quadtree is judged by the sum of the moving distances of all nodes during each iteration: in the nth iteration, when the sum of the moving distances of all nodes is 100, if the sum of the moving distances of all nodes in the (n + 1) th iteration is less than 100, at the moment, the reconstruction of the quadtree is stopped; if the sum of the moving distances of all the nodes in the (n + 1) th iteration is larger than 100, at the moment, the reconstruction of the quadtree is continued until the sum of the moving distances of all the nodes in the iteration is smaller than 100.
In the iteration, the first 120 iterations of the layout are calculated in the background (namely, no graph rendering is performed), and from the 121 st iteration, each iteration is performed with the graph rendering.
In step 2, the optimization method based on the information reuse of the quadtree mainly saves the time for constructing and calculating the quadtree in the first stage during each iteration. In principle, since the positions of the nodes change in each iteration, a quadtree needs to be constructed in each iteration; as the layout becomes stable step by step, the distance that the node moves on the layout is smaller, and at the moment, the change of the quadtree is smaller, so that the quadtree can not be recalculated, and the time for repeatedly constructing the quadtree can be saved.
And judging whether the quadtree needs to be reconstructed or not by using the sum of the moving distances of all the nodes in each iteration. Assuming that the sum of the moving distances of all nodes in one iteration is 100, since the iteration of the layout must be gradually stable, the sum of the moving distances of the nodes in the next iteration should be less than 100. But if the sum of the moving distances of all the nodes in the next iteration is more than 100, the constructed quadtree is considered to be inaccurate, and at the moment, the quadtree needs to be reconstructed.
Moreover, after each iteration of the Spring embed Barnes Hut, the node position is updated on the canvas, namely the canvas is refreshed, which is also called graph rendering. In order to reduce the rendering time consumption in the layout, the first 120 iterations of the layout are set to be calculated in the background; starting to show the layout from the 121 th iteration, and rendering the rest 180 iterations while calculating on the page, so that the change of the layout caused by the last 180 iterations is found to be small, and the overall effect is not influenced.
After the two optimization steps, the layout performance of the layout method is improved by 80%. In addition, as the process of repeatedly rendering the layout on the page is reduced, the animation effect is not very obvious blocked any more, and the method can be applied to large-scale data concentration.
In step 3, the connecting edge between the nodes has similar spring tension. In a particular implementation, the greater the distance between the nodes, the greater the spring force. Through judging the interior limit of cluster to reduce the distance of the interior limit of cluster, and then reduce the direct spring force of node, make the interior structure of cluster compacter.
In step 4, a bridge node is a node connecting important structures in the layout, and generally the layout should tend to extend the length of the bridge structure more, so that the overall layout can protrude from the bridge structure. As shown in fig. 3 of the present application, the inner edges of the first class bridge and the second class bridge are optimized respectively. Through judging whether the limit accords with the interior limit definition of bridge to set up the even limit of ideal distance elongation strength according to the classification in the bridge, at the in-process that specifically sets up, the distance between the interior limit of acquiescence one kind of bridge is greater than the distance in two kinds of bridges.
Further, in step 5, the step of,
the shortest path betweenness centrality is used for describing the connectivity of the graph, and when the shortest path betweenness centrality of one node or connecting edge is larger, the node or the connecting edge is an important bridge node or connecting edge in the graph and is connected with a plurality of different cluster structures.
In step 5, if the shortest path betweenness centrality of a connected edge is higher than 1/3 of the average value, it is defined as an inter-cluster edge. Inter-cluster edges are generally optimized by two methods: (1) enlarging the ideal distance of the edges among the clusters to highlight the connecting edges which are often used as the shortest paths among the clusters in the graph; (2) because each node can be subjected to a centripetal force towards the center of the layout, the limitation on the inter-cluster edges is reduced by reducing the centripetal force intensity of the nodes at the two ends of the inter-cluster edges.
Compared with the prior art, the invention has the following advantages and effects: because the SE-BH algorithm has 2 visual shortcomings for black grey product network asset map layout: loose cluster structure and unobtrusive bridge structure. To solve these two problems, the present application optimizes the cluster structure and the bridge structure. Through the step layout of the method, a new layout method (namely SEBH-XYQ layout method) of the network asset graph is obtained, and then the layout of the network asset graph can be realized through the SEBH-XYQ layout method. Compared with the traditional SE-BH layout method, the layout speed can be improved by about 80%, the cluster identification degree is improved in the visual effect, and a large enough space is reserved for the inter-cluster structure, so that the bridge structure is highlighted, an observer can conveniently and quickly and accurately capture the core information and the overall topological condition of the asset map, and the method is suitable for popularization and application.
Drawings
FIG. 1 is a flow diagram illustrating a method for placement of a network asset graph according to an embodiment of the invention;
FIG. 2 is a diagram illustrating the effect of spring force optimization on an inner edge of a cluster according to an embodiment of the present invention;
FIG. 3 is a diagram illustrating the classification of the inner edges of the bridge according to the embodiment of the present invention;
FIG. 4 is a diagram illustrating the effect of spring force optimization on the inner side of a bridge according to an embodiment of the present invention;
FIG. 5 is a graph illustrating the effect of spring force optimization of an inter-cluster edge according to an embodiment of the present invention;
fig. 6 is a final effect display diagram according to the embodiment of the invention.
Detailed Description
The present invention will be described in further detail with reference to examples, but the embodiments of the present invention are not limited thereto.
Unless defined otherwise, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs.
As used herein, the term "comprising" or "includes" can be open, semi-closed, and closed. In other words, the term also includes "consisting essentially of …," or "consisting of ….
The method and the device for distributing the network asset map based on SE-BH traditional force guidance can improve the distribution speed by about 80%, improve the identification degree of clusters in visual effect, and reserve a large enough space for an inter-cluster structure, so that a bridge structure is highlighted, and an observer can quickly and accurately capture the core information and the overall topology condition of the asset map.
Specifically, as shown in fig. 1, an embodiment of the present invention provides a method for laying out a network asset map, including the following steps:
step 1, initializing layout related parameters: setting a random initial position for each node, and then respectively determining a specific calculation formula of the edge connecting spring force and the node repulsive force;
step 2, optimizing the layout speed based on the information reuse of the quadtree: the first stage, firstly, constructing a quadtree; in the second stage, the repulsive force between the node and other nodes and between the node and the center of mass is calculated; in the third stage, judging whether to reconstruct the quadtree;
step 3, spring force optimization of the cluster inner edge: identifying cluster inner edges and reducing the distance of the cluster inner edges; the inner side of the cluster is a connecting side, one end of the connecting side is connected with the center of the cluster, and the other end of the connecting side is a non-bridge node;
step 4, optimizing the spring force of the inner side of the bridge: marking the inner bridge edge, dividing the inner bridge edge into a first class inner bridge edge and a second class inner bridge edge, and setting corresponding connecting edge distance elongation strength; wherein, the distance between the inner edges of the first class of bridges is larger than the distance between the inner edges of the second class of bridges; the inner side of the first class bridge is a connecting edge connecting the center of the cluster and the bridge node, and the inner side of the second class bridge is a connecting edge connecting the two bridge nodes;
step 5, spring force optimization of the inter-cluster edges and layout display of the network asset map: enlarging the ideal distance of the inter-cluster edges, then reducing the centripetal force intensity of nodes at two ends of the inter-cluster edges, and carrying out layout display on the network asset map; the inter-cluster edge is 1/3 connected edge whose shortest path betweenness centrality is higher than the average value.
In this embodiment, the network asset graph nodes and the data of the connecting edges are generally stored in JSON files after being imported, and the JSON files required by the present application are first established by using D3, so that the network asset graph is laid out by the layout method of the present application.
Further, in the step 1,
the initialization of the layout-related parameters comprises the following steps:
step 1.1, setting random initial positions for all nodes according to a formula I; all nodes are surrounded on a circle with a certain radius, and the initial positions of different nodes are different due to different rotation angles;
node a (x, y) ═ (r × cos (anglea), r × sin (anglea)) (formula one)
Wherein r is the radius, the default radius is 10, and angleA is the rotation angle of the node A;
step 1.2, setting spring force between nodes according to a second formula; the connecting edges between the nodes have the force similar to a spring, and in a specific implementation process, the distance between the nodes (A and B) can change along with the change of the spring force;
wherein l is an ideal distance of the connecting edge, alpha is an attenuation coefficient of the layout, and strengthh is the strength of the connecting edge (default is the minimum value of degrees of nodes at two ends of the connecting edge); particularly, the stress of the connecting edge is zero when the distance of the connecting edge is equal to the ideal distance of the connecting edge;
step 1.3, setting repulsive force between nodes according to a third formula and a fourth formula; in a specific implementation process, the calculation of the repulsive force between the nodes (a, B) is mainly implemented by the following equations three and four (i.e. the electric field strength formula), and the components of the repulsive force on the x and y axes are respectively:
Fx＝[disx(A,B)×Q(A)×Q(B)×alpha]/dis(A,B)2(III)
Fy＝[disy(A,B)×Q(A)×Q(B)×alpha]/dis(A,B)2(formula IV)
Wherein disx(A, B) is the distance, dis, of the node (A, B) on the x-axisy(A, B) is node (A, B) is inDistance on the y-axis, dis (A, B)2Is the euclidean distance between nodes (a, B), and q (a) is the amount of charge carried by node a.
Further, in the step 2,
and the reconstruction of the quadtree is judged by the sum of the moving distances of all nodes during each iteration: in the nth iteration, when the sum of the moving distances of all nodes is 100, if the sum of the moving distances of all nodes in the (n + 1) th iteration is less than 100, at the moment, the reconstruction of the quadtree is stopped; if the sum of the moving distances of all the nodes in the (n + 1) th iteration is larger than 100, at the moment, the reconstruction of the quadtree is continued until the sum of the moving distances of all the nodes in the iteration is smaller than 100.
In the iteration, the first 120 iterations of the layout are calculated in the background (namely, no graph rendering is performed), and from the 121 st iteration, each iteration is performed with the graph rendering.
In step 2, the optimization method based on the information reuse of the quadtree mainly saves the time for constructing and calculating the quadtree in the first stage during each iteration. In principle, since the positions of the nodes change in each iteration, a quadtree needs to be constructed in each iteration; as the layout becomes stable step by step, the distance that the node moves on the layout is smaller, and at the moment, the change of the quadtree is smaller, so that the quadtree can not be recalculated, and the time for repeatedly constructing the quadtree can be saved.
And judging whether the quadtree needs to be reconstructed or not by using the sum of the moving distances of all the nodes in each iteration. Assuming that the sum of the moving distances of all nodes in one iteration is 100, since the iteration of the layout must be gradually stable, the sum of the moving distances of the nodes in the next iteration should be less than 100. But if the sum of the moving distances of all the nodes in the next iteration is more than 100, the constructed quadtree is considered to be inaccurate, and at the moment, the quadtree needs to be reconstructed.
Moreover, after each iteration of the Spring embed Barnes Hut, the node position is updated on the canvas, namely the canvas is refreshed, which is also called graph rendering. In order to reduce the rendering time consumption in the layout, the first 120 iterations of the layout are set to be calculated in the background; starting to show the layout from the 121 th iteration, and rendering the rest 180 iterations while calculating on the page, so that the change of the layout caused by the last 180 iterations is found to be small, and the overall effect is not influenced.
After the two optimization steps, the layout performance of the layout method is improved by 80%. In addition, as the process of repeatedly rendering the layout on the page is reduced, the animation effect is not very obvious blocked any more, and the method can be applied to large-scale data concentration.
In step 3, the connecting edge between the nodes has similar spring tension. In a particular implementation, the greater the distance between the nodes, the greater the spring force. Through judging the interior limit of cluster to reduce the distance of the interior limit of cluster, and then reduce the direct spring force of node, make the interior structure of cluster compacter. As shown in the layout before optimization in fig. 2, when the cluster structure is too loose, the occupied space may be large, and other structures in the layout may be disturbed; after optimization, the cluster structure looks more compact due to the shorter connecting edge distance between the intra-cluster node and the cluster center node.
In step 4, a bridge node is a node connecting important structures in the layout, and generally the layout should tend to extend the length of the bridge structure more, so that the overall layout can protrude from the bridge structure. As shown in fig. 3 of the present application, the inner edges of the first class bridge and the second class bridge are optimized respectively; the optimization method for the inner edges of the bridges of one type is elongation to avoid the intra-cluster structure from disturbing the bridge structure, while the optimization method for the inner edges of the bridges of the second type is proper elongation to visually highlight the bridge structure. Through judging whether the limit accords with the interior limit definition of bridge to set up the even limit of ideal distance elongation strength according to the classification in the bridge, at the in-process that specifically sets up, the distance between the interior limit of acquiescence one kind of bridge is greater than the distance in two kinds of bridges. As can be seen from fig. 4, prior to optimization, multiple cluster structures were redundantly intermixed, disrupting the presentation of the bridge structure; after optimization, the relationship between clusters in the overall vision is obviously clearer, the link relationship can be effectively displayed, and enough space is reserved for displaying the bridge structure.
Further, in step 5, the step of,
the shortest path betweenness centrality is used for describing the connectivity of the graph, and when the shortest path betweenness centrality of one node or connecting edge is larger, the node or the connecting edge is an important bridge node or connecting edge in the graph and is connected with a plurality of different cluster structures.
In step 5, if the shortest path betweenness centrality of a connected edge is higher than 1/3 of the average value, it is defined as an inter-cluster edge. Inter-cluster edges are generally optimized by two methods: (1) enlarging the ideal distance of the edges among the clusters to highlight the connecting edges which are often used as the shortest paths among the clusters in the graph; (2) because each node can be subjected to a centripetal force towards the center of the layout, the limitation on the inter-cluster edges is reduced by reducing the centripetal force intensity of the nodes at the two ends of the inter-cluster edges. In fig. 5, the dashed connecting edges indicate connecting edges elongated during optimization of the inter-cluster edges, which somewhat highlight the overall structure. A comparison of the effects before and after optimization is also shown in fig. 5.
The display effect diagram of the network asset diagram of the embodiment after layout by the layout method is shown in fig. 6. As can be seen from fig. 6, after the network asset map is optimized in layout, the cluster identification degree is improved in visual effect, and a large enough space is reserved for the inter-cluster structure, so that the bridge structure is highlighted, and an observer can quickly and accurately capture the core information and the overall topology condition of the asset map.
Because the SE-BH algorithm has 2 visual shortcomings for black grey product network asset map layout: loose cluster structure and unobtrusive bridge structure. To solve these two problems, the present application optimizes the cluster structure and the bridge structure. Through the step layout of the method, a new layout method (namely SEBH-XYQ layout method) of the network asset graph is obtained, and then the layout of the network asset graph can be realized through the SEBH-XYQ layout method. Compared with the traditional SE-BH layout method, the layout speed can be improved by about 80%, the cluster identification degree is improved in the visual effect, and a large enough space is reserved for the inter-cluster structure, so that the bridge structure is highlighted, an observer can conveniently and quickly and accurately capture the core information and the overall topological condition of the asset map, and the method is suitable for popularization and application.
The above embodiments are preferred embodiments of the present invention, but the present invention is not limited to the above embodiments, and any other changes, modifications, substitutions, combinations, and simplifications which do not depart from the spirit and principle of the present invention should be construed as equivalents thereof, and all such changes, modifications, substitutions, combinations, and simplifications are intended to be included in the scope of the present invention.
Claims (7)
1. A method for laying out a network asset map is characterized by comprising the following steps:
step 1, initializing layout related parameters: setting a random initial position for each node, and then respectively determining a specific calculation formula of the edge connecting spring force and the node repulsive force;
step 2, optimizing the layout speed based on the information reuse of the quadtree: the first stage, firstly, constructing a quadtree; in the second stage, the repulsive force between the node and other nodes and between the node and the center of mass is calculated; in the third stage, judging whether to reconstruct the quadtree;
step 3, spring force optimization of the cluster inner edge: identifying cluster inner edges and reducing the distance of the cluster inner edges; the inner side of the cluster is a connecting side, one end of the connecting side is connected with the center of the cluster, and the other end of the connecting side is a non-bridge node;
step 4, optimizing the spring force of the inner side of the bridge: marking the inner bridge edge, dividing the inner bridge edge into a first class inner bridge edge and a second class inner bridge edge, and setting corresponding connecting edge distance elongation strength; wherein, the distance between the inner edges of the first class of bridges is larger than the distance between the inner edges of the second class of bridges; the inner side of the first class bridge is a connecting edge connecting the center of the cluster and the bridge node, and the inner side of the second class bridge is a connecting edge connecting the two bridge nodes;
step 5, spring force optimization of the inter-cluster edges and layout display of the network asset map: enlarging the ideal distance of the inter-cluster edges, then reducing the centripetal force intensity of nodes at two ends of the inter-cluster edges, and carrying out layout display on the network asset map; the inter-cluster edge is 1/3 connected edge whose shortest path betweenness centrality is higher than the average value.
2. The method for layout of a network asset map according to claim 1, wherein the initialization of the layout-related parameters in step S01 comprises the steps of:
step 1.1, setting random initial positions for all nodes according to a formula I;
nodeA (x, y) ═ (r × cos (anglea), r × sin (anglea)) (formula one)
Where r is the radius, the default radius is 10, and angleA is the rotation angle of node a.
3. The method of claim 2, wherein the initialization of the layout-related parameters further comprises the steps of:
step 1.2, setting spring force between nodes according to a second formula;
wherein l is the ideal distance of the connecting edge, alpha is the attenuation coefficient of the layout, and strengthh is the strength of the connecting edge.
4. The method of claim 3, wherein the initialization of the layout-related parameters further comprises the steps of:
step 1.3, setting repulsive force between nodes according to a third formula and a fourth formula; the repulsive force between the nodes (A, B) is calculated by the following equations three and four, and the components of the repulsive force on the x and y axes are respectively:
Fx＝[disx(A，B)×Q(A)×Q(B)×alpha]/dis(A，B)2(III)
Fy＝[disy(A，B)×Q(A)×Q(B)×alpha]/dis(A，B)2(formula IV)
Wherein disx(A, B) is the distance, dis, of the node (A, B) on the x-axisy(A, B) is the distance of the node (A, B) on the y-axis, dis (A, B)2Is the euclidean distance between nodes (a, B), and q (a) is the amount of charge carried by node a.
5. The method of claim 1, wherein in step S02, the reconstruction of the quadtree is determined by the sum of the moving distances of all nodes at each iteration: in the nth iteration, when the sum of the moving distances of all nodes is 100, if the sum of the moving distances of all nodes in the (n + 1) th iteration is less than 100, at the moment, the reconstruction of the quadtree is stopped; if the sum of the moving distances of all the nodes in the (n + 1) th iteration is larger than 100, at the moment, the reconstruction of the quadtree is continued until the sum of the moving distances of all the nodes in the iteration is smaller than 100.
6. The method of claim 5, wherein the first 120 iterations of the layout are performed in a background calculation, and wherein from the 121 th iteration, each iteration is performed with a graph rendering.
7. The method according to claim 1, wherein in step S05, the shortest path betweenness centrality is used to describe connectivity of the graph, and when the shortest path betweenness centrality of a node or a connecting edge is higher, the node or the connecting edge is an important bridge node or connecting edge in the graph, and connects a plurality of different cluster structures.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202111256942.2A CN114036700B (en) | 2021-10-27 | 2021-10-27 | A Layout Method of Network Assets Graph |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202111256942.2A CN114036700B (en) | 2021-10-27 | 2021-10-27 | A Layout Method of Network Assets Graph |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN114036700A true CN114036700A (en) | 2022-02-11 |
| CN114036700B CN114036700B (en) | 2022-07-01 |
Family
ID=80135511
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202111256942.2A Active CN114036700B (en) | 2021-10-27 | 2021-10-27 | A Layout Method of Network Assets Graph |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN114036700B (en) |
Citations (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20090296600A1 (en) * | 2005-10-28 | 2009-12-03 | Geoffrey Canright | Method and Device for Analysis and Visualization of a Network |
| US10586358B1 (en) * | 2017-05-10 | 2020-03-10 | Akamai Technologies, Inc. | System and method for visualization of beacon clusters on the web |
| US20200159874A1 (en) * | 2018-11-16 | 2020-05-21 | Two Six Labs, LLC | Dynamic updating of a force approximation data model |
| CN111464338A (en) * | 2020-03-16 | 2020-07-28 | 哈尔滨安天科技集团股份有限公司 | Step-by-step layout method and system for complex network topology |
| CN111897973A (en) * | 2020-08-10 | 2020-11-06 | 厦门渊亭信息科技有限公司 | WebGL-based mass node knowledge graph visual layout method and system |
| CN112597317A (en) * | 2021-01-11 | 2021-04-02 | 西藏民族大学 | Knowledge graph visualization method and system |
| CN112632196A (en) * | 2021-01-06 | 2021-04-09 | 中国工商银行股份有限公司 | Data visualization method and device and storage medium |
| CN112989028A (en) * | 2021-02-26 | 2021-06-18 | 江苏大学 | Knowledge graph layout optimization method based on force-oriented algorithm |
-
2021
- 2021-10-27 CN CN202111256942.2A patent/CN114036700B/en active Active
Patent Citations (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20090296600A1 (en) * | 2005-10-28 | 2009-12-03 | Geoffrey Canright | Method and Device for Analysis and Visualization of a Network |
| US10586358B1 (en) * | 2017-05-10 | 2020-03-10 | Akamai Technologies, Inc. | System and method for visualization of beacon clusters on the web |
| US20200159874A1 (en) * | 2018-11-16 | 2020-05-21 | Two Six Labs, LLC | Dynamic updating of a force approximation data model |
| CN111464338A (en) * | 2020-03-16 | 2020-07-28 | 哈尔滨安天科技集团股份有限公司 | Step-by-step layout method and system for complex network topology |
| CN111897973A (en) * | 2020-08-10 | 2020-11-06 | 厦门渊亭信息科技有限公司 | WebGL-based mass node knowledge graph visual layout method and system |
| CN112632196A (en) * | 2021-01-06 | 2021-04-09 | 中国工商银行股份有限公司 | Data visualization method and device and storage medium |
| CN112597317A (en) * | 2021-01-11 | 2021-04-02 | 西藏民族大学 | Knowledge graph visualization method and system |
| CN112989028A (en) * | 2021-02-26 | 2021-06-18 | 江苏大学 | Knowledge graph layout optimization method based on force-oriented algorithm |
Non-Patent Citations (7)
| Title |
|---|
| BONGSHIN LEE等: "Task Taxonomy for Graph Visualization", 《2006 ACM》, 6 May 2006 (2006-05-06), pages 1 - 5, XP058157207, DOI: 10.1145/1168149.1168168 * |
| KWAN-LIU MA等: "Large-Scale Graph Visualization and Analytics", 《IEEE COMPUTER SOCIETY》, 31 July 2013 (2013-07-31), pages 39 - 46, XP011526350, DOI: 10.1109/MC.2013.242 * |
| SHUOWEN FU等: "Heterogeneous Graph Modeling and Visualization for Cyber Asset Management", 《2021 8TH INTERNATIONAL CONFERENCE ON DEPENDABLE SYSTEMS AND THEIR APPLICATIONS》, 6 August 2021 (2021-08-06), pages 745 - 746 * |
| 伍勇: "面向社区分析的网络数据可视化技术研究", 《中国优秀硕士学位论文全文数据库 信息科技辑》, 15 January 2015 (2015-01-15), pages 138 - 756 * |
| 刘念: "复杂关系数据可视化技术研究与应用", 《中国硕士学位论文全文数据库 信息科技辑》, 15 May 2020 (2020-05-15), pages 138 - 112 * |
| 吴玲达等: "基于社团结构节点重要性的网络可视化压缩布局", 《北京航空航天大学学报》, no. 12, 20 August 2019 (2019-08-20), pages 2423 - 2430 * |
| 陈力平等: "基于节点相似度的力引导改进算法", 《计算机应用》, 19 July 2017 (2017-07-19), pages 214 - 218 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN114036700B (en) | 2022-07-01 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Selassie et al. | Divided edge bundling for directional network data | |
| CN103942308B (en) | The detection method and device of extensive myspace | |
| Holten et al. | Force‐directed edge bundling for graph visualization | |
| US20130127857A1 (en) | System and Method for Generating a Manifold Surface for a 3D Model of an Object Using 3D Curves of the Object | |
| Theisel | Designing 2D vector fields of arbitrary topology | |
| CN113034685A (en) | Method and device for superposing laser point cloud and high-precision map and electronic equipment | |
| CN112215864B (en) | Contour processing method and device of electronic map and electronic equipment | |
| CN112100450A (en) | Graph calculation data segmentation method, terminal device and storage medium | |
| US20100063953A1 (en) | Converting unordered graphs to oblivious read once ordered graph representation | |
| CN114491073A (en) | A method and system for realizing visual editing and persistence of knowledge graph | |
| CN118036224A (en) | Automatic mapping method and system for distribution network single line diagram sketch based on visual model | |
| CN112991529B (en) | Partition algorithm for meshing map by utilizing triangle | |
| US20240062469A1 (en) | Data processing method, apparatus, device, and medium | |
| CN114880337A (en) | Map data integrated updating method, device, equipment and storage medium | |
| WO2011025385A1 (en) | Method for local refinement of a geometric or physical representation | |
| CN114036700A (en) | A Layout Method of Network Assets Graph | |
| CN113959400B (en) | Intersection vertex height value acquisition method and device, electronic equipment and storage medium | |
| CN111367999B (en) | Blockchain method and system, electronic device and computer-readable storage medium | |
| Vihrovs et al. | An inverse distance-based potential field function for overlapping point set visualization | |
| CN110427583B (en) | Method for drawing map mass lines at mobile terminal in sparse mode | |
| CN110795822A (en) | Traffic network semantic modeling method and device, electronic equipment and storage medium | |
| CN111159480B (en) | Graph drawing method based on power grid GIS data | |
| CN114913304A (en) | A Triangular Mesh Reconstruction Method Based on Region Expansion | |
| Tian et al. | An approach to generate spatial Voronoi Treemaps for points, lines, and polygons | |
| Kim et al. | Single image–based 3D tree and growth models reconstruction |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |