Back to results
US 11,531,656 B1Granted
Duplicate determination in a graph
AssigneeInternational Business Machines Corporation
InventorsLars Bremer, Thuany Karoline Stuart, Hemanth Kumar Babu, Martin Oberhofer
Life of this patent
Estimating the term…
Abstract
Embodiments of the present invention provide for a method for duplicate determination in a graph. The graph comprises nodes representing entities and edges representing relationships between the entities. Embodiments of the present invention identify two target nodes in the graph. A neighborhood subgraph may be determined for each of the two nodes. The neighborhood subgraph includes the respective node. Embodiments of the present invention can then determine whether the two nodes are duplicates with respect to each other, based on a result of a comparison between the two subgraphs and based on a comparison of the two target nodes of the subgraphs.
Claims17
A computer implemented method comprising:
- duplicating determination in a graph that comprises nodes representing entities and edges representing relationships between the entities, wherein duplicating determination in the graph comprises:
- identifying at least two target nodes in the graph;
- determining a neighborhood subgraph for each of the two target nodes, the neighborhood subgraph including a respective target node;
- and
- determining whether the two target nodes are duplicates with respect to each other based on comparisons between two neighborhood subgraphs of the two target nodes, comparisons between two subgraphs, and comparisons between candidate nodes, wherein determining whether the two target nodes are duplicates comprise:
- generating a first score indicative of a difference between two neighborhood subgraphs by comparing the two neighborhood subgraphs of the two target nodes;
- generating a second score indicative of a similarity between the two target nodes using probabilistic matching;
- generating a third score indicative of a similarity between at least one pair of candidate nodes;
- and
- determining whether the two target nodes are duplicates based on a combination of the first score and the second score and the third score.
7 more elements
A computer program product comprising:
- one or more computer readable storage media and program instructions stored on the one or more computer readable storage media, the program instructions comprising:
- program instructions to duplicate determination in a graph that comprises nodes representing entities and edges representing relationships between the entities, wherein the program instructions to duplicate determination in the graph comprises:
- program instructions to identify at least two target nodes in the graph;
- program instructions to determine a neighborhood subgraph for each of the two target nodes, the neighborhood subgraph including a respective target node;
- and
- program instructions to determine whether the two target nodes are duplicates with respect to each other based on comparisons between two neighborhood subgraphs of the two target nodes, comparisons between two subgraphs, and comparisons between candidate nodes, wherein determining whether the two target nodes are duplicates comprise:
- program instructions to generate a first score indicative of a difference between two neighborhood subgraphs by comparing the two neighborhood subgraphs of the two target nodes;
- program instructions to generate a second score indicative of a similarity between the two target nodes using probabilistic matching;
- program instructions to generate a third score indicative of a similarity between at least one pair of candidate nodes;
- and
- program instructions to determine whether the two target nodes are duplicates based on a combination of the first score and the second score and the third score.
8 more elements
A computer system comprising:
- one or more computer processors;
- one or more computer readable storage media;
- and
- program instructions stored on the one or more computer readable storage media for execution by at least one of the one or more computer processors, the program instructions comprising:
- program instructions to duplicate determination in a graph that comprises nodes representing entities and edges representing relationships between the entities, wherein the program instructions to duplicate determination in the graph comprises:
- program instructions to identify at least two target nodes in the graph;
- program instructions to determine a neighborhood subgraph for each of the two target nodes, the neighborhood subgraph including a respective target node;
- and
- program instructions to determine whether the two target nodes are duplicates with respect to each other based on comparisons between two neighborhood subgraphs of the two target nodes, comparisons between two subgraphs, and comparisons between candidate nodes, wherein determining whether the two target nodes are duplicates comprise:
- program instructions to generate a first score indicative of a difference between two neighborhood subgraphs by comparing the two neighborhood subgraphs of the two target nodes;
- program instructions to generate a second score indicative of a similarity between the two target nodes using probabilistic matching;
- program instructions to generate a third score indicative of a similarity between at least one pair of candidate nodes;
- and
- program instructions to determine whether the two target nodes are duplicates based on a combination of the first score and the second score and the third score.
11 more elements
Dependencies are inferred from the claim text.