Probabilistic link strength reduction

• US 10,108,616 B2
• Filed: 07/17/2009
• Issued: 10/23/2018
• 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
• Primary Examiner(s): Yen, Syling
• Assistant Examiner(s): Tran, Bao
• Application Number:
  US12/505,348
• Publication Number:
  US 20110016114A1
• Time in Patent Office: 3,385 Days
• Field of Search: 707726, 707780, 707999005, 707797, 707798, 370252, 370255, 370324
• CPC Class Codes: G06F 16/94 Hypermedia Hyperlinking G06F40/134

Abstract

Techniques 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 to identify and exclude false-positive interpersonal relationships from evaluation in an entity resolution system, based on interpersonal relationship totals of individuals, the computer-implemented method comprising:

receiving, from a requesting entity, a request to identify interpersonal relationships satisfying a set of relationship criteria pertaining to a first individual represented in the entity resolution system, each interpersonal relationship comprising a relationship between a respective pair of individuals, wherein the set of relationship criteria is specified in the request;

determining an interpersonal relationship total of a second individual represented in the entity resolution system, the second individual having a plurality of interpersonal relationships, each of which has an associated interpersonal relationship strength, and of which a first interpersonal relationship satisfies a threshold strength for evaluation, the interpersonal relationship total comprising a numerical measure;

determining that the interpersonal relationship strength of each interpersonal relationship of the second individual is overestimated, by determining that the interpersonal relationship total of the second individual exceeds a threshold total for reduction;

upon determining that the interpersonal relationship strength of each interpersonal relationship of the second individual is overestimated, correcting the overestimated interpersonal relationship strength by reducing the interpersonal relationship strength by operation of one or more computer processors and based on a measure by which the interpersonal relationship total of the second individual exceeds the threshold total for reduction, wherein the interpersonal relationship strength of the first interpersonal relationship is reduced below the threshold strength for evaluation, thereby designating the first interpersonal relationship as a false-positive relationship;

identifying one or more interpersonal relationships satisfying the set of relationship criteria, by evaluating, in the entity resolution system, only interpersonal relationships having up to a specified degree of separation from the first individual and to the exclusion of both false-positive relationships and relationships beyond the false-positive relationships, thereby avoiding a processing cost incurred in evaluating the false-positive relationships and the relationships beyond the false-positive relationships; and

outputting the identified one or more interpersonal relationships responsive to the request.

2. The computer-implemented method of claim 1, wherein the interpersonal relationship strength of each interpersonal relationship of the second individual is reduced in proportion to an extent by which the interpersonal relationship total of the second individual exceeds the threshold total for reduction.

3. The computer-implemented method of claim 2, wherein the threshold total for reduction comprises a first threshold total for reduction, wherein the interpersonal relationship total of at least one individual is equal to a second threshold total for reduction, wherein the interpersonal relationship strength of each interpersonal relationship of the at least one individual is reduced to nil.

4. The computer-implemented method of claim 3, wherein the threshold total for reduction is selected from at least a threshold interpersonal relationship total and a threshold standard deviation of interpersonal relationship totals of individuals represented in the entity resolution system.

5. The computer-implemented method of claim 4, wherein the set of relationship criteria comprises interpersonal relationships having up to the specified degree of separation from the first individual and satisfying a minimum interpersonal relationship strength for querying.

6. The computer-implemented method of claim 5, wherein an interpersonal relationship strength of two individuals having greater than one degree of separation is determined based on an interpersonal relationship strength of each interpersonal relationship in a sequence of interpersonal relationships that is between the two individuals in the entity resolution system.

7. A non-transitory computer program product to identify and exclude false-positive interpersonal relationships from evaluation in an entity resolution system, based on interpersonal relationship totals of individuals, the non-transitory computer program product comprising:

a non-transitory computer-readable medium having computer-readable program code embodied therewith, the computer-readable program code executable by one or more computer processors to;

receive, from a requesting entity, a request to identify interpersonal relationships satisfying a set of relationship criteria pertaining to a first individual represented in the entity resolution system, each interpersonal relationship comprising a relationship between a respective pair of individuals, wherein the set of relationship criteria is specified in the request;

determine an interpersonal relationship total of a second individual represented in the entity resolution system, the second individual having a plurality of interpersonal relationships, each of which has an associated interpersonal relationship strength, and of which a first interpersonal relationship satisfies a threshold strength for evaluation, the interpersonal relationship total comprising a numerical measure;

determining that the interpersonal relationship strength of each interpersonal relationship of the second individual is overestimated, by determining that the interpersonal relationship total of the second individual exceeds a threshold total for reduction;

upon determining that the interpersonal relationship strength of each interpersonal relationship of the second individual is overestimated, correcting the overestimated interpersonal relationship strength by reducing the interpersonal relationship strength by operation of one or more computer processors and based on a measure by which the interpersonal relationship total of the second individual exceeds the threshold total for reduction, wherein the interpersonal relationship strength of the first interpersonal relationship is reduced below the threshold strength for evaluation, thereby designating the first interpersonal relationship as a false-positive relationship;

identifying one or more interpersonal relationships satisfying the set of relationship criteria, by evaluating, in the entity resolution system, only interpersonal relationships having up to a specified degree of separation from the first individual and to the exclusion of both false-positive relationships and relationships beyond the false-positive relationships, thereby avoiding a processing cost incurred in evaluating the false-positive relationships and the relationships beyond the false-positive relationships; and

outputting the identified one or more interpersonal relationships responsive to the request.

8. The computer program product of claim 7, wherein the interpersonal relationship strength of each interpersonal relationship of the second individual is reduced in proportion to an extent by which the interpersonal relationship total of the second individual exceeds the threshold total for reduction.

9. The computer program product of claim 8, wherein the threshold total for reduction comprises a first threshold total for reduction, wherein the interpersonal relationship total of at least one individual is equal to a second threshold total for reduction, wherein the interpersonal relationship strength of each interpersonal relationship of the at least one individual is reduced to nil.

10. The computer program product of claim 9, wherein the threshold total for reduction is selected from at least a threshold interpersonal relationship total and a threshold standard deviation of interpersonal relationship totals of individuals represented in the entity resolution system.

11. The computer program product of claim 10, wherein the set of relationship criteria comprises interpersonal relationships having up to the specified degree of separation from the first individual and satisfying a minimum interpersonal relationship strength for querying.

12. The computer program product of claim 11, wherein an interpersonal relationship strength of two individuals having greater than one degree of separation is determined based on an interpersonal relationship strength of each interpersonal relationship in a sequence of interpersonal relationships that is between the two individuals in the entity resolution system.

13. A system to identify and exclude false-positive interpersonal relationships from evaluation in an entity resolution system, based on interpersonal relationship totals of individuals, the system comprising:

one or more computer processors; and

a memory containing a program, which when executed by the one or more computer processors is configured to perform an operation comprising;

receiving, from a requesting entity, a request to identify interpersonal relationships satisfying a set of relationship criteria pertaining to a first individual represented in the entity resolution system, each interpersonal relationship comprising a relationship between a respective pair of individuals, wherein the set of relationship criteria is specified in the request;

determining an interpersonal relationship total of a second individual represented in the entity resolution system, the second individual having a plurality of interpersonal relationships, each of which has an associated interpersonal relationship strength, and of which a first interpersonal relationship satisfies a threshold strength for evaluation, the interpersonal relationship total comprising a numerical measure;

determining that the interpersonal relationship strength of each interpersonal relationship of the second individual is overestimated, by determining that the interpersonal relationship total of the second individual exceeds a threshold total for reduction;

upon determining that the interpersonal relationship strength of each interpersonal relationship of the second individual is overestimated, correcting the overestimated interpersonal relationship strength by reducing the interpersonal relationship strength by operation of one or more computer processors and based on a measure by which the interpersonal relationship total of the second individual exceeds the threshold total for reduction, wherein the interpersonal relationship strength of the first interpersonal relationship is reduced below the threshold strength for evaluation, thereby designating the first interpersonal relationship as a false-positive relationship;

identifying one or more interpersonal relationships satisfying the set of relationship criteria, by evaluating, in the entity resolution system, only interpersonal relationships having up to a specified degree of separation from the first individual and to the exclusion of both false-positive relationships and relationships beyond the false-positive relationships, thereby avoiding a processing cost incurred in evaluating the false-positive relationships and the relationships beyond the false-positive relationships; and

outputting the identified one or more interpersonal relationships responsive to the request.

14. The system of claim 13, wherein a second of the plurality of interpersonal relationships satisfies the threshold strength for evaluation, wherein the interpersonal relationship strength of the second interpersonal relationship is not reduced below the threshold strength for evaluation, wherein evaluating the interpersonal relationships includes evaluating the first interpersonal relationship to the exclusion of the second interpersonal relationship.

15. The system of claim 14, wherein the interpersonal relationship strength of each interpersonal relationship of the second individual is reduced only upon determining that the interpersonal relationship total of the second individual exceeds the threshold total for reduction, wherein the interpersonal relationship strength of each interpersonal relationship of the second individual is reduced by a predefined function of the measure by which the interpersonal relationship total of the second individual exceeds the threshold total for reduction.

16. The system of claim 15, wherein the interpersonal relationship strength of each interpersonal relationship of the second individual is reduced in proportion to an extent by which the interpersonal relationship total of the second individual exceeds the threshold total for reduction, wherein the threshold total for reduction comprises a first threshold total for reduction, wherein the interpersonal relationship total of at least one individual is equal to a second threshold total for reduction, different from the first threshold total for reduction, wherein the interpersonal relationship strength of each interpersonal relationship of the at least one individual is reduced to nil.

17. The system of claim 16, wherein the threshold total for reduction is selected from at least a threshold interpersonal relationship total and a threshold standard deviation of interpersonal relationship totals of individuals represented in the entity resolution system, wherein the set of relationship criteria comprises interpersonal relationships having up to the specified degree of separation from the first individual and satisfying a minimum interpersonal relationship strength for querying.

18. The system of claim 17, wherein an interpersonal relationship strength of two individuals having greater than one degree of separation is determined based on an interpersonal relationship strength of each interpersonal relationship in a sequence of interpersonal relationships that is between the two individuals in the entity resolution system.

19. The system of claim 18, wherein the requesting entity comprises a user, wherein the proportion is, in respective instances, a linear proportion and a non-linear proportion, wherein the degree of separation is specified in the request, wherein each of the threshold strength for evaluation, the first threshold total for reduction, and the second threshold total for reduction is predefined.

20. The system of claim 19, wherein the interpersonal relationship strength of each interpersonal relationship of the second individual is reduced in order to avoid overstating how strongly the second individual is acquainted with a target individual of the respective interpersonal relationship.

21. The system of claim 20 wherein the identified one or more interpersonal relationships are output to the requesting entity responsive to the request, wherein for each interpersonal relationship of the second individual, a respective relationship strength reduction amount is determined based on the predefined function, wherein the relationship strength reduction amount is different for each interpersonal relationship of the second individual.

22. The system of claim 21, wherein the interpersonal relationship strength of each interpersonal relationship of the second individual is reduced in proportion to an extent by which the interpersonal relationship total of the second individual exceeds the first threshold total for reduction, wherein the interpersonal relationship total of a third individual represented in the entity resolution system is equal to the second threshold total for reduction, wherein the interpersonal relationship strength of each interpersonal relationship of the third individual is reduced to nil.

23. The system of claim 22, wherein the predefined function is configured to refrain from reducing interpersonal relationship strength unless the interpersonal relationship total of the second individual exceeds the first threshold total for reduction, wherein the predefined function is further configured to reduce interpersonal relationship strength to nil upon determining that the interpersonal relationship total of the second individual exceeds the second threshold total for reduction, wherein the second threshold total for reduction is greater in measure than the first threshold total for reduction;

wherein a fourth individual represented in the entity resolution system has a first interpersonal relationship satisfying the threshold strength for evaluation, wherein the interpersonal relationship total of the fourth individual does not exceed the first threshold total for reduction, wherein no interpersonal relationship strength of the fourth individual is reduced.

24. A computer-implemented method to identify and exclude false-positive interpersonal relationships from evaluation in an entity resolution system, based on interpersonal relationship totals of individuals, the computer-implemented method comprising:

receiving a request to identify interpersonal relationships satisfying a set of relationship criteria pertaining to a first individual represented in the entity resolution system, each interpersonal relationship comprising a relationship between a respective pair of individuals, wherein the set of relationship criteria is specified in the request, wherein an interpersonal relationship total of a second individual having a plurality of interpersonal relationships is determined, of which each interpersonal relationship has an associated interpersonal relationship strength, the interpersonal relationship total comprising a numerical measure;

determining that the interpersonal relationship strength of each interpersonal relationship of the second individual is overestimated, by determining that the interpersonal relationship total of the second individual exceeds a threshold total for reduction;

upon determining that the interpersonal relationship strength of each interpersonal relationship of the second individual is overestimated, correcting the overestimated interpersonal relationship strength by reducing the interpersonal relationship strength by operation of one or more computer processors and based on a measure by which the interpersonal relationship total of the second individual exceeds the threshold total for reduction, wherein the interpersonal relationship strength of a first of the plurality of interpersonal relationships is reduced below a threshold strength for evaluation, thereby designating the first interpersonal relationship as a false-positive relationship; and

wherein only interpersonal relationships having up to a specified degree of separation from the first individual, and to the exclusion of both false-positive relationships and relationships beyond the false-positive relationships are evaluated in identifying one or more interpersonal relationships satisfying the set of relationship criteria, thereby avoiding a processing cost incurred in evaluating the false-positive relationships and the relationships beyond the false-positive relationships, wherein the identified one or more interpersonal relationships are output responsive to the request.

25. The computer-implemented method of claim 24, wherein the interpersonal relationship strength of each interpersonal relationship of the second individual is reduced in proportion to an extent by which the interpersonal relationship total of the second individual exceeds the threshold total for reduction.