Scoring nodes in a directed graph with positive and negative links

• US 8,370,313 B2
• Filed: 06/09/2010
• Issued: 02/05/2013
• Est. Priority Date: 06/10/2009
• Status: Active Grant

• Current Assignee: Snow, James
• Original Assignee: Snow, James
• Inventors: Snow, James Matthew
• Primary Examiner(s): Hoang, Son T
• Application Number:
  US12/797,167
• Publication Number:
  US 20110307494A1
• Time in Patent Office: 972 Days
• Field of Search: 707/694, 707/798
• US Class Current: 707/694
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A method assigns a score to each node in a directed graph. Nodes in the graph represent autonomous entities, and links denote opinions entities hold of each other. Scores are assigned based on either a deterministic iterative method or a random walk. Both methods are able to take negative opinions into account by assigning negative reputation to a node in proportion to the positive reputation of the node that links to it with a negative opinion, and also assigning a separate kind of negative reputation to nodes that have a positive opinion of a node with either kind of negative reputation. The random walk method also solves the “rank sink” problem of previous methods by disallowing any single traversal from visiting any particular node more than once within a certain interval.

Claims

1. A method of determining a multidimensional reputation score for each node in a directed graph, comprising:

providing, to a computer, the directed graph comprising a plurality of nodes, a plurality of positive links and a plurality of negative links, wherein each of the plurality of nodes represents an autonomous entity and each of the plurality of positive and negative links represents a positive or negative opinion which a source node of each link holds of a target node of each link, respectively,

generating, by the computer, an initial estimate of a reputation score for having at least a value of positive reputation, a value of negative reputation, and a value of gullibility wherein the gullibility value is a separate kind of negative reputation accrued by a node by establishing positive links to nodes with negative reputation;

updating, by the computer, the initial estimate of the reputation score of each node for one or more rounds wherein

each node'"'"'s positive incoming links contribute to that node'"'"'s positive reputation score in proportion to the positive reputation score of the source of that positive link in the immediately previous round, and

each node'"'"'s negative incoming links contribute to that node'"'"'s negative reputation score in proportion to the positive reputation score of the source of that negative link in the immediately previous round;

each node'"'"'s positive outgoing links contribute to that node'"'"'s gullibility score in proportion to some weighted combination of the negative reputation score and the gullibility score of the target of that positive link in the immediately previous round;

and

returning from a last round, by the computer, a final reputation score for one or more nodes wherein the returning comprises;

producing the final reputation score for each node which includes a gullibility score.

2. The method of claim 1, where the directed graph represents relationships between users of a multiplayer online computer game, wherein the nodes represent the users, and the links represent the relationships.

3. The method of claim 1, where the directed graph represents relationships between users of an online forum, wherein the nodes represent the users, and the links represent the relationships.

4. The method of claim 1, where the directed graph represents relationships between computers connected to a common peer-to-peer service, wherein the nodes represent the computers, and the links represent the relationships.

5. A method of determining a reputation score for each node in a directed graph comprising:

providing, to a computer, the directed graph comprising a plurality of nodes, and a plurality of links, wherein each of the plurality of nodes represents an autonomous entity and each of the plurality of links represents a positive opinion which a source node of that link holds of a target node of that link,

generating, by the computer, a reputation score for each node having at least a value of positive reputation

by performing one or more random traversals and counting visits to each node by incrementing a per-node counter wherein a generating comprises;

counting at most one visit to each node per traversal, so that a reputation score of a particular node is not increased by having a link to other nodes that links back to the particular node,

and returning a final reputation score for the particular node, wherein the final reputation score is a value of the counter of the particular node divided by a sum of counters for all of the plurality of nodes.

6. The method of claim 5 wherein each node'"'"'s final score is further modified by multiplying the score by the total number of nodes in the directed graph.

7. The method of claim 5, wherein when a node is visited during a particular traversal, the node is removed from consideration as a candidate destination node for a remainder of the traversal.

8. The method of claim 5, wherein during a particular traversal, counters for all visited nodes are each incremented only once, regardless of whether a node was visited more than once.

9. The method of claim 5, where the directed graph represents relationships between users of a multiplayer online computer game, wherein the nodes represent the users, and the links represent the relationships.

10. The method of claim 5, where the directed graph represents relationships between users of an online forum, wherein the nodes represent the users, and the links represent the relationships.

11. The method of claim 5, where the directed graph represents relationships between computers connected to a common peer-to-peer service, wherein the nodes represent the computer, and the links represent the relationships.

12. A method of determining a multidimensional reputation score for each node in a directed graph, comprising:

providing, by to a computer, the directed graph comprising a plurality of nodes, a plurality of positive links and a plurality of negative links, wherein each of the plurality of nodes represents an autonomous entity and each of the plurality of positive and negative links represents a positive or negative opinion which a source node of that link holds of a target node of that link, respectively,

generating, by the computer, a reputation score for each node having at least a value of positive reputation, a value of negative reputation, and a value of gullibility wherein the gullibility value is a kind of negative reputation accrued by establishing positive links to nodes with negative reputation by performing one or more random traversals and counting visits to each node by incrementing a per-node set of counters, one for each of positive reputation, negative reputation, and gullibility, wherein the generating comprises;

traversing by following links at random in outgoing direction, incrementing positive value counter for all visited nodes until the traversing terminates or traverses a negative link, in response to the traversing traverses the negative link, the traversing

increments the negative value counter corresponding to a node which is the destination of the negative link, and

proceeds to follow positive incoming links in a reverse direction at random from the destination of the negative link,

incrementing a gullibility counter of every node the traversing visits until the traversal terminates; and

producing a final reputation score for each node which includes a gullibility score computed in part from gullibility counter for each node, wherein positive links contribute to a source node of the positive links gullibility score in proportion to a negative reputation and gullibility scores of a target node of the positive links,

wherein the final reputation score for a particular node comprises of positive value of counter of the particular node, negative value of the counter of the particular node, and gullibility counter of the particular node, each divided by a total sum of all hits of all types for all of the plurality of nodes.

13. The method of claim 12 wherein each node'"'"'s final score values are further modified by multiplying each by the total number of nodes in the directed graph.

14. The method of claim 12, wherein once a node is visited during a positive incoming stage of a traversal, the node is removed from consideration as a candidate destination node for a remainder of the traversal.

15. The method of claim 12, wherein during a positive incoming stage of a traversal, counters for all visited nodes are each incremented only once, regardless of whether a node was visited more than once.

16. The method of claim 12, where the directed graph represents relationships between users of a multiplayer online computer game, wherein the nodes represent the users, and the links represent the relationships.

17. The method of claim 12, where the directed graph represents relationships between users of an online forum, wherein the nodes represent the users, and the links represent the relationships.

18. The method of claim 12, where the directed graph represents relationships between computers connected to a common peer-to-peer service, wherein the nodes represent the computers, and the links represent the relationships.