Method for processing graphs and information processing apparatus

Patent metadata

Field	Value
Publication number	US-10186060-B2
Application number	US-201615356935-A
Country	US
Kind code	B2
Filing date	Nov 21, 2016
Priority date	Nov 26, 2015
Publication date	Jan 22, 2019
Grant date	Jan 22, 2019

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.

First claim

What is claimed is:

1. A non-transitory computer-readable storage medium storing a graph processing program that causes a computer to execute a process comprising:
collecting logs from servers and forming the collected logs into a plurality of source graphs;
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 ordering numbers of two nodes in a subgraph to reorder nodes within the subgraph or swapping one node in the subgraph with a neighboring node that is outside the subgraph and connected to one of the nodes in the subgraph, such that a similarity between the reference matrix and a submatrix representing node-to-node connections in the subgraph becomes larger.

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 processing program that causes a computer to to execute a process comprising:
collecting logs from servers and forming the collected logs into a plurality of source graphs;
generating stochastic matrixes respectively corresponding to the 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;
selecting the plurality of source graphs one by one as a third graph, calculating a similarity matrix that represents similarity between the reference matric and a second expected value matrix corresponding to the selected third graph, and revising the probabilities indicated in a stochastic matrix corresponding to the selected third graph, based on the calculated similarity matrix.

7. A graph processing method comprising:
collecting logs from servers and forming the collected logs into a plurality of source graphs;
extracting, by a processor, a plurality of subgraphs from the 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 ordering numbers of two nodes in a subgraph to reorder nodes within the subgraph or swapping one node in the subgraph with a neighboring node that is outside the subgraph and connected to one of the nodes in the subgraph, such that a similarity between the reference matrix and a representing node-to-node connections in the subgraph becomes larger.

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 execute a

Assignees

• Fujitsu Ltd

Inventors

• Maruhashi Koji

Classifications

• G06T11/26 Primary

  Drawing of charts or graphs · CPC title

• G06N7/01 Primary

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06F21/00

  Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity · CPC title

• H04L63/1408

  by monitoring network traffic (monitoring network traffic per se H04L43/00) · CPC title

• G06N7/005

  Physics · mapped topic