Inferring User Interests

• US 20080275861A1
• Filed: 05/01/2007
• Published: 11/06/2008
• Est. Priority Date: 05/01/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Sivakumar, Dandapani, Jing, Yushi, Baluja, Shumeet, Yagnik, Jay
• Granted Patent: US 8,055,664 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06Q 30/0274 Split fees

Abstract

The subject matter of this specification can be embodied in, among other things, a method that includes determining, for a portion of users of a social network, label values each comprising an inferred interest level of a user in a subject indicated by a label, associating a first user with one or more second users based on one or more relationships specified by the first user, and outputting a first label value for the first user based on one or more second label values of the one or more second users.

Claims

1. A computer-implemented method comprising:

determining, for a portion of users of a social network, label values each comprising an inferred interest level of a user in a subject indicated by a label;

associating a first user with one or more second users based on one or more relationships specified by the first user; and

outputting a first label value for the first user based on one or more second label values of the one or more second users.

2. The method of claim 1, wherein the first label comprises a revised label value of a previous label value that was assigned to the user.

3. The method of claim 1, wherein the first user is associated with the one or more second users through a common group membership.

4. The method of claim 1, further comprising identifying labels that specify potential interests of users.

5. The method of claim 1, wherein determining label values for the portion of users comprises classifying users with the label values using machine learning algorithms to classify text written by a user to infer label values to associate with the user.

6. The method of claim 5, wherein the text written by the user comprises text on a social network profile of the user, textual posts made by the user, and content of electronic documents associated a group of which the user is a member.

7. The method of claim 1, wherein the one or more social relationships specified by the first user comprise a group membership or a friendship.

8. The method of claim 1, wherein the label comprises advertising keywords selected by advertisers, non-advertising keywords based on content of profiles and not selected by advertisers, text associated with advertisements a user previously selected, or categories that encompasses a plurality of either advertising or non-advertising keywords.

9. The method of claim 1, further comprising generating a first graph comprising nodes for each user of the social network system, wherein the nodes are linked based on the social relationships specified by the users.

10. The method of claim 9, wherein the first graph further comprises nodes associated with label values selected from a group consisting of group nodes representing groups of users, label nodes representing labels, advertiser nodes representing advertisers, and Adgroup nodes representing advertising keyword groups.

11. The method of claim 10, further comprising determining label values for a portion of the nodes the first graph, the determination comprising for each node of the portion, adding the node'"'"'s current label value to a weighted value of a neighboring node'"'"'s label value, for each neighboring node.

12. The method of claim 11, wherein the weighted value is based on an edge that links the nodes.

13. The method of claim 11, wherein neighboring nodes comprise label nodes that have static label values used to determine the label values for the portion.

14. The method of claim 11, wherein the label values for each node of the portion of the nodes is initialized to a starting value before the determination of the label values for the node.

15. The method of claim 14, wherein the starting value is zero.

16. The method of claim 10, further comprising linking user nodes associated with users to label nodes based on whether the users have inferred interests in the subjects indicated by the labels.

17. The method of claim 10, wherein the nodes are further linked based on relationships specified by the advertisers, relationships specified by an advertisement server, or relationships specified by a text classification algorithm.

18. The method of claim 9, further comprising generating a second graph having nodes associated with the users of the social network, wherein the label values are assigned to the nodes using label nodes having a plurality of static label values.

19. The method of claim 18, further comprising determining label values for output using both the first and second graph.

20. The method of claim 19, further comprising selecting final label values for the first user by excluding the label values generated one of the graphs, by weighting the generated label values equally, or by weighting the generated label values based on a confidence measure that expresses a mathematical confidence in the accuracy of the label values generated by each of the graphs.

21. The method of claim 20, wherein the confidence measure is based on a comparison of a label value to an expected label value distribution.

22. The method of claim 1, further comprising determining the first label value based on the second label values.

23. The method of claim 1, further comprising assigning weights to each of the second label values based on a type of social relationship.

24. The method of claim 23, wherein the social relationship is selected from a group consisting of a uni-directional social relationship, a bi-directional social relationship, degree-of-separation social relationship, and a degree-of-page visitation social relationship.

25. The method of claim 23, wherein the weights are used to determine the contribution of the corresponding second label values when determining the first label value.

26. The method of claim 1, further comprising selecting an advertisement to display in association with the first user based on the first label.

27. The method of claim 1, further comprising outputting, for the first user, additional label values for different labels based on the one or more second label values of the second users.

28. The method of claim 27, further comprising selecting a label with the greatest label value to associate with the first user.

29. The method of claim 28, further comprising selecting an advertisement to display in association with the first user based on the selected label.

30. The method of claim 27, further comprising normalizing the first label value and additional label values for the first user.

31. The method of claim 1, further comprising determining label values to associate with entities comprising groups of users, groups of keywords selected by advertisers, advertisers, and individual keywords not selected by an advertiser.

32. The method of claim 31, further comprising normalizing the determined label values across all users and entities.

33. The method of claim 1, further comprising recursively outputting label values for the first user based on the one or more second users until a threshold is reached.

34. The method of claim 33, wherein the threshold is based on a convergence measure or a specified static value.

35. The method of claim 1, further comprising determining the first label value by starting a random walk algorithm from a first node in a graph representing the first user, the graph comprising nodes representing users, groups of users, labels, advertisers, advertising keyword groups, or combinations thereof.

36. The method of claim 35, wherein the random walk algorithm comprises recursively selecting additional nodes in the graph linked to previously selected nodes until a node is selected that is used as a label.

37. The method of claim 36, wherein the random walk algorithm comprises maintaining a count of the nodes that are used as labels.

38. The method of claim 37, wherein the first label value is based on the count maintained.

39. The method of claim 36, wherein the random walk algorithm further comprises recursively selecting all previously unselected users linked by specified relationships until all linked users have been traversed.

40. A computer-implemented method comprising:

generating a data structure that represents users of a social network as user nodes linked based on social relationships specified by the users;

associating, with a portion of the user nodes, one or more label values that characterize a user'"'"'s interest based on information about the user received from the social network system; and

outputting, for user nodes that lack adequate information about the corresponding users to determine a label value, label values based on neighboring label values associated with neighboring user nodes that are linked to the user nodes that lack the adequate information.

41. A system for inferring user interests comprising:

a classifying module for determining, for a portion of users of a social network, label values each comprising an inferred interest level of a user in a subject indicated by a label;

means for associating a first user with one or more second users based on one or more relationships specified by the first user; and

an interface for outputting a first label value for the first user based on one or more second label values of the one or more second users.

42. A computer-implemented method comprising:

identifying a relationship between a first and second user of a social network;

associating first information used to target advertising with the first user of a social network based on content generated by the first user;

inferring, based on the first information and the relationship, second information used to target advertising to the second user of the social network; and

outputting an advertisement for the second user based on the inferred second information.