PROBABILISTIC LINK STRENGTH REDUCTION

• US 20110016114A1
• Filed: 07/17/2009
• Published: 01/20/2011
• Est. Priority Date: 07/17/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: ALLEN, THOMAS BRADLEY, Macy, Brian Eugene
• Granted Patent: US 10,108,616 B2
• Time in Patent Office: Days
• US Class Current: 707/726
• CPC Class Codes: G06F 16/94 Hypermedia Hyperlinking G06F40/134

Abstract

Systems, methods and articles of manufacture are disclosed for resolving relationships in a relationship graph of identities. A strength of at least one link from a node of the relationship graph may be reduced, based on at least a count of the links from the node. Further, the reduction may be based on one or more predefined threshold counts. The node having a reduced link strength may be evaluated to identify whether a relationship between the node and a specified node meets predefined criteria for a relationship of interest. A user may be alerted of any identified relationship.

Claims

1. A computer-implemented method for evaluating a relationship graph of identities for relationship resolution, comprising configuring one or more computer processors to perform an operation comprising:

counting a number of links from a node of the relationship graph of identities for identity resolution, up to a first predefined threshold;

reducing, for each additional link exceeding the first predefined threshold and not exceeding a second predefined threshold, the strength of at least one link from the node to generate a pruned relationship graph; and

traversing the pruned relationship graph to identify a relationship between two nodes of the relationship graph that meets predefined criteria for relationships.

2. The computer-implemented method of claim 1, wherein the strength of the at least one link is reduced in proportion to an extent by which the count of links exceeds the first predefined threshold.

3. The computer-implemented method of claim 2, wherein the proportion is linear.

4. The computer-implemented method of claim 1, wherein the number of links from the node is equal to the second predefined threshold, and wherein the strength of the at least one link is reduced to nil.

5. The computer-implemented method of claim 1, wherein the first predefined threshold is selected from at least a threshold count of links and a threshold standard deviation of link counts of nodes of the relationship graph.

6. The computer-implemented method of claim 1, wherein the predefined criteria for relationships comprises links between any two nodes of the pruned relationship graph that satisfy a minimum link strength.

7. The computer-implemented method of claim 6, wherein the a link strength of two nodes having greater than one degree of separation in the pruned relationship graph is determined from a strength of each link between the two nodes in the pruned relationship graph.

8. The computer-implemented method of claim 1, wherein the operation further comprises:

alerting a user of the identified relationship.

9. A computer readable storage medium containing a program, which, when executed on a processor, performs an operation for evaluating a relationship graph of identities for relationship resolution, the operation comprising:

counting a number of links from a node of the relationship graph of identities for identity resolution, up to a first predefined threshold;

reducing, for each additional link exceeding the first predefined threshold and not exceeding a second predefined threshold, the strength of at least one link from the node to generate a pruned relationship graph; and

traversing the pruned relationship graph to identify a relationship between two nodes of the relationship graph that meets predefined criteria for relationships.

10. The computer program product of claim 9, wherein the strength of the at least one link is reduced in proportion to an extent by which the count of links exceeds the first predefined threshold.

11. The computer program product of claim 10, wherein the proportion is linear.

12. The computer program product of claim 9, wherein the number of links from the node is equal to the second predefined threshold, and wherein the strength of the at least one link is reduced to nil.

13. The computer program product of claim 9, wherein the first predefined threshold is selected from at least a threshold count of links and a threshold standard deviation of link counts of nodes of the relationship graph.

14. The computer program product of claim 9, wherein the predefined criteria for relationships comprises links between any two nodes of the pruned relationship graph that satisfy a minimum link strength.

15. The computer program product of claim 14, wherein the a link strength of two nodes having greater than one degree of separation in the pruned relationship graph is determined from a strength of each link between the two nodes in the pruned relationship graph.

16. The computer program product of claim 9, wherein the computer usable program code is further configured for:

alerting a user of the identified relationship.

17. A system, comprising:

a computer processor; and

a memory containing a program, which when executed by the processor is configured to perform an operation for evaluating a relationship graph of identities for relationship resolution, the operation comprising;

counting a number of links from a node of the relationship graph of identifies for identity resolution, up to a first predefined threshold;

reducing, for each additional link exceeding the first predefined threshold and not exceeding a second predefined threshold, the strength of at least one link from the node to generate a pruned relationship graph; and

traversing the pruned relationship graph to identify a relationship between two nodes of the relationship graph that meets predefined criteria for relationships.

18. The system of claim 17, wherein the strength of the at least one link is reduced in proportion to an extent by which the count of links exceeds the first predefined threshold.

19. The system of claim 18, wherein the proportion is linear.

20. The system of claim 17, wherein the number of links from the node is equal to the second predefined threshold, and wherein the strength of the at least one link is reduced to nil.

21. The system of claim 17, wherein the first predefined threshold is selected from at least a threshold count of links and a threshold standard deviation of link counts of nodes of the relationship graph.

22. The system of claim 17, wherein the predefined criteria for relationships comprises links between any two nodes of the pruned relationship graph that satisfy a minimum link strength.

23. The system of claim 22, wherein the a link strength of two nodes having greater than one degree of separation in the pruned relationship graph is determined from a strength of each link between the two nodes in the pruned relationship graph.

24. The system of claim 17, wherein the operation further comprises:

alerting a user of the identified relationship.

25. A computer-implemented method for pruning a relationship graph of identities for relationship resolution, comprising configuring one or more computer processors to perform an operation comprising:

reducing the strength of at least one link from a node of the relationship graph of identities for identity resolution, based on at least a count of the links from the node.