Graph-based multi-threading group detection

Patent metadata

Field	Value
Publication number	US-2023131051-A1
Application number	US-202117509854-A
Country	US
Kind code	A1
Filing date	Oct 25, 2021
Priority date	Oct 25, 2021
Publication date	Apr 27, 2023
Grant date	—

Abstract

Methods and systems are presented for detecting groups within a graph using computer-based multi-threading techniques. These techniques provide technical improvements in computing power and efficiency for analysis of large graphs. A group detection system accesses a graph. Threads are instantiated to perform task related to a group detection process based on the nodes in the graph, where a thread is instantiated for a corresponding node. Each thread determines a neighbor count representing a number of neighbor nodes having one degree of separation from the corresponding node. Each thread also generates a list comprising an identity of the corresponding node and identities of the neighbor nodes. The thread transmits the list only to threads corresponding to a first subset of the neighbor nodes having more neighbors than the corresponding node, but not to threads corresponding to a second subset of the neighbor nodes having less neighbors than the corresponding nodes.

First claim

What is claimed is:

1 . A system, comprising:
a non-transitory memory; and one or more hardware processors coupled with the non-transitory memory and configured to read instructions from the non-transitory memory to cause the system to perform operations comprising:
accessing a graph comprising a plurality of nodes and a plurality of edges connecting the plurality of nodes, wherein each node in the plurality of nodes represents a user account with a service provider, and wherein for any particular two nodes in the graph, an edge that exists between the particular two nodes indicates at least one common account attribute between two user accounts represented by the particular two nodes;
configuring a plurality of threads to perform tasks related to a group detection process based on the plurality of nodes, wherein each thread in the plurality of threads includes stored executable instructions configured to perform the tasks based on a corresponding node in the plurality of nodes;
determining, by a first thread from the plurality of threads that corresponds to a first node in the plurality of nodes, a first neighbor count representing a number of neighbor nodes having one degree of separation from the first node within the graph;
obtaining, by the first thread, a plurality of neighbor counts from a set of threads corresponding to the neighbor nodes of the first node;
determining, by the first thread for the first node, a first subset of the neighbor nodes having first neighbor counts more than the first neighbor count and a second subset of the neighbor nodes having second neighbor counts less than the first neighbor count;
generating, by the first thread, a first list comprising a first identity of the first node and identities of the neighbor nodes of the first node; and
transmitting, by the first thread, the first list to a first subset of the set of threads corresponding to the first subset of the neighbor nodes, but not a second subset of the set of threads corresponding to the second subset of the neighbor nodes.

2 . The system of claim 1 , wherein the operations further comprise:
receiving, by the first thread, one or more lists from the second subset of the set of threads; determining, by the first thread, that at least one list received from a particular thread is a subset of the first list; and in response to determining that the at least one list is a subset of the first list, terminating the particular thread.

3 . The system of claim 1 , wherein the operations further comprise:
transmitting, by the first thread, a first group detection report to a group detection system, wherein the group detection report comprises the first list.

4 . The system of claim 3 , wherein the operations further comprise:
receiving, by the group detection system, one or more group detection reports comprising the first group detection report from one or more threads comprising the first thread; and identifying, by the group detection system from the plurality of nodes in the graph, one or more groups of related nodes based on the group detection reports.

5 . The system of claim 3 , wherein the operations further comprise:
identifying, by the group detection system, a first group of related nodes within the graph based on the first group detection report obtained from the first thread; collectively analyzing activities conducted through user accounts represented by the first group of related nodes; deriving a pattern based on the collectively analyzing the activities; and performing an action associated with the user accounts based on the pattern.

6 . The system of claim 5 , wherein the action comprises reducing an access level associated with the user accounts.

7 . The system of claim 5 , wherein the action comprises providing an incentive to the user accounts.

8 . The system of claim 1 , wherein the operations further comprise:
generating, by the first thread, a first hashed value based on the first list; determining, by the first thread and based on a neighbor count obtained from a second thread of the plurality of thread, that a particular neighbor node from the neighbor nodes has a neighbor count identical to the first neighbor count; and determining, by the first thread, whether the first node and the particular neighbor node belong to a same group by comparing the first hashed value against a second hashed value obtained from the second thread.

9 . The system of claim 8 , wherein the operations further comprise:
in response to determining that the first node and the particular neighbor node belong to the same group, terminating the second thread.

10 . A method comprising:
accessing, by one or more hardware processors, a graph comprising a plurality of nodes and a plurality of edges connecting the plurality of nodes, wherein each node in the plurality of nodes represents a user account with a service provider, and wherein for any particular two nodes in the graph, an edge that exists between the particular two nodes indicates at least one common account attribute between two user accounts represented by the particular two nodes; and instantiating, by the one or more hardware processors, a first thread to perform tasks related to a group detection process based on a first node from the plurality of nodes, wherein the first thread comprises executable instructions configured to:
determine a first set of nodes having one degree of separation from the first node;
determine, for the first node, a first neighbor count representing a first number of nodes within the first set of nodes;
identify, from the first set of nodes, a first subset of nodes and a second subset of nodes, wherein each node in the first subset of nodes has more neighbor nodes than the first node, and wherein each node in the second subset of nodes has less neighbor nodes than the first node; and
compare the first set of nodes against neighbor nodes of the first subset of nodes but not against neighbor nodes of the second subset of nodes.

11 . The method of claim 10 , wherein the executable instructions are further configured to:
generate a first list of identities comprising an identity of the first node and identities of the first set of nodes; receive a second list of identities from a second thread corresponding to a second node in the graph; and determine whether the second list of identities is a subset of the first list of identities.

12 . The method of claim 11 , wherein the executable instructions are further configured to:
in response to determining that the second list of identities is a subset of the first list of identities, cause the second thread to terminate.

13 . The method of claim 10 , further comprising:
identifying a first group of nodes within the graph based on the first node and the first set of nodes; collectively analyzing activities conducted through user accounts represented by the first group of nodes; deriving a pattern based on the collectively analyzing the activities; and performing an action associated with the user accounts based on the pattern.

14 . The method of claim 10 , wherein the action comprises reducing an access level associated with the user accounts.

15 . A non-transitory machine-readable medium having stored thereon machine-readable instructions executable to cause a machine to perform operations comprising:
accessing a graph comprising a plurality of nodes and a plurality of edges connecting the plurality of nodes, wherein each node in the plurality of nodes represents a user account with a service provider, and wherein for any pa

Assignees

• Paypal Inc

Inventors

• Qiao Zhenyu
• Huang Jie
• Gu Jun
• Feng Si
• Dai Yunjing

Classifications

• G06F21/552

  involving long-term monitoring or reporting · CPC title

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F9/4881

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F16/90335

  Query processing · CPC title

• G06F9/52

  Program synchronisation; Mutual exclusion, e.g. by means of semaphores · CPC title