METHOD FOR PROCESSING GRAPHS AND INFORMATION PROCESSING APPARATUS
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
8 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. - View Dependent Claims (2, 3, 4, 5)
-
-
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.
-
Specification