Social network node clustering system and method
First Claim
Patent Images
1. A computer-implemented method of generating clusters of users in a social network, the social network represented as a graph of nodes and the users represented as the nodes, the method comprising:
- generating by a similarity processor, a matrix of nodes by;
obtaining a first neighbor list for a first user and a second neighbor list for a second user in the social network;
finding one or more common nodes in the first and second neighbor lists; and
applying a first similarity measure based on a number of the one or more common nodes and a graph-specific decay parameter, the graph-specific decay parameter describing how a similarity score is spread out in the graph of nodes according to one or more values of the graph-specific decay parameter;
forming groups by a clustering processor, the clustering processor assigning select nodes to intermediate clusters responsive to the matrix and merging select clusters together responsive to similarity thereof; and
modifying the intermediate clusters by adding select nodes responsive to similarity thereof.
2 Assignments
0 Petitions
Accused Products
Abstract
Users in a social network are represented by nodes on a network graph. A similarity processor generates a similarity matrix of nodes and neighbors. A clustering processor groups select nodes based on similarity. Nodes initially assigned to one cluster are selectively added to other clusters based on similarity. A social network processor provides features and processing based on the clusters of nodes thus produced.
95 Citations
20 Claims
-
1. A computer-implemented method of generating clusters of users in a social network, the social network represented as a graph of nodes and the users represented as the nodes, the method comprising:
-
generating by a similarity processor, a matrix of nodes by; obtaining a first neighbor list for a first user and a second neighbor list for a second user in the social network; finding one or more common nodes in the first and second neighbor lists; and applying a first similarity measure based on a number of the one or more common nodes and a graph-specific decay parameter, the graph-specific decay parameter describing how a similarity score is spread out in the graph of nodes according to one or more values of the graph-specific decay parameter; forming groups by a clustering processor, the clustering processor assigning select nodes to intermediate clusters responsive to the matrix and merging select clusters together responsive to similarity thereof; and modifying the intermediate clusters by adding select nodes responsive to similarity thereof. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A system for electronically generating clusters of users in a social network, the social network represented as a graph of nodes and the users represented as the nodes, the system comprising:
-
a memory; a similarity processor configured to execute code loaded into the memory to generate a matrix of nodes by; obtaining a first neighbor list for a first user and a second neighbor list for a second user in the social network; finding one or more common nodes between the nodes in the first and second neighbor lists; and applying a first similarity measure based on a number of the one or more common nodes and a graph-specific decay parameter, the graph-specific decay parameter describing how a similarity score is spread out in the graph of nodes according to one or more values of the graph-specific decay parameter; and a clustering processor configured to execute code loaded into the memory to group the nodes and neighbors into the clusters, the clustering processor including a first subsystem adapted to combine nodes into intermediate clusters and combine intermediate clusters together responsive to similarity thereof, the clustering processor further including a soft cluster subsystem adapted to add nodes to the intermediate clusters responsive to similarity thereof in order to generate the clusters. - View Dependent Claims (9, 10, 11)
-
-
12. A non-transitory computer-readable storage medium containing executable computer program instructions for generating clusters of users in a social network, the social network represented as a graph of nodes and the users represented as the nodes, the computer program instructions comprising:
-
instructions to generate a matrix of nodes by; obtaining a first neighbor list for a first user and a second neighbor list for a second user in the social network; finding one or more common nodes between the nodes in the first and second neighbor lists; and applying a first similarity measure based on a number of the one or more common nodes and a graph-specific decay parameter, the graph-specific decay parameter describing how a similarity score is spread out in the graph of nodes according to one or more values of the graph-specific decay parameter; instructions to form groups by assigning select nodes to intermediate clusters responsive to the matrix; instructions to merge select clusters together responsive to similarity thereof; and instructions to modify the intermediate clusters by adding select nodes responsive to similarity thereof. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20)
-
Specification