Subgraph detection device, subgraph detection method, program, data structure of data, and information recording medium

摘要

To provide a detection device capable of, e.g., obtaining a list of genes whose expressions are commonly changed in response to administration of a specific drug or drugs, based on consideration of relationship (e.g., interacting relationship among genes) among genes, a list of proteins whose expressions are commonly changed in response to administration of a specific drug or drugs, based on consideration of relationship (e.g., interacting relationship among proteins) among proteins, and a list of users who purchased an identical product or products, based on consideration of relationship (e.g., friendship) among users, and so forth. A graph data obtaining unit (20) obtains graph data indicating a graph including a plurality of vertexes. A vertex data obtaining unit (22) obtains vertex data that correlates an information item to a vertex. Based on the graph data and the vertex data, a subgraph detection unit (24) detects a subgraph that is a subgraph of the graph in which information items correlated to the respective vertexes in the subgraph have predetermined relationship.

主权项

1. A subgraph detection device, comprising:
graph data obtaining means for obtaining graph data indicating a graph including a plurality of vertexes and one or more edges; vertex data obtaining means for obtaining vertex data that correlates an element set including at least one kind of element to the vertex; and subgraph detection means for carrying out detection, based on the graph data and the vertex data, of a subgraph being a subgraph of the graph in which a product set of the element sets correlated to the respective vertexes in the subgraph includes an N (N>=1) or larger number of kinds of elements, wherein the subgraph detection means includes:
determination means, while making respective nodes of a search tree as a determination target in a search order according to a depth or width-first search algorithm, in which the nodes each have a set of vertexes in the graph, and the search tree has a vertex set obtained by adding, as a new end vertex, one vertex adjacent to an end vertex in a vertex set of a parent node to the vertex set as a child node of the parent node, for carrying out determination, when a vertex set of a node being the determination target includes a plurality of vertexes, to see whether or not a product set of element sets correlated to the respective vertexes in the vertex set includes the N or larger number of kinds of elements, and means for carrying out the detection, based on a result of determination by the determination means, and when a product set of element sets correlated to respective vertexes in a vertex set of a first node in the search tree is included in a product set of element sets correlated to respective vertexes in a vertex set of a second node that is a node having a vertex set including an end vertex that is same as an end vertex in the vertex set of the first node and that is a node having a vertex set including the vertex set of the first node, the determination means does not carry out the determination with respect to a vertex set of a descendant node of the first node as the determination target.