JP5700841B2 - Graph data visualization display device, method, and program - Google Patents

Description

  The present invention relates to a graph data visualization display device, method, and program, and more particularly, to a graph data visualization display device, method, and program for visualizing graph data composed of a plurality of nodes and edges connecting the nodes.

  A technique for visualizing a network as a graph (hereinafter simply referred to as “visualization technique”) generally refers to visualizing graph data that forms a network based on the relationship between data. The graph data can be visualized by expressing it with a node indicating the element and an edge connecting the nodes. For example, in the case of a WEB page with hyperlinks on the Internet, graph visualization can be performed by expressing each WEB page as a node and a hyperlink as an edge. In addition, for example, network display such as finance / communication / transport / social organization / gene information, graph display of data such as chemistry / biology / medicine, and graph display of text data and image data based on relevance Various applications are possible, such as display of the display, combination display of related module groups (for example, an LSI design drawing of an IC chip), and label display used for graphical display of maps and reference books. Therefore, a graph visualization display technique using a mechanical algorithm by a computer is a technique in demand in a very wide range of fields.

<Conditions>
An important and greatest object in the graph visualization display technology is that it is preferable to satisfy the following two conditions as much as possible on the graph visualization display device.

  [Condition 1] Arrange the nodes so as not to overlap each other.

  [Condition 2] Relevant nodes are connected via an edge and arranged in the vicinity.

  These conditions are shown in FIG. [Condition 1] is to prevent misreading of information due to overlapping display of different node information. [Condition 2] is to improve visual information recognition accuracy by arranging related nodes in the vicinity. In order to satisfy the above two conditions, it is necessary to obtain the arrangement coordinates of the node on the graph visualization display device.

<Related technologies>
[Basic technology]
Conventionally, a technique using a dynamic model has been widely used as a graph visualization display technique for satisfying the above conditions, and the following two are most frequently used all over the world.

  ・ Spring model method: This is a method in which a virtual spring is assumed between all nodes and the coordinate update method is sequentially performed one node at a time. In general, the number of shortest path paths on the graph between the nodes is calculated as the natural length of the spring between the nodes (for example, see Non-Patent Document 1).

  Force-directed method: Gives a repulsive force between all nodes (for example, Coulomb repulsive force that works between molecules), gives an attractive force between connected nodes (edges), and updates coordinates with this attractive force The total sum of repulsive forces is used for updating (for example, see Non-Patent Document 2).

  In either of the two methods described above, a repulsive force is exerted between all the nodes, and it is possible to eliminate the overlap between the nodes required by [Condition 1]. In addition, an attractive force works between the nodes to be connected, and the connection nodes required in [Condition 2] can be arranged in the vicinity.

  In the above two methods, when the attractive and repulsive functions are uniquely determined, the coordinates are set so that the objective function converges (maximum entropy is obtained) using a numerical calculation method such as the steepest descent method or Newton method. Update.

  With respect to the above condition 2, various methods have been proposed since the 1980s regarding the graph visualization display technique for the technique of “obtaining an optimum arrangement at high speed”. There are roughly two approaches to the problem of finding the optimum arrangement at high speed.

  [Approach 1] Perform efficient initial placement to speed up convergence on the objective function of numerical computations.

  [Approach 2] Speed up numerical calculations for optimal placement.

  Normally, [Approach 2] is particularly effective for speeding up the operation, and the key is how fast the processing is performed. However, in the present invention, a problem that is regarded as a problem is a request for a technique for visualizing and displaying graphs in real time for "streaming data whose data structure keeps changing such as the number of nodes and the number of edges". Therefore, the “efficient initial arrangement method” described in [Approach 1] is required particularly for the graph visualization display that handles large-scale streaming data. In [Approach 2], several methods have been proposed for speeding up using an approximation method in particular. However, since this method is compatible with and compatible with the present invention, it is included as a subject of the present invention. Absent.

  In [Approach 1], as a typical method, there is a graph visualization calculation method using the LGL method (for example, see Non-Patent Document 3). The LGL method creates a minimum spanning tree from a graph data structure and draws based on the created spanning tree.

  In addition, a method has been proposed in which calculation processing is performed by placing the higher order near the center in consideration of the order (see, for example, Patent Document 1). This method is very effective when the target graph data is about several tens to several hundreds of nodes and all the nodes are connected.

Japanese Patent Laid-Open No. 2002-312803

Kamada, T., and Kawai, S .: An algorithm for drawing general undirected graphs, Information Processing Letters, 12, 31, 7-15 (1989). Fruchterman, T. M. J., and Reingold, E. M .: Graph Drawing by Force-directed Placement, Software-Practice and Experience, 11, 21, 1129-1164 (1991). Adai, LGL: creating a map of protein function with an algorithm for visualizing very large biological networks Lyon, B .: The Opte Project (2005) .http: //www.opte.org/

  A fundamental requirement for the above-described graph visualization display technique is “to obtain an optimum arrangement at high speed”. Specifically, graph data within a window displayed on a personal computer display device or within the size of image data that can withstand printing (in reality, several hundred to several thousand nodes) should be displayed in the window. In a few seconds, it is necessary to calculate the arrangement within a few minutes even for printed materials. At this time, it is required to satisfy the above two conditions “nodes do not overlap” and “relevant things are arranged in the vicinity”.

  In recent years, microblogging using Social Networking Service (SNS) such as Twitter (registered trademark) and Facebook (registered trademark) has become popular, and data continues to increase. In the large-scale data analysis that continues to increase on the Web, it is required to process the data stream in real time and “visualize” it at the same time. Therefore, in the graph visualization technique, there is a demand for a visualization technique for streaming data whose data structure keeps changing, such as the number of nodes and the number of edges changing.

  In addition, in the method using the minimum spanning tree in [Approach 1] in the initial arrangement and the streaming processing, the influence of approximation that eliminates the connection relation is strong, so that the node of the extremely remote node has the edge connection. Undesirable results occur because of the pairing. That is, [Condition 1] can be satisfied, but [Condition 2] cannot sufficiently satisfy the readability.

  Further, the method of Patent Document 1 is not an effective means for graph data composed of partial graphs or particularly large-scale graph data.

  The present invention has been made in view of the above points, and in the graph visualization display technology, nodes do not overlap each other with respect to streaming data whose data structure continues to change, such as the number of nodes and the number of edges, and the like. It is an object of the present invention to provide a graph data visualization display device, method and program that satisfy two conditions that the related ones are arranged in the vicinity and can obtain an optimum arrangement at high speed in real time.

In order to solve the above problems, the present invention (Claim 1) is a graph visualization display device for visualizing graph data composed of a plurality of nodes and edges connecting the nodes,
Processing means for generating a graph visualization image based on graph data expressing a relationship between a plurality of nodes and the nodes as edges;
Display means for displaying the graph visualization image generated in the processing means,
The processing means includes
Wherein when on the display space displayed on the display unit to add a node is a connection relationship between additional nodes that will be added, the additional node to the center of gravity of the existing arrangement node group that have already been arranged after placing the, correct the position of each node according to Jo Tokoro dynamics model,
When adding a plurality of additional nodes, the arrangement is made before any additional nodes that are connected to any of the existing arrangement nodes, rather than the additional nodes that are connected to only one of the plurality of additional nodes. .

The present invention (Claim 2 ) provides the processing means,
When placing the additional node to the center of gravity of the existing arrangement node group, if the node with the same connection information exists, to add the additional node staggered arrangement minutely using a random number.

The present invention (Claim 3 ) provides the processing means,
When the additional node is only one connection relationship is between the existing arrangement node, place the additional node to the vicinity of the existing arrangement nodes in a connected relationship.

Further, the present invention (Claim 4 ) provides the processing means,
Said additional node is not connected to the relationship between the pre-Symbol existing placement node, it placed anywhere on the display space.

  As described above, according to the present invention, when addition or deletion occurs in node information of graph data such as streaming data or time-series graph data, the processing speed in the graph visualization display is improved, and It is possible to achieve a high degree of compatibility between the demands for quality improvement and high-speed processing through efficiency.

It is a figure which shows the conditions requested | required of a graph visualization display technique. It is a block diagram of the graph visualization display apparatus in one embodiment of this invention. It is a flowchart of operation | movement of the processing apparatus in one embodiment of this invention. It is a flowchart of the process of the additional node arrangement | positioning determination part in one embodiment of this invention. It is FIG. (1) which shows the arrangement | positioning method of the additional node in one embodiment of this invention. It is FIG. (2) which shows the arrangement | positioning method of the additional node in one embodiment of this invention. It is FIG. (The 3) which shows the arrangement | positioning method of the additional node in one embodiment of this invention. It is an example of co-occurrence graph visualization using person data in an embodiment of the present invention. It is sample data (the 1) in one embodiment of the present invention. It is sample data (the 2) in one embodiment of the present invention. It is FIG. (1) which shows a comparison with a prior art and this invention. It is FIG. (The 2) which shows a comparison with a prior art and this invention.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

  FIG. 2 shows a configuration of a graph data visualization display device according to an embodiment of the present invention.

  The graph visualization display device 10 shown in the figure stores a storage device 14 that stores graph data to be processed, a processing device (CPU) 11 that executes graph visualization display processing by program control, and a program that controls the processing device 11. Main memory 12 and display device 13 for displaying a visualized image of graph data generated by processing device 11.

  FIG. 2 shows only the configuration for realizing the present embodiment. Actually, in addition to the configuration of FIG. 2, it is assumed that an input device such as a keyboard and a mouse for inputting various commands and data, various peripheral devices, an interface for a network, and the like are provided.

  In addition, the graph data visualization display device according to the present embodiment performs optimization calculation of node coordinates according to an additional node initial arrangement determination unit 21 to be added based on graph data, a deletion node processing unit 22, and a predetermined dynamic model. A node arrangement coordinate optimization update processing unit 23 for performing various components, which are virtual software programs realized in the processing device 11 controlled by a computer program held in the main memory 12.

  FIG. 3 is a flowchart of the operation of the processing apparatus according to the embodiment of the present invention.

  In the following, the addition node initial placement determination unit 21, the deletion node processing unit 22, and the node placement coordinate optimization update processing unit 23 perform the addition node deletion, the deletion node deletion, and the optimization update processing of the coordinates of all nodes. explain.

  Step 301) Obtain graph data from the storage device 14.

  Step 302) The processing apparatus 11 determines the timing for adding or deleting each node. For the timing, for example, Wikipedia (registered trademark) person list data (FIGS. 8 to 12 described later), the birth year and death year data is read, the time window is set to one year, and the birth year is set. It is determined by performing pre-processing so as to add a node (in this case, a person) and to delete the node at the end of the year.

  Step 303) If it is time to update the node information, the process proceeds to step 304; otherwise, the process proceeds to step 306.

  Step 304) The additional node arrangement determining unit 21 determines the coordinates of the additional node. Detailed processing will be described later with reference to FIG.

  Step 305) The delete node processing unit 22 deletes the delete node. Actually, when it is not included in the list at the time of node update, it is excluded at the update timing.

  Step 306) The node arrangement coordinate optimization update processing unit 23 calculates and updates the optimum arrangement of nodes from the equation of motion according to a predetermined dynamic model. As the optimization, for example, the Newton method can be used.

  Step 307) The node arrangement coordinate optimization update processing unit 23 updates the coordinates of all nodes.

  Step 308) If the stop condition is satisfied, the process is terminated; otherwise, the process proceeds to Step 303.

  Next, the process in step 304 will be described.

  FIG. 4 is a flowchart of the process of the additional node arrangement determining unit in the embodiment of the present invention.

  Step 401) The additional node arrangement determining unit 21 acquires graph data from the storage device 14.

  Step 402) The connection edge information of the node to be added is extracted from the graph data.

  Step 403) Arbitrarily select one newly added node.

  Step 404) It is determined whether the selected newly added node has an edge connection. If there is an edge connection, the process proceeds to Step 406, and if not, the process proceeds to Step 405.

  Step 405) If there is no edge connection, the coordinates of the newly added node are randomly placed in the drawing area on the memory in the added node placement determining unit 21 using a random number, and the process proceeds to Step 411.

  Step 406) If there is an edge connection, it is determined whether there is an existing placement node at the edge connection destination. If there is an edge connection, the process proceeds to step 408, and if not, the process proceeds to step 407.

  Step 407) If the edge connection destinations of all the remaining new nodes are new nodes, the process proceeds to Step 405. Otherwise, the process proceeds to Step 403.

  Step 408) It is determined whether there is one existing arrangement node of the edge connection destination. If there is one, the process proceeds to Step 410, and if not, the process proceeds to Step 409.

  Step 409) When there are a plurality of existing arrangement nodes of the edge connection destination, the coordinates of the newly added node are arranged at the center of gravity of the existing arrangement node group of the connection destination, and the process proceeds to Step 411.

  Step 410) When there is one existing arrangement node at the connection destination of the edge, the node is arranged in the vicinity of the existing arrangement node at the connection destination, and the process proceeds to Step 411.

  Step 411) If additional nodes still remain in the connection edge information, the process proceeds to Step 403, and if not, the process ends.

  Hereinafter, four patterns for arranging nodes in the processing shown in the flowchart of FIG. 4 will be described.

<Node addition processing (1)>
The additional node arrangement determining unit 21 arranges the added node at the center of gravity with respect to the existing arrangement node having the connection relation based on the additional edge (step 409). For example, as shown in FIG. 5, when adding the nodes and edges shown in (b) and (c) to the existing placement node in (a), the 9th node becomes the center of gravity of 5th and 8th. The 10th node is placed at the center of gravity of Nos. 1, 5 and 4, and the 11th node is placed at the center of gravity of Nos. 2 and 4. The node placement coordinate optimization update processing unit 23 performs placement optimization calculation according to a predetermined dynamic model based on the additionally placed coordinates of (d), and obtains the placement of (e).

<Node addition processing (2)>
When the added node is in a connection relationship with a node that is already arranged and is also in a connection relationship with the additional node (step 409), the additional node arrangement determination unit 21 is in a connection relationship with the existing arrangement node. By adding the nodes first and adding the nodes sequentially, the additional nodes are arranged at the center of gravity of the existing arrangement nodes. For example, as shown in FIG. 6, when adding the nodes and edges shown in (b) and (c) to the existing placement node in (a), first, the 5th and 8th connecting the 9th node. It arrange | positions like the (d) to the gravity center of a number. Next, the 10th node is arranged at the center of gravity of the 9th, 5th and 4th as shown in (f). Next, the 11th node is arranged at the center of gravity of the 10th and 2nd as shown in (h). The node arrangement coordinate optimization update processing unit 23 performs optimization calculation according to a predetermined dynamic model based on the arrangement of (h) to obtain the optimum arrangement of (i).

<Node addition processing (3)>
When the number of nodes to be added is one existing placement node that is in a connection relationship, the additional node placement determination unit 21 places in the vicinity of the existing placement node instead of the center of gravity (step 410). For example, as shown in FIG. 7, when adding the nodes and edges shown in (b) and (c) to the arranged nodes in (a), the 9th node is placed in the vicinity of the 5th and the 10th. The node is arranged in the vicinity of No. 1 and the node 11 is arranged in the vicinity of No. 4. The node arrangement coordinate optimization update processing unit 23 performs optimization calculation according to a predetermined dynamic model based on the additionally arranged coordinates (d), and obtains the optimum arrangement (e).

<Node addition processing (4)>
Those having no connection relationship with nodes that have already been arranged are arranged at an arbitrary location on the display space (step 405).

  Next, the process of the above embodiment will be specifically described.

  FIG. 8 is an example of co-occurrence graph visualization using person data according to an embodiment of the present invention. The data used was a person list collected from Wikipedia (registered trademark), the co-occurrence degree was calculated based on the frequency of appearance in Wikipedia (registered trademark) articles, and graph data was created based on the co-occurrence degree Is. FIG. 8A shows a state in which optimal placement is performed according to a predetermined dynamic model based on the co-occurrence data of a person alive in 160 years. In FIG. 6B, the coordinate arrangement of the person who was alive in 161 was performed, and it can be seen that “Liu Bei” was newly added compared to the data of 160 in FIG. At this time, “Liu Bei” had a high degree of co-occurrence with 4 people such as “Cao Cao” who had already been placed, and was connected to the center of gravity of the existing placement coordinates of the 4 people. Based on the arrangement coordinates of (b), the optimum arrangement calculation is again performed using a predetermined dynamic model, and the resulting arrangement is (c). Sample data used for realizing the graph visualization display are shown in FIGS.

<Comparison between the prior art and the present invention>
In order to consider the effect of the present invention, verification was performed using the above-described person list data of Wikipedia (registered trademark). As the quantitative evaluation, calculation was optimized using a predetermined dynamic model, and evaluation was performed based on the average and variance of the edge length of the graph data.

  First, using the data for 1970, optimal placement calculation is performed using a predetermined dynamic model until the placement calculation sufficiently converges, and the 1970 placement coordinates are obtained. Comparison between the case where 1971 data was added based on the acquired 1970 coordinates, and the additional arrangement was initialized using the method of the present invention, and the case where the additional arrangement was initialized using a random number Went. FIG. 11 shows the result. (A) and (b) of the figure are average values of edge lengths in the conventional method and the present invention, and it can be seen that the method of the present invention converges earlier than the conventional method. In addition, the reason why the conventional method in FIG. 6A is nearly twice as large as the method of the present invention as an initial value is that a very long edge occurs.

  On the other hand, in the method of the present invention of (b), since the generation of long edges can be suppressed, the average value can be kept low from the beginning. The closer the variance value is to 0, the better. However, it is impossible to take a value of 0 because complex network data is physically impossible to embed completely in 2 dimensions due to the problem of dimensional compression. However, the calculation is performed so that the value is as small as possible.

  FIGS. 7C and 7D show the edge length variance values of the conventional method and the present invention, and it can be seen that the method of the present invention converges earlier than the conventional method as with the average value. In addition, the reason why the conventional method (c) is overwhelmingly larger than the method of the present invention as the initial value is that a very long edge occurs as described above. From the results shown in FIG. 11, it can be seen that the conventional method performs an iterative calculation about 4000 times until convergence, whereas the method of the present invention does not reach 1000 times and almost converges in about 100 times. I understand that.

  FIG. 12 shows the result of the layout calculation of the above-mentioned Wikipedia (registered trademark) data using data from 132 to 2010. In each age, 100 iterations were performed using a predetermined dynamic model under the same conditions. (A) and (b) are the average values of the edge lengths of the conventional method and the method of the present invention, and the conventional method can no longer converge as the number of nodes increases, whereas in the method of the present invention, 100 times. It can be seen that the calculation is progressing while maintaining accuracy with a degree of iterative calculation. The figure in FIG. 12 is an enlargement of the year 1900 to 2010 in FIG. It can be seen that the method of the present invention can withstand a sudden increase in the number of nodes (in this case, about 100 people increase in each age).

As mentioned above, when adding a node on the display space, depending on the connection relationship of the graph data,
1) Place it at the center of gravity of the nodes already placed;
2) If there is only one connection relationship with a node that has already been placed, place it near the node in the connection relationship;
3) If there is no connection with a node that has already been placed, place it at any location on the display space;
One of the above is performed sequentially. Then, a predetermined dynamic model is applied between the added node and a node already arranged on the display space to correct the position of each node.

  This makes it possible to perform processing at higher speed and with higher accuracy when visualizing data in which nodes and edges are sequentially added or deleted.

  Further, the present invention constructs the operation of the processing device 11 shown in FIG. 2 in the above embodiment as a program, and installs and executes it on a computer used as a graph visualization display device, or distributes it via a network. It is possible to make it.

  The present invention is not limited to the above-described embodiments and examples, and various modifications and applications are possible within the scope of the claims.

10 Graph visualization display device 11 Processing device (CPU)
12 main memory 13 display device 21 additional node arrangement determination unit 22 deletion node processing unit 23 node arrangement coordinate optimization update processing unit

Claims (9)

A graph visualization display device for visualizing graph data composed of a plurality of nodes and an edge connecting between the nodes,
Processing means for generating a graph visualization image based on graph data expressing a relationship between a plurality of nodes and the nodes as edges;
Display means for displaying the graph visualization image generated in the processing means,
The processing means includes
Wherein when on the display space displayed on the display unit to add a node is a connection relationship between additional nodes that will be added, the additional node to the center of gravity of the existing arrangement node group that have already been arranged after placing the, correct the position of each node according to Jo Tokoro dynamics model,
When adding a plurality of additional nodes, the arrangement is made before any additional nodes that are connected to any of the existing arrangement nodes, rather than the additional nodes that are connected to only one of the plurality of additional nodes. ,
A graph visualization display device characterized by that. The processing means includes
When placing the additional node to the center of gravity of the existing arrangement node group, if the node with the same connection information exists, to add the additional node staggered arrangement minutely using a random number <br / The graph visualization display device according to claim 1. The processing means includes
Wherein if additional nodes is only one connection relationship is between the existing arrangement node graph visualization of the you place additional nodes <br/> claim 1, wherein in the vicinity of the existing arrangement nodes in a connected relationship Display device. The processing means includes
Before Symbol existing arrangement node and said additional node connection relationship is not of any you placed where <br/> claim 1 graph visualization device according on the display space. A graph visualization display method for visualizing graph data composed of a plurality of nodes and an edge connecting the nodes,
Processing means for generating a graph visualization image based on graph data expressing a relationship between a plurality of nodes and the nodes as edges;
In a device comprising: display means for displaying the graph visualization image generated in the processing means;
The processing means is
Wherein when on the display space displayed on the display unit to add a node is a connection relationship between additional nodes that will be added, the additional node to the center of gravity of the existing arrangement node group that have already been arranged a placement step of placing a
After the placement step, a correction step for correcting the position of each node according to Jo Tokoro dynamics model,
The stomach line,
In the step of arranging, when adding a plurality of additional nodes, an additional node connected to any of the existing arranged nodes rather than an additional node connected to only one of the plurality of additional nodes To place first,
A graph visualization display method characterized by that. In the placing step,
When placing the additional node to the center of gravity of the existing arrangement node group, if the node with the same connection information exists, according to claim 5, wherein adding the additional node staggered arrangement minutely using a random number Graph visualization display method. In the placing step,
The graph visualization display method according to claim 5 , wherein when the additional node has only one connection relationship with the existing arrangement node, the additional node is arranged in the vicinity of the existing arrangement node in the connection relation. In the placing step,
It said additional node is not connected to the relationship between the pre-Symbol existing placement node, graphical visualization method of claim 5 wherein the located anywhere on the display space. Computer
The graph visualization display program for functioning as each means of the graph visualization display apparatus of any one of Claims 1 thru | or 4 .

Images