Social network node clustering system and method

• US 9,026,537 B1
• Filed: 11/22/2013
• Issued: 05/05/2015
• 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): Corrielus, Jean M
• Application Number:
  US14/087,969
• Time in Patent Office: 529 Days
• Field of Search: 707/737, 707/999.002, 709/223
• 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 comprising:

determining, using one or more computing devices, a set of first nodes in a social graph of a social network, the first nodes representing users of the social network;

generating, using the one or more computing devices, a neighbor list including sets of neighboring nodes for each of the first nodes;

transforming, using the one or more computing devices, the neighbor list to identify trivial neighboring nodes and non-trivial neighboring nodes;

comparing, using the one or more computing devices, the first nodes that are associated with each of the non-trivial neighboring nodes to produce a similarity matrix; and

clustering, using the one or more computing devices, similar nodes from set of first nodes using the similarity matrix.

2. The computer-implemented method of claim 1, wherein the trivial neighboring nodes are associated with a single node from among the set of first nodes and the non-trivial neighboring nodes are associated with two or more nodes from among the set of first nodes.

3. The computer-implemented method of claim 1, wherein transforming the neighbor list includes transforming the sets of neighboring nodes into sets that are indexed by neighboring node and that include the first nodes that the neighboring node corresponds to.

4. The computer-implemented method of claim 1, wherein transforming the neighbor list includes converting the neighbor list into an inverted index.

5. The computer-implemented method of claim 1, wherein comparing the first nodes that are associated with each of the non-trivial neighboring nodes to produce the similarity matrix includes determining a number of intersecting first nodes between the sets of neighboring nodes.

6. The computer-implemented method of claim 1, wherein clustering the similar nodes from the set of first nodes using the similarity matrix includes processing the similarity matrix to cluster the first nodes into clusters based on a predetermined similarity metric.

7. The computer-implemented method of claim 6, further comprising merging two or more of the clusters based on a predetermined cluster-to-cluster level of similarity.

8. A computer program product comprising a non-transitory computer-readable medium storing a computer-readable program, wherein the computer-readable program, when executed on a computer, causes the computer to perform operations comprising:

determining a set of first nodes in a social graph of a social network, the first nodes representing users of the social network;

generating a neighbor list including sets of neighboring nodes for each of the first nodes;

transforming the neighbor list to identify trivial neighboring nodes and non-trivial neighboring nodes;

comparing the first nodes that are associated with each of the non-trivial neighboring nodes to produce a similarity matrix; and

clustering similar nodes from set of first nodes using the similarity matrix.

9. The computer program product of claim 8, wherein the trivial neighboring nodes are associated with a single node from among the set of first nodes and the non-trivial neighboring nodes are associated with two or more nodes from among the set of first nodes.

10. The computer program product of claim 8, wherein transforming the neighbor list includes transforming the sets of neighboring nodes into sets that are indexed by neighboring node and that include the first nodes that the neighboring node corresponds to.

11. The computer program product of claim 8, wherein transforming the neighbor list includes converting the neighbor list into an inverted index.

12. The computer program product of claim 8, wherein comparing the first nodes that are associated with each of the non-trivial neighboring nodes to produce the similarity matrix includes determining a number of intersecting first nodes between the sets of neighboring nodes.

13. The computer program product of claim 8, wherein clustering the similar nodes from the set of first nodes using the similarity matrix includes processing the similarity matrix to cluster the first nodes into clusters based on a predetermined similarity metric.

14. The computer program product of claim 8, wherein the computer-readable program, when executed on a computer, further causes the computer to perform operations of:

merging two or more of the clusters based on a predetermined cluster-to-cluster level of similarity.

15. A system comprising:

one or more processors;

one or more memories storing instructions that, when executed by the one or more processors, cause the system to perform operations including;

determining a set of first nodes in a social graph of a social network, the first nodes representing users of the social network;

generating a neighbor list including sets of neighboring nodes for each of the first nodes;

transforming the neighbor list to identify trivial neighboring nodes and non-trivial neighboring nodes;

comparing the first nodes that are associated with each of the non-trivial neighboring nodes to produce a similarity matrix; and

clustering similar nodes from set of first nodes using the similarity.

16. The system of claim 15, wherein the trivial neighboring nodes are associated with a single node from among the set of first nodes and the non-trivial neighboring nodes are associated with two or more nodes from among the set of first nodes.

17. The system of claim 15, wherein transforming the neighbor list includes transforming the sets of neighboring nodes into sets that are indexed by neighboring node and that include the first nodes that the neighboring node corresponds to.

18. The system of claim 15, wherein transforming the neighbor list includes converting the neighbor list into an inverted index.

19. The system of claim 15, wherein comparing the first nodes that are associated with each of the non-trivial neighboring nodes to produce the similarity matrix includes determining a number of intersecting first nodes between the sets of neighboring nodes.

20. The system of claim 15, wherein clustering the similar nodes from the set of first nodes using the similarity matrix includes processing the similarity matrix to cluster the first nodes into clusters based on a predetermined similarity metric.

21. The system of claim 15, wherein the instructions, when executed by the one or more processors, further cause the system to perform operations including:

merging two or more of the clusters based on a predetermined cluster-to-cluster level of similarity.