Generating suggestions for user groups in social networks

• US 8,977,649 B1
• Filed: 10/19/2012
• Issued: 03/10/2015
• Est. Priority Date: 10/21/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Matias, Yossi, Barenholz, Tzvi Itzhak, Leichtberg, Ari J., Hassidim, Avinatan
• Primary Examiner(s): SYED, FARHAN M
• Application Number:
  US13/656,443
• Time in Patent Office: 872 Days
• US Class Current: 707/798
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06Q 30/0282 Rating or review of business operators or products
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

Implementations of the present disclosure include providing a suggested social circle includes generating a list of contacts who, based on first predetermined criteria, are to be considered for potential inclusion in a social circle to be suggested to a particular user and generating an edge and vertex-weighted graph representation that indicates a strength of the particular user'"'"'s affinity to each of the contacts. A set of vertices in the graph that has a high overall score based on predetermined factors is identified. After determining that the contacts corresponding to the identified set of vertices should be presented as a suggested social circle to the particular user, social circle data corresponding to the suggested social circle is transmitted, to a client device associated with the particular user, to display a representation of the suggested social circle on the client device.

Claims

1. A system comprising:

a processing device; and

a data store coupled to the processing device and having instructions stored thereon which, when executed by the processing device, cause the processing device to perform operations comprising;

generating a list of contacts who, based on first predetermined criteria, are to be considered for potential inclusion in a social circle to be suggested to a particular user;

determining, for each contact, an interaction score between the particular user and the contact, the interaction score indicating an extent of interactions between the particular user and the contact;

determining, for each contact, a similarity score between the particular user and the contact, the similarity score indicating an extent of similarities in profiles between the particular user and the contact;

determining, for each contact, a friendship score between the particular user and the contact, the friendship score indicating an extent to which the contact and the particular user are members of one another'"'"'s social circles;

determining, for each contact, a social score between the particular user and the contact, the social score indicating a number of other contacts who are members of at least one social circle for the particular user and the contact;

generating and storing an edge and vertex-weighted graph representation that indicates a strength of the particular user'"'"'s affinity to each of the contacts, wherein each vertex in the graph corresponds to a particular one of the contacts, and the weight of each edge connecting a pair of vertices is based on a weighted sum of the interaction score, the similarity score, the friendship score, and the social score;

identifying a set of vertices in the graph that has an overall score, based on at least on the weight of one or more edges of the edge and vertex-weighted graph and one or more predetermined factors, that exceeds a threshold;

determining that the contacts corresponding to the identified set of vertices should be presented as a suggested social circle to the particular user; and

transmitting social circle data corresponding to the suggested social circle to display a representation of the suggested social circle on a client device associated with the particular user.

2. The system of claim 1 wherein the predetermined factors to determine the overall score for a particular set of vertices include an initial score for the set that represents a strength of the particular user'"'"'s affinity to the contacts that correspond to the vertices in the set as a whole based on interactions between the particular user and the contacts that correspond to the vertices in the set.

3. The system of claim 1 wherein the predetermined factors to determine the overall score for a particular set of vertices include the set'"'"'s conductance.

4. The system of claim 1 wherein the predetermined factors to determine the overall score for a particular set of vertices include a sum of the weights of each of the vertices in the set.

5. The system of claim 1 wherein the predetermined factors to determine the overall score for a particular set of vertices include the size of the set.

6. The system of claim 5 wherein the predetermined factors to determine the overall score for a particular set of vertices include a preference for a set of particular size.

7. The system of claim 1 wherein the predetermined factors to determine the overall score for a particular set of vertices include:

an initial score for the set that represents a strength of the particular user'"'"'s affinity to the contacts that correspond to the vertices in the set as a whole based on interactions between the particular user and the contacts that correspond to the vertices in the set;

the set'"'"'s conductance;

a sum of the weights of each of the vertices in the set; and

a preference for a set of a particular size.

8. The system of claim 7 wherein the overall score of the set is based, at least in part, on a weighted sum of the set'"'"'s initial score, the set'"'"'s conductance, and the sum of the weights of the vertices in the set.

9. The system of claim 8 wherein the overall score of the set is based on the weighted sum multiplied by a factor that indicates the preference for a set of a particular size.

10. The system of claim 1 wherein the operation of identifying a set of vertices in the graph that has a high overall score includes:

(a) adding an additional vertex to a prior set of vertices to form a new set of vertices; and

(b) repeating (a) so long as the overall score of the new set increases relative to the prior set.

11. A method of providing a suggested social circle, the method comprising:

generating, by a server system, a list of contacts who, based on first predetermined criteria, are to be considered for potential inclusion in a social circle to be suggested to a particular user;

determining, for each contact, an interaction score between the particular user and the contact, the interaction score indicating an extent of interactions between the particular user and the contact;

determining, for each contact, a similarity score between the particular user and the contact, the similarity score indicating an extent of similarities in profiles between the particular user and the contact;

determining, for each contact, a friendship score between the particular user and the contact, the friendship score indicating an extent to which the contact and the particular user are members of one another'"'"'s social circles;

determining, for each contact, a social score between the particular user and the contact, the social score indicating a number of other contacts who are members of at least one social circle for the particular user and the contact;

generating, by the server system, an edge and vertex-weighted graph representation that indicates a strength of the particular user'"'"'s affinity to each of the contacts, wherein each vertex in the graph corresponds to a particular one of the contacts, and the weight of each edge connecting a pair of vertices is based on a weighted sum of the interaction score, the similarity score, the friendship score, and the social score;

identifying a set of vertices in the graph that has a high overall score based on at least on the weight of one or more edges of the edge and vertex-weighted graph and one or more predetermined factors;

determining that the contacts corresponding to the identified set of vertices should be presented as a suggested social circle to the particular user; and

transmitting, to a client device associated with the particular user, social circle data corresponding to the suggested social circle to display a representation of the suggested social circle on the client device.

12. The method of claim 11 wherein the predetermined factors to determine the overall score for a particular set of vertices include:

an initial score for the set that represents a strength of the particular user'"'"'s affinity to the contacts that correspond to the vertices in the set as a whole based on interactions between the particular user and the contacts that correspond to the vertices in the set;

the set'"'"'s conductance;

a sum of the weights of each of the vertices in the set; and

a preference for a set of a particular size.

13. The method of claim 12 wherein the overall score of the set is based, at least in part, on a weighted sum of the set'"'"'s initial score, the set'"'"'s conductance, and the sum of the weights of the vertices in the set.

14. The method of claim 13 wherein the overall score of the set is based on the weighted sum multiplied by a factor that indicates the preference for a set of a particular size.

15. The method of claim 11 wherein identifying a set of vertices in the graph that has a high overall score includes:

(a) adding an additional vertex to a prior set of vertices to form a new set of vertices; and

(b) repeating (a) so long as the overall score of the new set increases relative to the prior set.

16. A 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:

generating a list of contacts who, based on first predetermined criteria, are to be considered for potential inclusion in a social circle to be suggested to a particular user;

determining, for each contact, an interaction score between the particular user and the contact, the interaction score indicating an extent of interactions between the particular user and the contact;

determining, for each contact, a similarity score between the particular user and the contact, the similarity score indicating an extent of similarities in profiles between the particular user and the contact;

determining, for each contact, a friendship score between the particular user and the contact, the friendship score indicating an extent to which the contact and the particular user are members of one another'"'"'s social circles;

determining, for each contact, a social score between the particular user and the contact, the social score indicating a number of other contacts who are members of at least one social circle for the particular user and the contact;

generating an edge and vertex-weighted graph representation that indicates a strength of the particular user'"'"'s affinity to each of the contacts, wherein each vertex in the graph corresponds to a particular one of the contacts, and the weight of each edge connecting a pair of vertices is based on a weighted sum of the interaction score, the similarity score, the friendship score, and the social score;

identifying a set of vertices in the graph that has a high overall score based on at least on the weight of one or more edges of the edge and vertex-weighted graph and one or more predetermined factors;

determining that the contacts corresponding to the identified set of vertices should be presented as a suggested social circle to the particular user; and

transmitting, to a client device associated with the particular user, social circle data corresponding to the suggested social circle to display a representation of the suggested social circle on the client device.

17. The medium of claim 16 wherein the predetermined factors to determine the overall score for a particular set of vertices include:

an initial score for the set that represents a strength of the particular user'"'"'s affinity to the contacts that correspond to the vertices in the set as a whole based on interactions between the particular user and the contacts that correspond to the vertices in the set;

the set'"'"'s conductance;

a sum of the weights of each of the vertices in the set; and

a preference for a set of a particular size.

18. The medium of claim 17 wherein the overall score of the set is based, at least in part, on a weighted sum of the set'"'"'s initial score, the set'"'"'s conductance, and the sum of the weights of the vertices in the set.

19. The medium of claim 18 wherein the overall score of the set is based on the weighted sum and a factor that indicates the preference for a set of a particular size.

20. The medium of claim 17 wherein the operation of identifying a set of vertices in the graph that has a high overall score includes:

(a) adding an additional vertex to a prior set of vertices to form a new set of vertices; and

(b) repeating (a) so long as the overall score of the new set increases relative to the prior set.