Inferring user interests

• US 8,055,664 B2
• Filed: 05/01/2007
• Issued: 11/08/2011
• 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
• Primary Examiner(s): Chbouki; Tarek
• Application Number:
  US11/742,995
• Publication Number:
  US 20080275861A1
• Time in Patent Office: 1,652 Days
• Field of Search: None
• US Class Current: 707/749
• 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, with a computer server system that includes one or more processors, initial label values for at least a portion of a group of users of a social network, wherein each of the label values indicates a probability that a user is interested in a subject indicated by a label;

associating a first user with a first plurality of users from the group of users and a second user with a second plurality of users from the group of users based on social relationships associated with the first user and the second user, respectively, wherein the first plurality of users includes the second user and the second plurality of users includes the first user;

determining label values for the first user and the second user based on bi-directional propagation of label values, wherein the bi-directional propagation of label values comprises;

determining a first label value for the first user based on a combination of label values for the first plurality of users including a label value for the second user; and

determining a second label value for the second user based on a combination of label values for the second plurality of users including the determined first label value for the first user; and

outputting the first label value for the first user and the second label value for the second user.

2. The method of claim 1, wherein the determined first label value for the first user comprises a revised label value of an initial label value that was assigned to the first user, revised based on the combination of the label values for the first plurality of users.

3. The method of claim 1, wherein the first user is associated with the first plurality of 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 the initial label values for the at least a portion of the group of users comprises classifying users with the label values using machine learning techniques 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 with a group of which the user is a member.

7. The method of claim 1, wherein the social relationships associated with 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, wherein the nodes are linked based on the social relationships associated with the users of the social network.

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 nodes representing advertising keyword groups.

11. The method of claim 10, further comprising determining label values for a portion of the nodes of 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 an initial value before the determination of the label values for the node.

15. The method of claim 14, wherein the initial 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 by 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 assigning weights to each of the label values for the first plurality of users based on a type of social relationship between the first user and each of the first plurality of users.

23. The method of claim 22, 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.

24. The method of claim 22, wherein the weights are used to determine a contribution of the corresponding label values for the first plurality of users when determining the first label value.

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

26. The method of claim 1, further comprising outputting, for the first user, additional label values for different labels based on the label values for the first plurality of users.

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

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

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

30. 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.

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

32. The method of claim 1, wherein the label values are determined by iteratively performing the bi-directional propagation of label values until a threshold is reached.

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

34. The method of claim 1, further comprising determining the first label value by starting a random walk technique 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.

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

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

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

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

39. The computer-implemented method of claim 1, wherein an initial label value for a user is determined based on information associated with the user'"'"'s profile on the social network and information associated with the user'"'"'s activity related to the social network.

40. A system for inferring user interests comprising:

one or more processors;

a classifying module for determining initial label values for at least a portion of a group of users of a social network, wherein each of the label values indicates a probability that a user is interested in a subject indicated by a label;

means for associating a first user with a first plurality of users from the group of users and a second user with a second plurality of users from the group of users based on relationships associated with the first user and the second user, respectively, wherein the first plurality of users includes the second user and the second plurality of users includes the first user;

means for determining label values for the first user and the second user based on bidirectional propagation of label values, wherein the bi-directional propagation of label values causes (i) a first label value for the first user to be determined based on a combination of label values for the first plurality of users including a label value for the second user, and (ii) a second label value for the second user to be determined based on a combination of label values for the second plurality of users including the determined first label value for the first user; and

an interface for outputting the first label value for the first user and the second label value for the second user.

41. The system of claim 40, wherein determining the initial label values for the at least a portion of the group of users comprises classifying users with the label values using machine learning techniques to classify text written by a user to infer label values to associate with the user.

42. The system of claim 41, 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 with a group of which the user is a member.

43. The system of claim 40, wherein the bi-direction propagation of label values causes weights to be assigned to each of the label values for the first plurality of users based on a type of social relationship between the first user and each of the first plurality of users.

44. The system of claim 43, 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.

45. The system of claim 43, wherein the weights are used to determine a contribution of the corresponding label values for the first plurality of users when determining the first label value.

46. The system of claim 40, wherein the label values are determined by iteratively performing the bi-directional propagation of label values until a threshold is reached.

47. The system of claim 46, wherein the threshold is based on a convergence measure or a specified static value.

48. A computer program product tangibly embodied in a non-transitory computer storage device storing instructions that, when executed, cause a processor to perform operations comprising:

determining initial label values for at least a portion of a group of users of a social network, wherein each of the label values indicates a probability that a user is interested in a subject indicated by a label;

associating a first user with a first plurality of users from the group of users and a second user with a second plurality of users from the group of users based on social relationships associated with the first user and the second user, respectively, wherein the first plurality of users includes the second user and the second plurality of users includes the first user;

determining label values for the first user and the second user based on bi-directional propagation of label values, wherein the bi-directional propagation of label values comprises;

determining a first label value for the first user based on a combination of label values for the first plurality of users including a label value for the second user; and

determining a second label value for the second user based on a combination of label values for the second plurality of users including the determined first label value for the first user; and

outputting the first label value for the first user and the second label value for the second user.

49. The computer program product of claim 48, wherein the social relationships associated with the first user comprise a group membership or a friendship.

50. The computer program product of claim 48, 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.

51. The computer program product of claim 48, wherein the operations further comprise generating a first graph comprising nodes for each user of the social network, wherein the nodes are linked based on the social relationships associated with the users of the social network.

52. The computer program product of claim 51, 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 nodes representing advertising keyword groups.

53. The computer program product of claim 52, wherein the operation further comprise determining label values for a portion of the nodes of 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.

54. The computer program product of claim 53, wherein the weighted value is based on an edge that links the nodes.

55. The computer program product of claim 52, 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.

56. The computer program product of claim 51, wherein the operations further comprise 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.

57. The computer program product of claim 56, wherein the operation further comprise determining label values for output using both the first and second graph.

58. The computer program product of claim 48, wherein the operation further comprise selecting an advertisement to display in association with the first user based on the determined first label value for the first user.

59. The computer program product of claim 48, wherein the operation further comprise outputting, for the first user, additional label values for different labels based on the label values for the first plurality of users.

60. The computer program product of claim 59, wherein the operations further comprise selecting a label with the greatest label value to associate with the first user;

and

selecting an advertisement to display in association with the first user based on the selected label.

61. The computer program product of claim 59, wherein the operation further comprise normalizing the first label value and additional label values for the first user.