Formation and description of user subgroups
View Patent ↗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.
1. A computer-implemented method comprising:
for each user of a group 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 expressly specified 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 vector of the first sub-group based on the interest vectors of the users in the first sub-group;
identifying user characteristics corresponding to the centroid vector;
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 phrase;
identifying a plurality of the highest-ranking pages;
forming a textual description of the first sub-group comprising the topic phrases associated with the identified plurality of highest-ranking pages.
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:
computing first conditional probabilities that users would have an affinity for a particular page from the page affinity vector, given that the users have a particular interest from the interest vector;
computing second conditional probabilities that users would have a particular interest from the interest vector, given that the users have particular user characteristics; and
for each concept represented by the interest vector:
computing, using the first conditional probabilities and second conditional probabilities, 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. The computer-implemented method of claim 1 , wherein the interest vector is generated directly from the page affinity vector, without reference to prior values of the interest vector.
7. The computer-implemented method of claim 1 , wherein identifying the user characteristics corresponding to the centroid comprises averaging characteristics of users in the sub-group.
8. A computer system comprising:
a computer processor; and
a non-transitory computer-readable storage medium storing instructions executable by the processor, the instructions comprising:
instructions for, for each user of a group 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 expressly specified 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;
instructions for clustering the group of users into a plurality of sub-groups by applying a distance function to the interest vectors of the users;
instructions for, for a first sub-group of the plurality of sub-groups:
identifying a centroid vector of the first sub-group based on the interest vectors of the users in the first sub-group;
identifying user characteristics corresponding to the centroid vector;
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;
identifying a plurality of the highest-ranking pages;
forming a description of the first sub-group based on the topics associated with a plurality of the highest-ranking pages.
9. The computer system of claim 8 , wherein identifying the user characteristics corresponding to the centroid vector 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 system of claim 8 , wherein identifying the centroid of the first subgroup comprises averaging the interest vectors of the users in the first sub-group.
11. The computer system of claim 8 , 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 system of claim 11 , the instructions further comprising instructions for ranking each page of the plurality of pages using the computed conditional probabilities.
13. A non-transitory computer-readable storage medium storing instructions executable by a processor, the instructions comprising:
instructions for, for each user of a group 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 expressly specified 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;
instructions for clustering the group of users into a plurality of sub-groups by applying a distance function to the interest vectors of the users;
instructions for, for a first sub-group of the plurality of subgroups:
identifying a centroid vector of the first sub-group based on the interest vectors of the users in the first sub-group;
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 highest-ranking objects of the ranked objects.
14. The non-transitory computer-readable storage medium of claim 13 , wherein the objects are pages of the social networking system.
15. The non-transitory computer-readable storage medium of claim 13 , wherein identifying characteristics corresponding to the sub-group comprises:
identifying user characteristics corresponding to the centroid vector by weighting characteristics of the users in the sub-group according to their distances from the centroid vector.
16. The non-transitory computer-readable storage medium of claim 15 , wherein identifying the centroid vector of the first subgroup comprises averaging the interest vectors of the users in the first sub-group.