METHOD FOR PROCESSING GRAPHS AND INFORMATION PROCESSING APPARATUS

• US 20170154445A1
• Filed: 11/21/2016
• Published: 06/01/2017
• Est. Priority Date: 11/26/2015
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: MARUHASHI, Koji
• Granted Patent: US 10,186,060 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 21/00 Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00

Abstract

A computer generates connection matrixes corresponding to subgraphs extracted from source graphs. The connection matrixes include a plurality of elements each describing a connection between nodes in a corresponding subgraph or between a node in the corresponding subgraph and a neighboring node connected to one of the nodes in the corresponding subgraph. Based on the connection matrixes, the computer then generates a reference matrix that indicates a characteristic pattern of connections of nodes in the subgraphs, taking into consideration an order in which these nodes are arranged. The computer further performs a node-ordering swap operation on individual subgraphs, such that a submatrix representing node-to-node connections in a subgraph will be more similar to the reference matrix. The node-ordering swap operation includes changing the order of two nodes in a subgraph or swapping one node in a subgraph with a neighboring node connected to that subgraph.

Claims

1. A non-transitory computer-readable storage medium storing a graph program that causes a computer to perform a procedure comprising:

extracting a plurality of subgraphs from a plurality of source graphs, each of the plurality of subgraphs including a specific number of nodes;

first generating a plurality of connection matrixes for the plurality of subgraphs, respectively, each of the plurality of connection matrixes including connection information of a first plurality of nodes in a corresponding subgraph, each of the first plurality of nodes having an ordering number, the connection information including connection relationships among the first plurality of nodes and connection relationships between the first plurality of nodes and a plurality of neighboring nodes, the plurality of neighboring nodes being connected to at least one of the first plurality of nodes;

second generating a reference matrix from the plurality of connection matrixes, the reference matrix including connection pattern characteristic information of the plurality of subgraphs, the connection pattern characteristic information including connection pattern characteristics of nodes with a same ordering number in the plurality of subgraphs; and

performing a node-ordering swap operation respectively for the each of the plurality of subgraphs, the node-ordering swap operation including swapping order numbers of two nodes in a subgraph or swapping one node in the subgraph with a neighboring node such that a similarity of the reference matrix and a submatrix become larger, the submatrix representing node-to-node connections in the subgraph.

2. The non-transitory computer-readable storage medium according to claim 1, wherein the procedure further comprises:

executing, after the plurality of subgraphs are revised by the node-ordering swap operation, another round of the first generating, the second generating, and the performing of a node-ordering swap operation, with respect to the revised subgraphs.

3. The non-transitory computer-readable storage medium according to claim 2, wherein the procedure further comprises:

outputting a latest version of the reference matrix when the node-ordering swap operation is unable to obtain a node-ordering swap solution that makes the subgraph more similar to the reference matrix.

4. The non-transitory computer-readable storage medium according to claim 3, wherein the procedure further comprises:

receiving a new source graph after the latest version of the reference matrix is outputted;

extracting a new subgraph from the received new source graph; and

performing a node-ordering swap operation on the extracted new subgraph, using the latest version of the reference matrix that has been outputted.

5. The non-transitory computer-readable storage medium according to claim 1, wherein the second generating evaluates average node-to-node connections in the plurality of subgraphs by calculating how many of nodes placed in a first node position in the subgraphs are connected to nodes placed in a second node position in the plurality of subgraphs.

6. A non-transitory computer-readable storage medium storing a graph program that causes a computer to perform a procedure comprising:

generating stochastic matrixes respectively corresponding to a plurality of source graphs, each of the stochastic matrixes describing probabilities that individual nodes in a source graph are selected when generating a subgraph by sequentially selecting a specific number of nodes;

selecting the plurality of source graphs one by one as a first graph, and generating a first expected value matrix that includes first expected values, assuming that the specific number of nodes are sequentially selected from the selected first graph with the probabilities indicated in a stochastic matrix corresponding to the selected first graph, the first expected values representing expected presence of connections between each node in the selected first graph and the specific number of nodes that are sequentially selected from the selected first graph;

selecting the plurality of source graphs one by one as a second graph, and generating a second expected value matrix that includes second expected values, assuming that a subgraph is formed by sequentially selecting the specific number of nodes from the selected second graph with the probabilities indicated in a stochastic matrix corresponding to the selected second graph, the second expected values each representing expected presence of a connection between nodes that are selected from the selected second graph;

generating a reference matrix from the second expected value matrixes respectively corresponding to the plurality of source graphs, the reference matrix including connection pattern characteristic information of a plurality of subgraphs respectively extracted from the plurality of source graphs, the connection pattern characteristic information including connection pattern characteristics of nodes with a same ordering number in the plurality of subgraphs; and

selecting the plurality of source graphs one by one as a third graph, and revising the probabilities indicated in a stochastic matrix corresponding to the selected third graph, such that a first expected value matrix corresponding to the selected third graph be more similar to the reference matrix.

7. A graph processing method comprising:

extracting, by a processor, a plurality of subgraphs from a plurality of source graphs, each of the plurality of subgraphs including a specific number of nodes;

first generating, by the processor, a plurality of connection matrixes for the plurality of subgraphs, respectively, each of the plurality of connection matrixes including connection information of a first plurality of nodes in a corresponding subgraph, each of the first plurality of nodes having an ordering number, the connection information including connection relationships among the first plurality of nodes and connection relationships between the first plurality of nodes and a plurality of neighboring nodes, the plurality of neighboring nodes being connected to at least one of the first plurality of nodes;

second generating, by the processor, a reference matrix from the plurality of connection matrixes, the reference matrix including connection pattern characteristic information of the plurality of subgraphs, the connection pattern characteristic information including connection pattern characteristics of nodes with a same ordering number in the plurality of subgraphs; and

performing, by the processor, a node-ordering swap operation respectively for the each of the plurality of subgraphs, the node-ordering swap operation including swapping order numbers of two nodes in a subgraph or swapping one node in the subgraph with a neighboring node such that a similarity of the reference matrix and a submatrix become larger, the submatrix representing node-to-node connections in the subgraph.

8. An information processing apparatus comprising:

a memory configured to store a plurality of source graphs; and

a processor coupled to the memory, the processor being configured to perform a procedure including;

extracting a plurality of subgraphs from the plurality of source graphs, each of the plurality of subgraphs including a specific number of nodes,

first generating a plurality of connection matrixes for the plurality of subgraphs, respectively, each of the plurality of connection matrixes including connection information of a first plurality of nodes in a corresponding subgraph, each of the first plurality of nodes having an ordering number, the connection information including connection relationships among the first plurality of nodes and connection relationships between the first plurality of nodes and a plurality of neighboring nodes, the plurality of neighboring nodes being connected to at least one of the first plurality of nodes,

second generating a reference matrix from the plurality of connection matrixes, the reference matrix including connection pattern characteristic information of the plurality of subgraphs, the connection pattern characteristic information including connection pattern characteristics of nodes with a same ordering number in the plurality of subgraphs, and

performing a node-ordering swap operation respectively for the each of the plurality of subgraphs, the node-ordering swap operation including swapping order numbers of two nodes in a subgraph or swapping one node in the subgraph with a neighboring node such that a similarity of the reference matrix and a submatrix become larger, the submatrix representing node-to-node connections in the subgraph.