| 摘要 |
<p>[Problem] To figure out a degree of similarity between graphs for an SNS, links in the WWW or the like in a reasonable computation time, the graphs having extremely large numbers of nodes. [Solving Means] Nodes of each of graphs are given values unique to labels of the nodes. These values are fixed-length bit strings, preferably. A length of each of the bit strings is selected so as to be a number sufficiently larger than the number of digits that is enough to express kinds of labels. The nodes of each of the graphs are sequentially visited by use of an existing graph search technique such as depth-first order search, breath-first order search or the like. In the visiting, when staying at one node, a system of this invention calculates bit-string values by performing calculations on bit-string label values of all of nodes adjacent to the one node, and on a bit-string label value of the one node. The system of this invention performs a hash calculation using the thus calculated bit-string values and the bit-string label value originally held by the one node, thereby calculating another bit-string label value and setting this bit-string label value as a new label value of the one node. Thus, when the system finishes visiting all of the nodes in one of the graphs, label values of all of the nodes finish being rewritten. When the system finishes performing the same processing on the other one of the graphs to be compared for graph similarity, label values of all of the nodes finish being rewritten in the other graph. Then, the degree of similarity can be figured out by calculating a percentage of the number of nodes, which have label values agreeing with label values of nodes in the other graph, to all of the nodes in the one graph.</p> |
