Social network node clustering system and method

• US 8,606,787 B1
• Filed: 09/15/2010
• Issued: 12/10/2013
• Est. Priority Date: 09/15/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Asgekar, Amogh, Tawari, Sandesh
• Primary Examiner(s): Kerzhner, Aleksandr
• Application Number:
  US12/882,441
• Time in Patent Office: 1,182 Days
• Field of Search: 707/737, 707/999.002
• US Class Current: 707/737
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06Q 50/01 Social networking

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.

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.

2. The method of claim 1, wherein the forming uses the first similarity measure and the modifying uses a second similarity measure.

3. The method of claim 1, wherein the similarity processor is comprised of distributed computing devices and said generating is performed by the distributed computing devices.

4. The method of claim 1, wherein the clustering processor is comprised of distributed computing devices and said forming groups is performed by the distributed computing devices.

5. The method of claim 1, wherein generating further comprises forming an inverse matrix of neighbors and nodes.

6. The method of claim 1, wherein the generating includes applying the first similarity measure based on a ratio between the number of the one or more common nodes in the first and second neighbor lists and the graph-specific decay parameter.

7. The method of claim 1, further comprising storing the clusters for future use.

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.

9. The system of claim 8, further comprising a storage subsystem operatively coupled to the clustering processor and configured to store the clusters for future use.

10. The system of claim 8, wherein the similarity processor is further configured to generate an inverse matrix of neighbors and nodes.

11. The system of claim 8, wherein the similarity processor is further configured to apply the first similarity measure based on a ratio between the number of the one or more common nodes in the first and second neighbor lists and the graph-specific decay parameter.

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.

13. The non-transitory computer-readable storage medium of claim 12 wherein the first similarity measure is applied in the assigning and a second similarity measure is applied in the merge of select clusters.

14. The non-transitory computer-readable storage medium of claim 12 wherein a first portion of the computer program instructions is executed on a first computing device and a second portion of the computer program instructions is executed on a second computing device.

15. The non-transitory computer-readable storage medium of claim 12 wherein the instructions to generate include instructions to form an inverse matrix of neighbors and nodes.

16. The non-transitory computer-readable storage medium of claim 12 wherein the instructions to generate include instructions to apply the first similarity measure based on a ratio of the number of the one or more common nodes and the graph-specific decay parameter.

17. The non-transitory computer-readable storage medium of claim 12 further comprising instructions to store the clusters for future use.

18. The non-transitory computer-readable storage medium of claim 12 further comprising instructions to apply the clusters to the social network.

19. The non-transitory computer-readable storage medium of claim 12 further comprising instructions to share information with select nodes corresponding to select clusters.

20. The non-transitory computer-readable storage medium of claim 12 instructions to suggest sharing of information responsive to select clusters.