Systems and methods for reputation management

• US 7,827,052 B2
• Filed: 09/30/2005
• Issued: 11/02/2010
• Est. Priority Date: 09/30/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Reynar, Jeff C., Scott, James Kevin, Dave, Kushal B., Hylton, Jeremy A.
• Primary Examiner(s): Jeanty; Romain
• Assistant Examiner(s): Feeney; Brett
• Application Number:
  US11/241,693
• Publication Number:
  US 20070078699A1
• Time in Patent Office: 1,859 Days
• Field of Search: None
• US Class Current: 705/7.11
• CPC Class Codes: G06Q 10/063 Operations research, analysis or management
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A reputation management system, method and computer readable storage medium assigns reputation scores to various types of entities including, but not limited to people, products, advertisers and merchants. A reputation function is based on a directed graph including the reviewers and the reviews. The nodes in the graph represent the reviewers and the reviews and the links in the graph represent the ratings. The reputation function is iteratively solved until a convergence condition is met. Prior to convergence, when a stability condition is met, the reputation function is modified so as to remove portions of the function corresponding to nodes with negative reputations. Upon convergence, reputation values for at least the reviewers and reviews corresponding to nodes that have not been removed from the reputation function are generated.

Claims

1. A method for determining reputation values comprising:

on a server system having one or more processors and memory storing one or more programs for execution by the one or more processors, performing the steps comprising;

until a convergence condition is satisfied;

iteratively solving a reputation function for a set of reputation values with respect to a set of linked nodes, the nodes including first nodes representing reviewers and second nodes representing reviews, wherein at each iteration, the reputation values of the reviewers are updated in accordance with reputation values of one or more of the reviews and the reputation values of the reviews are updated in accordance with reputation values of one or more of the reviewers;

determining whether a stability condition is satisfied, wherein the stability condition is satisfied when an absolute difference between a current value of the set of reputation values and a previous value of the set of reputation values is less than a predetermined convergence value;

modifying the reputation function so as to remove from the reputation function portions of the reputation function corresponding to nodes with negative reputation when the stability condition is satisfied; and

generating reputation values for at least the reviewers and reviews corresponding to nodes that have not been removed from the reputation function.

2. The method of claim 1, wherein prior to solving a first iteration of the reputation function:

excluding from the reputation function nodes having no outlinks; and

excluding from the reputation function nodes having no positively valued outlinks.

3. The method of claim 2, wherein prior to solving the first iteration of the reputation function but subsequent to excluding from the reputation function nodes having no outlinks and excluding from the reputation function nodes having no positively valued outlinks:

normalizing respective outlinks for a node to sum to a predefined value.

4. The method of claim 3, wherein the normalizing includes:

normalizing the respective node outlinks by dividing each respective node outlink value by a value corresponding to a sum of the respective node outlink values; and

creating modified node outlink values when the sum of the normalized node outlink values does not sum to the predefined value by distributing a value corresponding to (1−

the sum of the normalized node outlink values) among the positively valued normalized node outlink values.

5. The method of claim 1, wherein modifying the reputation function includes:

removing nodes having a respective current iteration reputation value less than zero.

6. The method of claim 5, wherein removing nodes having the respective current iteration reputation value less than zero is performed when the stability condition is satisfied.

7. The method of claim 5, wherein subsequent to the removing, modifying the reputation function to distribute the respective current iteration value corresponding to each removed node among a remaining set of reputation values.

8. The method of claim 7, further including:

identifying a set of nodes removed because their respective current iteration reputation values were less than zero; and

modifying each respective current iteration reputation value in the set based on a decay factor of the reputation ranking function and an iteration value during which the respective node in the set was removed.

23. The method of claim 1, wherein

iteratively solving a reputation function comprises iteratively solving the reputation function for a vector of reputation values with respect to a matrix of linked nodes, the nodes including first nodes representing reviewers and second nodes representing reviews, wherein at each iteration, the matrix is multiplied by the vector such that the reputation values of the reviewers are updated in accordance with reputation values of one or more of the reviews and the reputation values of the reviews are updated in accordance with reputation values of one or more of the reviewers;

and

modifying the reputation function comprises modifying the reputation function so as to remove from the matrix nodes with negative reputation when the stability condition is satisfied.

9. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

instructions for repeatedly performing a set operations, until a convergence condition is satisfied, the set of operations comprising;

solving an iteration of a reputation function for a set of reputation values with respect to a set of linked nodes, the nodes including first nodes representing reviewers and second nodes representing reviews, wherein at each iteration, the reputation values of the reviewers are updated in accordance with reputation values of one or more of the reviews and the reputation values of the reviews are updated in accordance with reputation values of one or more of the reviewers;

determining whether a stability condition is satisfied, wherein the stability condition is satisfied when an absolute difference between a current value of the set of reputation values and a previous value of the set of reputation values is less than a predetermined convergence value;

modifying the reputation function so as to remove from the reputation function portions of the reputation function corresponding to nodes with negative reputation when the stability condition is satisfied; and

generating reputation values for at least the reviewers and reviews corresponding to nodes that have not been removed from the reputation function.

10. The computer program product of claim 9, further including instructions for, prior to solving a first iteration of the reputation function:

excluding from the reputation function nodes having no outlinks; and

excluding from the reputation function nodes having no positively valued outlinks.

11. The computer program product of claim 10, further including instructions for, prior to solving the first iteration of the reputation function but subsequent to excluding from the reputation function nodes having no outlinks and excluding from the reputation function nodes having no positively valued outlinks:

normalizing respective outlinks for a node to sum to a predefined value.

12. The computer program product of claim 11, wherein the instructions for normalizing include:

instructions for normalizing the respective node outlinks by dividing each respective node outlink value by a value corresponding to a sum of the respective node outlink values; and

instructions for creating modified node outlink values when the sum of the normalized node outlink values does not sum to the predefined value by distributing a value corresponding to (1−

the sum of the normalized node outlink values) among the positively valued normalized node outlink values.

13. The computer program product of claim 9, wherein the instructions for modifying the reputation function include:

instructions for removing nodes having a respective current iteration reputation value less than zero.

14. The computer program product of claim 13, further including instructions for, subsequent to the removing, modifying the reputation function to distribute the respective current iteration value corresponding to each removed node among a remaining set of reputation values.

15. The computer program product of claim 14, further including instructions for:

identifying a set of nodes removed because their respective current iteration reputation values were less than zero; and

modifying each respective current iteration reputation value in the set based on a decay factor of the reputation ranking function and an iteration value during which the respect node in the set was removed.

24. The computer program product of claim 9, wherein

solving an iteration of a reputation function comprises solving an iteration of a reputation function for a vector of reputation values with respect to a matrix of linked nodes, the nodes including first nodes representing reviewers and second nodes representing reviews, wherein at each iteration, the matrix is multiplied by the vector such that the reputation values of the reviewers are updated in accordance with reputation values of one or more of the reviews and the reputation values of the reviews are updated in accordance with reputation values of one or more of the reviewers;

and

modifying the reputation function comprises modifying the reputation function so as to remove from the matrix nodes with negative reputation when the stability condition is satisfied.

16. A computer, comprising:

memory;

one or more processors; and

at least one program, stored in the memory and executed by the one or more processors, the at least one program including;

instructions for iteratively solving a reputation function for a set of reputation values with respect to a set of linked nodes, the nodes including first nodes representing reviewers and second nodes representing reviews, wherein at each iteration, the reputation values of the reviewers are updated in accordance with reputation values of one or more of the reviews and the reputation values of the reviews are updated in accordance with reputation values of one or more of the reviewers;

instructions for determining whether a stability condition is satisfied, wherein the stability condition is satisfied when an absolute difference between a current value of the set of reputation values and a previous value of the set of reputation values is less than a predetermined convergence value;

instructions modifying the reputation function so as to remove from the reputation function portions of the reputation function corresponding to nodes with negative reputation when the stability condition is satisfied; and

instructions for generating reputation values for at least the reviewers and reviews corresponding to nodes that have not been removed from the reputation function.

17. The computer of claim 16, wherein the program further includes instructions for, prior to solving a first iteration of the reputation function:

excluding from the reputation function nodes having no outlinks; and

excluding from the reputation function nodes having no positively valued outlinks.

18. The computer of claim 17, wherein the program further includes instructions for, prior to solving the first iteration of the reputation function but subsequent to excluding from the reputation function nodes having no outlinks and excluding from the reputation function nodes having no positively valued outlinks:

normalizing respective outlinks for a node to sum to a predefined value.

19. The computer of claim 18, wherein the instructions for normalizing includes instructions for:

normalizing the respective node outlinks by dividing each respective node outlink value by a value corresponding to a sum of the respective node outlink values; and

creating modified node outlink values when the sum of the normalized node outlink values does not sum to the predefined value by distributing a value corresponding to (1−

the sum of the normalized node outlink values) among the positively valued normalized node outlink values.

20. The computer of claim 16, wherein the instructions for modifying the reputation function includes instructions for removing nodes having a respective current iteration reputation value less than zero.

21. The computer of claim 20, wherein the program further includes instructions for, subsequent to the removing, modifying the reputation function to distribute the respective current iteration value corresponding to each removed node among a remaining set of reputation values.

22. The computer of claim 21, wherein the program further includes instructions for:

identifying a set of nodes removed because their respective current iteration reputation values were less than zero; and

modifying each respective current iteration reputation value in the set based on a decay factor of the reputation ranking function and an iteration value during which the respect node in the set was removed.

25. The computer of claim 16, wherein

the instructions for iteratively solving a reputation function comprise instructions for iteratively solving a reputation function for a vector of reputation values with respect to a matrix of linked nodes, the nodes including first nodes representing reviewers and second nodes representing reviews, wherein at each iteration, the matrix is multiplied by the vector such that the reputation values of the reviewers are updated in accordance with reputation values of one or more of the reviews and the reputation values of the reviews are updated in accordance with reputation values of one or more of the reviewers;

and

the instructions modifying the reputation function comprise instructions modifying the reputation function so as to remove from the matrix nodes with negative reputation when the stability condition is satisfied.