Social identity clustering

• US 8,626,835 B1
• Filed: 10/21/2010
• Issued: 01/07/2014
• Est. Priority Date: 10/21/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gyongyi, Zoltan I., Heymans, Maureen, Lopyrev, Mikhail, Roehrig, Hein
• Primary Examiner(s): Chan, Wing F
• Assistant Examiner(s): Thieu, Benjamin M.
• Application Number:
  US12/909,822
• Time in Patent Office: 1,174 Days
• Field of Search: 709/204, 709/223, 709/225, 707/1, 707/6, 707/102, 345/420, 345/440
• US Class Current: 709/204
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for social identity clustering. In one aspect, a method includes receiving a connection graph representing public social data, where the nodes represent social identities and each edge is either a “me” edge between identities claimed to belong to the same person or a “friend” edge between identities claimed to belong to different identities. The method further includes converting the graph to a cluster graph in which each node initially corresponds to a single node of the connection graph. The method further includes updating the cluster graph by iteratively merging cluster nodes based on an analysis of the weight of the “me” edges connecting them, and then replacing the merged cluster nodes within the graph with a new cluster node containing the merged cluster nodes, where the edges of the new cluster node are the aggregated edges of the merged cluster nodes.

Claims

1. A computer-implemented method executed using one or more processors, the method comprising:

receiving, by the one or more processors, a connection graph representing public social data comprising identity data and social link data, wherein the connection graph comprises nodes and directed edges, each edge connecting a pair of nodes, wherein each node represents an identity extracted from the public social data and each edge represents a social link extracted from the public social data from one identity to another different identity, wherein each node represents a distinct identity, and wherein each edge is a “

me”

edge if the edge represents a “

me”

social link between identities claimed by a link author as belonging to the same person or real-life entity, and a “

friend”

edge represents a “

friend”

social link between identities claimed by a link author as belonging to different persons or entities;

converting, at the one or more processors, the connection graph to a cluster graph, the cluster graph comprising clusters and cluster edges, each edge connecting a pair of clusters, each cluster corresponding to one or more nodes of the connection graph, and each edge of the cluster graph corresponding to one or more edges of the connection graph, wherein each cluster of the cluster graph initially corresponds to a single node of the connection graph and each edge of the cluster graph initially corresponds to a single edge of the connection graph; and

clustering, at the one or more processors, identities by iteratively performing the following actions (i) and (ii) until no pair of clusters exists in the cluster graph that satisfies the threshold fraction condition of action (ii);

(i) identifying all outgoing “

me”

edges from a first cluster and all “

me”

edges to a second cluster, wherein each “

me”

edge has a respective weight; and

(ii) determining that the weights of all “

me”

edges from the first cluster to the second cluster are more than a threshold fraction of the weights of all outgoing “

me”

edges from the first cluster and as a consequence merging the first cluster and the second cluster to form a new cluster replacing the first and second clusters, wherein the edges of the new cluster node are aggregations of the edges of the former first cluster and the edges of the former second cluster, and wherein the new cluster represents the identities of the former first cluster and the identities of the former second cluster.

2. The method of claim 1, further comprising assigning weights to “

me”

edges, wherein a weight assigned to a “

me”

edge from a first node to a second node is determined from a reputation value assigned to the first node and a measure of textual similarity between a user name associated with the identity represented by the first node and a user name associated with the identity represented by the second node.

3. The method of claim 2, wherein the measure of textual similarity is one of two or more predetermined values.

4. The method of claim 2, wherein the measure of textual similarity is computed by applying a comparison function.

5. The method of claim 4 wherein the comparison function is an edit distance function.

6. The method of claim 1 wherein the “

me”

edges connecting the first cluster and the second cluster are replaced with a single replacement “

me”

edge, and the replacement “

me”

edge weight is a sum of the weights of the replaced “

me”

edges.

7. The method of claim 1, further comprising:

cleaning the connection graph by removing erroneous nodes and edges before converting the connection graph to the cluster graph.

8. The method of claim 7, wherein cleaning the connection graph comprises:

removing a node from the connection graph because the node is on an exclusion list from the connection graph.

9. The method of claim 7, wherein cleaning the connection graph further comprises:

removing a node and the “

me”

edges of the node from the connection graph because a total number of incoming “

me”

edges to the node exceeds an in-degree threshold value or a total number of outgoing “

me”

edges from the node exceeds an out-degree threshold value.

10. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving a connection graph representing public social data comprising identity data and social link data, wherein the connection graph comprises nodes and directed edges, each edge connecting a pair of nodes, wherein each node represents an identity extracted from the public social data and each edge represents a social link extracted from the public social data from one identity to another different identity, wherein each node represents a distinct identity, and wherein each edge is a “

me”

edge if the edge represents a “

me”

social link between identities claimed by a link author as belonging to the same person or real-life entity, and a “

friend”

edge represents a “

friend”

social link between identities claimed by a link author as belonging to different persons or entities;

converting the connection graph to a cluster graph, the cluster graph comprising clusters and cluster edges, each edge connecting a pair of clusters, each cluster corresponding to one or more nodes of the connection graph, and each edge of the cluster graph corresponding to one or more edges of the connection graph, wherein each cluster of the cluster graph initially corresponds to a single node of the connection graph and each edge of the cluster graph initially corresponds to a single edge of the connection graph; and

clustering identities by iteratively performing the following actions (i) and (ii) until no pair of clusters exists in the cluster graph that satisfies the threshold fraction condition of action (ii);

(i) identifying all outgoing “

me”

edges from a first cluster and all “

me”

edges to a second cluster, wherein each “

me”

edge has a respective weight; and

(ii) determining that the weights of all “

me”

edges from the first cluster to the second cluster are more than a threshold fraction of the weights of all outgoing “

me”

edges from the first cluster and as a consequence merging the first cluster and the second cluster to form a new cluster replacing the first and second clusters, wherein the edges of the new cluster node are aggregations of the edges of the former first cluster and the edges of the former second cluster, and wherein the new cluster represents the identities of the former first cluster and the edges of the former second cluster.

11. A system comprising:

one or more computers and one or more storage devices storing instructions that when executed by the one or more computers cause the one or more computers to perform operations comprising;

receiving a connection graph representing public social data comprising identity data and social link data, wherein the connection graph comprises nodes and directed edges, each edge connecting a pair of nodes, wherein each node represents an identity extracted from the public social data and each edge represents a social link extracted from the public social data from one identity to another different identity, wherein each node represents a distinct identity, and wherein each edge is a “

me”

edge if the edge represents a “

me”

social link between identities claimed by a link author as belonging to the same person or real-life entity, and a “

friend”

edge represents a “

friend”

social link between identities claimed by a link author as belonging to different persons or entities;

converting the connection graph to a cluster graph, the cluster graph comprising clusters and cluster edges, each edge connecting a pair of clusters, each cluster corresponding to one or more nodes of the connection graph, and each edge of the cluster graph corresponding to one or more edges of the connection graph, wherein each cluster of the cluster graph initially corresponds to a single node of the connection graph and each edge of the cluster graph initially corresponds to a single edge of the connection graph; and

clustering identities by iteratively performing the following actions (i) and (ii) until no pair of clusters exists in the cluster graph that satisfies the threshold fraction condition of action (ii);

(i) identifying all outgoing “

me”

edges from a first cluster and all “

me”

edges to a second cluster, wherein each “

me”

edge has a respective weight; and

(ii) determining that the weights of all “

me”

edges from the first cluster to the second cluster are more than a threshold fraction of the weights of all outgoing “

me”

edges from the first cluster and as a consequence merging the first cluster and the second cluster to form a new cluster replacing the first and second clusters, wherein the edges of the new cluster node are aggregations of the edges of the former first cluster and the edges of the former second cluster, and wherein the new cluster represents the identities of the former first cluster and the edges of the former second cluster.

12. The system of claim 11, wherein the operations further comprise assigning weights to “

me”

edges, wherein a weight assigned to a “

me”

edge from a first node to a second node is determined from a reputation value assigned to the first node and a measure of textual similarity between a user name associated with the identity represented by the first node and a user name associated with the identity represented by the second node.

13. The system of claim 12, wherein the measure of textual similarity is one of two or more predetermined values.

14. The system of claim 12, wherein the measure of textual similarity is computed by applying a comparison function.

15. The system of claim 14, wherein the comparison function is an edit distance function.

16. The system of claim 11, wherein the “

me”

edges connecting the first cluster and the second cluster are replaced with a single replacement “

me”

edge, and the replacement “

me”

edge weight is a sum of the weights of the replaced “

me”

edges.

17. The system of claim 11, wherein the operations further comprise:

cleaning the connection graph by removing erroneous nodes and edges before converting the connection graph to the cluster graph.

18. The system of claim 17, wherein cleaning the connection graph comprises:

removing a node from the connection graph because the node is on an exclusion list from the connection graph.

19. The system of claim 17, wherein cleaning the connection graph further comprises:

removing a node and the “

me”

edges of the node from the connection graph because a total number of incoming “

me”

edges to the node exceeds an in-degree threshold value or a total number of outgoing “

me”

edges from the node exceeds an out-degree threshold value.