Patent ID: 8831271

Claim:
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.