Systems and methods for using one or more networks to assess a metric about an entity

• US 10,469,504 B1
• Filed: 09/08/2017
• Issued: 11/05/2019
• Est. Priority Date: 09/08/2017
• Status: Active Grant

• Current Assignee: Stripe, Inc.
• Original Assignee: Stripe, Inc.
• Inventors: Dandekar, Pranav, Lofgren, Peter, Goel, Ashish
• Primary Examiner(s): Homayounmehr, Farid
• Assistant Examiner(s): Le, Thanh T
• Application Number:
  US15/699,808
• Time in Patent Office: 788 Days
• Field of Search: 726 4
• CPC Class Codes: G06F 15/16 Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs coordinating program control therefor G06F9/52; in regulating and control system G05B
• CPC Class Codes: G06F 21/50 Monitoring users, programs or devices to maintain the integrity of platforms, e.g. of processors, firmware or operating systems
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 63/101 Access control lists [ACL]
• CPC Class Codes: H04L 63/102 Entity profiles
• CPC Class Codes: H04L 63/105 Multiple levels of security

Abstract

Described herein are systems and methods for predicting a metric value for an entity associated with a query node in a graph that represents a network. In embodiments, using a user'"'"'s profile as the query node, a metric about that user may be estimated based, at least in part, as a function of how well connected the query node is to a whitelist of “good” users/nodes in the network, a blacklist of “bad” users/nodes in the network, or both. In embodiments, one or more nodes or edges may be weighted when determining a final score for the query node. In embodiments, the final score regarding the metric may be used to take one or more actions relative to the query node, including accepting it into a network, allowing or rejecting a transaction, assigning a classification to the node, using the final score to compute another estimate for a node, etc.

Claims

1. A computer-implemented method for predicting a metric value for an entity associated with a query node in a graph that represents a network, the method comprising:

for each pre-classified node in a set of pre-classified nodes, which comprises a set of whitelist nodes, from the network, determining a score that gauges a strength of connection between the pre-classified node to the query node, the strength of connection being obtained by performing the steps comprising;

responsive to a first condition of the set of pre-classified nodes having a number of nodes above a first threshold being true, performing the steps comprising;

performing a number of random walks in the graph from the query node in the graph and terminating at another node in the graph;

for at least each node in the graph at which a random walk terminates, keeping a counter of how many times a walk terminated at that node in the graph;

determining a ranking value between the query node and another node in the graph based at least in part by dividing the number of times walks terminated on the another node by the number of random walks; and

using one or more ranking values to obtain a score that measures a strength of connection between the query node and the another node in the graph; and

generating a final value for the metric for the query node, the final value comprising a combination of at least one of the scores that gauges strength of connection between the pre-classified nodes of the set of pre-classified nodes to the query node.

2. The computer-implemented method of claim 1 wherein the step of using one or more ranking values to obtain a score that measures a strength of connection between the query node and the another node in the graph further comprising:

using the ranking values of a set of in-neighbors of the another node to obtain a ranking value for the another node, responsive to the another node having a number of in-neighbors that is less than a second threshold.

3. The computer-implemented method of claim 1 further comprising:

responsive to the first condition of the set of pre-classified nodes having a number of nodes above a first threshold being false, performing the steps comprising;

for each pre-classified node and its in-neighbors, obtaining ranking values and related residual values for nodes within a first distance of the pre-classified node;

for the query node, obtaining ranking values and related residual values for nodes within a second distance of the query node; and

using at least some of the ranking and residual values to obtain a probability that a random walk from the query node stops at a pre-classified node, the probability being used to obtain a score that measures a strength of connection between the query node and the pre-classified node.

4. The computer-implemented method of claim 3 wherein the first and second distances are two steps in the graph.

5. The computer-implemented method of claim 1 wherein the set of pre-classified nodes also comprises a set of blacklist nodes, the method further comprising:

the step of generating a final value for the metric for the query node, the final value comprising a combination of at least one of the scores that gauges strength of connection between the pre-classified nodes of the set of pre-classified nodes to the query node comprises;

generating a blacklist blended value for the metric comprising a combination of the scores for the blacklist nodes in the set of blacklist nodes;

generating a whitelist blended value for the metric comprising a combination of the scores for the whitelist nodes in the set of whitelist nodes; and

generating a final score blended from the whitelist blended value and the blacklist blended value to obtain the final value for the query node.

6. The computer-implemented method of claim 5 wherein the whitelist blended value has a first sign and the blacklist blended value has a second sign and the method further comprises:

responsive to the final value having the first sign, assigning a positive reputation to the query node; and

responsive to the final value having the second value, assigning a negative reputation to the query node.

7. The computer-implemented method of claim 6 using the final value to classify the query node in which the query node is included in the pre-classified nodes for use in predicting a metric value for an entity associated with a different query node in the graph.

8. A system for predicting a metric value for an entity associated with a query node in a graph that represents a network, the system comprising:

one or more processors; and

a non-transitory computer-readable medium or non-transitory computer-readable media comprising one or more sequences of instructions which, when executed by the one or more processors, causes steps to be performed comprising;

for each pre-classified node in a set of pre-classified nodes, which comprises a set of whitelist nodes, from the network, determining a score that gauges a strength of connection between the pre-classified node to the query node, the strength of connection being obtained by performing the steps comprising;

responsive to a first condition of the set of pre-classified nodes having a number of nodes above a first threshold being true, performing the steps comprising;

performing a number of random walks in the graph from the query node in the graph and terminating at another node in the graph;

for at least each node in the graph at which a random walk terminates, keeping a counter of how many times a walk terminated at that node in the graph;

determining a ranking value between the query node and another node in the graph based at least in part by dividing the number of times walks terminated on the another node by the number of random walks; and

using one or more ranking values to obtain a score that measures a strength of connection between the query node and the another node in the graph; and

generating a final value for the metric for the query node, the final value comprising a combination of at least one of the scores that gauges strength of connection between the pre-classified nodes of the set of pre-classified nodes to the query node.

9. The system of claim 8 wherein the step of using one or more ranking values to obtain a score that measures a strength of connection between the query node and the another node in the graph further comprising:

using the ranking values of a set of in-neighbors of the another node to obtain a ranking value for the another node, responsive to the another node having a number of in-neighbors that is less than a second threshold.

10. The system of claim 8 wherein the non-transitory computer-readable medium or non-transitory computer-readable media further comprises one or more sequences of instructions which, when executed by the one or more processors, causes steps to be performed comprising:

responsive to the first condition of the set of pre-classified nodes having a number of nodes above a first threshold being false, performing the steps comprising;

for each pre-classified node and its in-neighbors, obtaining ranking values and related residual values for nodes within a first distance of the pre-classified node;

for the query node, obtaining ranking values and related residual values for nodes within a second distance of the query node; and

using at least some of the ranking and residual values to obtain a probability that a random walk from the query node stops at a pre-classified node, the probability being used to obtain a score that measures a strength of connection between the query node and the pre-classified node.

11. The system of claim 10 wherein the first and second distances are two steps in the graph.

12. The system of claim 8 wherein the set of pre-classified nodes further comprises a set of blacklist nodes and wherein the step of generating a final value for the metric for the query node, the final value comprising a combination of at least one of the scores that gauges strength of connection between the pre-classified nodes of the set of pre-classified nodes to the query node comprises:

generating a blacklist blended value for the metric comprising a combination of the scores for the blacklist nodes in the set of blacklist nodes;

generating a whitelist blended value for the metric comprising a combination of the scores for the whitelist nodes in the set of whitelist nodes; and

generating a final score blended from the whitelist blended value and the blacklist blended value to obtain the final value for the query node.

13. The system of claim 12 wherein the whitelist blended value has a first sign and the blacklist blended value has a second sign and wherein the non-transitory computer-readable medium or non-transitory computer-readable media further comprises one or more sequences of instructions which, when executed by the one or more processors, causes steps to be performed comprising:

responsive to the final value having the first sign, classifying the query node with a positive reputation classification; and

responsive to the final value having the second value, classifying the query node with a negative reputation classification.

14. A computer-implemented method for predicting a metric about an entity associated with a query node in a graph that represents a network, the method comprising:

for each whitelist node in a set of whitelist nodes from the network, determining a score that measures a strength of connection of the query node with respect to the whitelist node by performing the steps comprising;

performing a number of random walks in the graph from a start node in the graph and terminating at another node in the graph;

keeping a counter of how many times a walk terminated at a node in the graph;

determining an estimate of a strength of connection between the start node and another node in the graph comprising dividing the number of times walks terminated on the another node by the number of random walks; and

using the estimate of a strength of connection to determine the score that measures a strength of connection;

generating a whitelist blended value for the metric comprising a combination of the scores for the whitelist nodes in the set of whitelist nodes;

for each blacklist node in a set of blacklist nodes from the network, determining a score that measures a strength of connection of the blacklist node with respect to the query node;

generating a blacklist blended value for the metric comprising a combination of the scores for the blacklist nodes in the set of blacklist nodes; and

generating a final score blended from the whitelist blended value and the blacklist blended value to obtain an overall score for the query node.

15. The computer-implemented method of claim 14 wherein the whitelist blended value has a first sign and the blacklist blended value has a second sign and the method further comprising:

responsive to the final score having the first sign, taking an affirmative action relative to the query node; and

responsive to the final score having the second value, taking a negative action relative to the query node.

16. The computer-implemented method of claim 14 further comprising the step of:

obtaining final scores for a plurality of query nodes;

responsive to a query node from the plurality of query nodes having a final score with a first sign, assigning it to the set of whitelist nodes;

responsive to a query node from the plurality of query nodes having a final score with a second sign, assigning it to the set of blacklist nodes; and

selecting a query node and repeating the prior steps until a stop condition is reached to obtain a final score blended for the query node.

17. The computer-implemented method of claim 14 further comprising:

generating the graph of the network by determining or inferring one or more interactions between entities, wherein a node in the graph represents an entity and an edge in the graph connects two nodes and represents at least one interaction between those two nodes.

18. The computer-implemented method of claim 17 further comprising:

assigning weights to at least one of;

one or more nodes in the graph, one or more edges in the graph, or both; and

using at least one of the weights in computing a final score.

19. A non-transitory computer-readable medium or non-transitory computer-readable media comprising one or more sequences of instructions which, when executed by one or more processors, causes steps for predicting a metric about an entity associated with a query node in a graph that represents a network to be performed, the steps comprising:

for each whitelist node in a set of whitelist nodes from the network, determining a score that measures a strength of connection of the query node with respect to the whitelist node by performing the steps comprising;

performing a number of random walks in the graph from a start node in the graph and terminating at another node in the graph;

keeping a counter of how many times a walk terminated at a node in the graph;

determining an estimate of a strength of connection between the start node and another node in the graph comprising dividing the number of times walks terminated on the another node by the number of random walks; and

using the estimate of a strength of connection to determine the score that measures a strength of connection;

generating a whitelist blended value for the metric comprising a combination of the scores for the whitelist nodes in the set of whitelist nodes;

for each blacklist node in a set of blacklist nodes from the network, determining a score that measures a strength of connection of the blacklist node with respect to the query node;

generating a blacklist blended value for the metric comprising a combination of the scores for the blacklist nodes in the set of blacklist nodes; and

generating a final score blended from the whitelist blended value and the blacklist blended value to obtain an overall score for the query node.