FORMATION AND DESCRIPTION OF USER SUBGROUPS

• US 20140172855A1
• Filed: 12/19/2012
• Published: 06/19/2014
• Est. Priority Date: 12/19/2012
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Powell, Spencer, Arnoux, Boris
• Granted Patent: US 9,348,886 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

A system forms sub-groups from a given user group of a social networking system and form descriptions of the sub-groups that provide an intuitive understanding of sub-group composition, such as likings of the sub-groups. In one embodiment, a given user group of a social networking system is clustered into a plurality of sub-groups, and representative characteristics—such as the characteristics of a composite or actual member of the sub-group—are determined for each sub-group. In order to form sub-group descriptions, a set of objects, such as pages of the social networking system, is ranked with respect to the representative characteristics of the sub-group. The highest-ranking objects for a sub-group are then used to form the description of that sub-group. For example, the topics associated with each of the highest-ranking pages can be combined into the sub-group description.

Claims

1. A computer-implemented method comprising:

for each user of a training set of users of a social networking system;

generating an interest vector from a page affinity vector of the user, wherein;

the page affinity vector of the user indicates, for each page of a plurality of pages of the social networking system, whether the user has expressed an affinity for the page,

the interest vector indicates, for each concept of a plurality of concepts, whether the user is likely to have an interest in the concept, and

the interest vector has fewer elements than the page affinity vector;

clustering the group of users into a plurality of sub-groups by applying a distance function to the interest vectors of the users;

for a first sub-group of the plurality of subgroups;

identifying a centroid of the first sub-group;

identifying user characteristics corresponding to the centroid;

ranking each page of a plurality of pages on the social networking system with respect to the sub-group based on the identified user characteristics, each page having an associated topic phrase;

identifying a plurality of the highest-ranking objects;

forming a textual description of the sub-group comprising the topic phrases associated with the identified plurality of highest-ranking objects.

2. The computer-implemented method of claim 1, wherein identifying the centroid of the first subgroup comprises averaging the interest vectors of the users in the first sub-group.

3. The computer-implemented method of claim 2, wherein identifying the user characteristics corresponding to the user centroid comprises:

for each user in the first sub-group;

determining a distance of the user'"'"'s interest vector from the centroid using the distance function;

weighting user characteristics of the user based on the determined distance;

setting the user characteristics corresponding to the user centroid to a weighted average of the weighted user characteristics of the users in the first sub-group.

4. The computer-implemented method of claim 1, wherein ranking each page of the plurality of pages with respect to the first sub-group comprises:

for each concept represented by the interest vector;

computing a conditional probability that a user having the concept in the user'"'"'s interest vector will have an affinity for a given page.

5. The computer-implemented method of claim 4, further comprising ranking each page of the plurality of pages using the computed conditional probabilities.

6. A computer-implemented method comprising:

clustering a group of users of a social networking system into a plurality of sub-groups;

for a first sub-group of the plurality of sub-groups;

identifying a centroid of the first sub-group;

identifying user characteristics corresponding to the centroid;

ranking each page of a plurality of pages on the social networking system with respect to the first sub-group based on the identified user characteristics, each page having an associated topic;

forming a description of the first sub-group based on the topics associated with a plurality of the highest-ranking objects.

7. The computer-implemented method of claim 6, further comprising:

for each user of the group of users of the social networking system;

generating an interest vector from a page affinity vector of the user, wherein;

the page affinity vector of the user indicates, for each page of a plurality of pages of the social networking system, whether the user has expressed an affinity for the page,

the interest vector indicates, for each concept of a plurality of concepts, whether the user is likely to have an interest in the concept, and

the interest vector has fewer elements than the page affinity vector.

8. The computer-implemented method of claim 7, wherein clustering the group of users into the plurality of sub-groups comprises applying a distance function to pairs of the generated interest vectors.

9. The computer-implemented method of claim 8, wherein identifying the user characteristics corresponding to the user centroid comprises:

for each user in the first sub-group;

determining a distance of the user'"'"'s interest vector from the centroid using the distance function;

weighting user characteristics of the user based on the determined distance;

setting the user characteristics corresponding to the user centroid to a weighted average of the weighted user characteristics of the users in the first sub-group.

10. The computer-implemented method of claim 7, wherein identifying the centroid of the first subgroup comprises averaging the interest vectors of the users in the first sub-group.

11. The computer-implemented method of claim 7, wherein ranking each page of the plurality of pages with respect to the first sub-group comprises:

for each concept represented by the interest vector;

computing a conditional probability that a user having the concept in the user'"'"'s interest vector will have an affinity for a given page.

12. The computer-implemented method of claim 11, further comprising ranking each page of the plurality of pages using the computed conditional probabilities.

13. A computer-implemented method comprising:

clustering a group of users of a social networking system into a plurality of sub-groups;

for a first sub-group of the plurality of subgroups;

identifying characteristics corresponding to the first sub-group;

ranking each object of a plurality of objects with respect to the first sub-group based on the identified characteristics, each object having an associated topic;

forming a description of the first sub-group based on the topics associated with a plurality of the highest-ranking objects.

14. The computer-implemented method of claim 13, wherein the objects are pages of the social networking system.

15. The computer-implemented method of claim 13, wherein clustering the group of users into the plurality of sub-groups comprises applying a distance function to pairs of the generated interest vectors.

16. The computer-implemented method of claim 13, wherein identifying characteristics corresponding to the sub-group comprises:

identifying a centroid of the first sub-group; and

identifying user characteristics corresponding to the centroid by weighting characteristics of the users in the sub-group according to their distances from the centroid.

17. The computer-implemented method of claim 16, wherein identifying the centroid of the first subgroup comprises averaging the interest vectors of the users in the first sub-group.

18. The computer-implemented method of claim 13 wherein ranking each object of the plurality of object with respect to the first sub-group comprises:

for each concept represented by the interest vector;

computing a conditional probability that a user having the concept in the user'"'"'s interest vector will have an affinity for a given object.

19. The computer-implemented method of claim 18, further comprising ranking each object of the plurality of objects using the computed conditional probabilities.

20. A computer-implemented method comprising:

for each user of a training set of users of a social networking system;

generating, from a first vector of information about a user, a second vector of information about the user, the second vector having lower dimensionality than the first vector;

clustering the group of users into a plurality of sub-groups by applying a distance function to the second vectors of the users;

for a first sub-group of the plurality of sub-groups;

identifying user characteristics corresponding to the first sub-group;

ranking each object of a plurality of objects with respect to the first sub-group based on the identified characteristics;

forming a textual description of the sub-group based on highest-ranking ones of the ranked objects using topics corresponding to the first vectors.