Intelligent reputation attribution platform

• US 20090076994A1
• Filed: 06/01/2007
• Published: 03/19/2009
• Est. Priority Date: 06/05/2006
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Upperbeyond, Inc.
• Inventors: Ghosh, Rishab Aiyer, Prakash, Vipul Ved
• Granted Patent: US 7,831,536 B2
• Time in Patent Office: Days
• US Class Current: 706/46
• CPC Class Codes: G06N 5/00 Computing arrangements using knowledge-based models

Abstract

Systems and methods allowing for the attribution of reputation to data sources (e.g., for the creation of referrals) are provided. In an illustrative implementation scores (e.g., reputation scores) are determined for a target entity connected a source entity on a network on a given dimension. In the illustrative implementation, an entity may be directly linked to any number of other entities on any number of dimensions, with each link having an associated score. Illustratively, each dimension has an associated transitive dimension. A directed path on a given dimension between two entities, a source and a target, consists of a directed link from the source entity to an intermediate entity, prefixed to a directed path from the intermediate entity to the target entity. In the illustrative implementation, links on the path can travel on the transitive dimension associated with the given dimension.

Claims

1. A system for reputation attribution comprising:

a reputation attribution engine operable to generate reputation scores based one or more characteristics between one or more entities of a given population;

an instruction set having at least one instruction instructing the reputation attribution engine to generate reputation scores within a range R which can be mapped to a value from −

1 to +1 for the entities of an identified population,

wherein the instruction set provides instructions to the reputation attribution engine according to a selected reputation scoring paradigm comprising,

for a population of entities, a target entity connected to a source entity on a network being capable of being represented as a directed graph on a given dimension,

wherein an entity may be directly, uni-directionally linked other entities on other dimensions such that a direct link can have an associated score within the range R,

wherein each dimension can have an associated transitive dimension,

wherein a directed path on a given dimension between two entities can comprise a direct link from a source entity to an intermediate entity, prefixed to a directed path from an intermediate entity to a target entity,

wherein the directed path can be subject to one or more constraints comprising any of a direct link from any entity to the target entity can reside on the given dimension and a direct link on the path from an entity to an intermediate entity that is not the target entity can reside in one or more place comprising the transitive dimension associated with the given dimension and on the given dimension itself if the given dimension is itself is a transitive dimension,

wherein a graph search is performed to identify directed paths from a source entity to a target entity on the given dimension to generate scoring directed graph combining identified directed paths, and

wherein the individual scores on a direct link on the identified directed paths on the scoring directed graph are combined to produce one or more reputation scores having a selected confidence value associated for each resulting score, for the target entity from the perspective of the source entity.

2. The system as recited in claim 1 wherein the graph search and individual score combination can be performed in sequence.

3. The system as recited in claim 1 wherein the graph search and individual score combination can be performed simultaneously.

4. The system as recited in claim 3 wherein a separately stored scoring directed graph is not generated.

5. The system as recited in claim 1 wherein the search graph operation can be optimized by one or more combination of reputation scores generated when combining the individual scores.

6. The system as recited in claim 5 wherein the optimization operation can exclude one or more paths between the source entity and the target entity.

7. The system as recited in claim 1 wherein the reputation attribution engine comprises a computing environment.

8. The system as recited in claim 1 further comprising a communications network operable to communicate data between the reputation attribution engine and one or more cooperating parties.

9. The system as recited in claim 8 wherein the one or more cooperating parties comprise other computing environments.

10. The system as recited in claim 9 wherein the other computing environments comprise a graphical user interface operable of one or more operations comprising any of receiving input data representative of a request for a reputation score operation, displaying generated reputation scores and associated reputation type data, and navigating and/or manipulating the input and/or displayed data.

11. A computer implemented method for attributing reputation scores within a range R and that can be mapped to a value from −

1 to +1, such that for a population of entities within a range R and that can be mapped −

1 . . . +1, for a target entity connected to a source entity on a network represented as a directed graph on a given dimension comprising the acts of;

(a) performing a graph search to identify one or more directed paths from the source entity to the target entity on the given dimension to generate a directed graph having therein a combination of the identified directed paths; and

(b) for the target entity, combining individual scores on a direct link on one or more directed paths on a scoring directed graph to produce one or more final scores.

12. The method as recited in claim 11 further comprising providing an entity so that it is operable to be directly uni-directionally linked to other entities on one or more other dimensions.

13. The method as recited in claim 11 further comprising providing a population space of entities having one or more of the following characteristics comprising any of:

a direct link having an associated score within the range R, a dimension has an associated transitive dimension, and a directed path on a given dimension between two entities can comprise a direct link from a source entity to an intermediate entity prefixed to a directed path from the intermediate entity to the target entity such that the directed path can be constrained so that a direct link from any entity to the target entity can be on the given dimension and so that a direct link on the path from an entity to an intermediate entity can be on the transitive dimension associated with the given dimension or can be on the given dimension itself if the given dimension is itself is a transitive dimension.

14. The method as recited in claim 11 further comprising performing acts (a) and (b) simultaneously.

15. The method as recited in claim 14 further comprising optimizing the generated reputation scores utilizing the final scores.

16. The method as recited in claim 11 further comprising calculating for each path on the scoring directed graph a path score that is the product of all scores on each directed link on the path, and a single final score that is the average of all the path scores, with an associated confidence value of 1.

17. The method as recited in claim 11 further comprising for the target entity, combining individual scores on a direct link on one or more directed paths on a scoring directed graph to produce one or more final scores to generate a set of scores from a source entity to the target entity with an associated set of one confidence value for each score,

wherein each score on a directed link from a first entity to a second entity is defined as a confidence value for the score on a directed link from the second entity to a third entity on each path identified in act (a),

wherein a score selected from between the scores from the first entity to the second entity and the scores from the second entity to the third entity is defined as the confidence value for the score on a directed link from the third entity to a fourth entity to generate a selected score,

wherein the selected score may be determined as the lesser of the scores and/or other discriminating process;

wherein a score with a negative confidence value is substituted by the negated score with the negated confidence value,

wherein the set of scores for a fork entity defined as an entity having more than one path from the source entity is determined by the further act (C) of;

converting each imput confidence value TI_n associated with each score SI_n on each directed link numbered n from each of n entities to the fork entity into an error margin M_n=1−

T_n,

further calculating the result scores SO_m as means of the m shortest ranges formed by intersecting the ranges [Si_n−

M_n . . . SI_n+M_n] for all values of n,

wherein shortest ranges are defined as the smallest possible intersections of the largest number of overlapping ranges,

wherein the set of confidence values T_m associated with the set of scores SO_m for the fork entity are calculated as the difference between the minimum and maximum of each shortest range of which SO_m is the mean, and

wherein the set of scores and associated set of confidence values for a fork entity where the fork entity is the target entity are the final set of scores and associated set of confidence values for act (b).

18. The method as recited in claim 11 further comprising providing a population space where more than one directed link on the same dimension can exist between any two entities such that the directed link has one or more associated identifiers comprising a time stamp representative of the time of the creation of the link,

wherein act (a) can be constrained by a limiting condition such that only directed links for which the identifier meets this condition are included within paths identified between the source entity and the target entity.

19. The method as recited in claim 18 further comprising for the target entity, combining individual scores on a direct link on one or more directed paths on a scoring directed graph to produce one or more final scores to generate a set of scores from a source entity to the target entity with an associated set of one confidence value for each score,

wherein each score on a directed link from a first entity to a second entity can be defined as a confidence value for the score on a directed link from the second entity to a third entity on each path identified in act (a),

wherein a score selected from between the scores from the first entity to the second entity and the scores from the second entity to the third entity can be defined as the confidence value for the score on a directed link from the third entity to a fourth entity to provide a selected score,

wherein the selected score can be determined as the lesser of the scores, or through any other selection process,

wherein a score with a negative confidence value can be substituted by the negated score with the negated confidence value,

wherein the set of scores for a fork entity defined as an entity having more than one path from the source entity is determined by the further act (C) of:

converting each input confidence value TI_n associated with each input score SI_n on each directed link numbered n from each of n entities to the fork entity into an error margin M_n=1−

T_n,

further calculating the result output scores SO_m as means of the m shortest ranges formed by intersecting the ranges [SI_n−

M_n . . . SI_n+M_n] for all values of n,

wherein shortest ranges are defined as the smallest possible intersections of the largest number of overlapping ranges;

wherein the result output confidence values TO_m associated with the result output scores SO_m for the fork entity are calculated as the difference between the minimum and maximum of each shortest range of which SO_m is the mean, and

wherein the set of scores and associated set of confidence values for a fork entity where the fork entity is the target entity are the final set of scores and associated set of confidence values for act (b).

20. A method to determine the influence in a given dimension of a intermediate entity in determining the score in the given dimension of a target entity from a source entity, comprising the computer-implemented acts of:

(a) determining a measure of influence of a given intermediate entity on potential source entities defined as those with one or more directed paths to the intermediate entity on the given dimension or associated transitive dimension, given the existence of potential target entities defined as those to which one or more directed paths exist from the intermediate entity on the given dimension or associated transitive dimension, where the measure of influence can be calculated as a function of values comprising;

the number of potential source entities, the number of potential target entities, the number of potential directed paths between any one entity and any other entity on a the given dimension, the number of potential directed paths that include the given intermediate entity, the number of times within a defined period that a directed link from the intermediate entity is used for the target entity, combining individual scores on a direct link on one or more directed paths on a scoring directed graph to produce one or more final scores, the number of times within a defined period that a path from any source entity to any target entity is identified by performing a graph search to identify one or more directed paths from the source entity to the target entity on the given dimension to generate a directed graph having therein a combination of the identified directed paths act, and the number of times within a defined period that a set of final scores is generated for the target entity, combining individual scores on a direct link on one or more directed paths on a scoring directed graph to produce one or more final scores.

21. The method as recited in claim 20, further comprising notifying entities comprising any of source entities, target entities, and the given intermediate entity of the measure of influence determined for the intermediate entity.