Video-related recommendations using link structure

• US 8,145,679 B1
• Filed: 12/13/2010
• Issued: 03/27/2012
• Est. Priority Date: 11/01/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Yagnik, Jay, Sivakumar, Dandapani, Jing, Yushi, Baluja, Shumeet
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): LODHI, ANDALIB FT
• Application Number:
  US12/966,747
• Time in Patent Office: 470 Days
• Field of Search: 707/713, 707/791, 707/796, 707/800, 707/802, 707/803
• US Class Current: 707/802
• CPC Class Codes: G06F 16/437 Administration of user profiles, e.g. generation, initialisation, adaptation, distribution
• CPC Class Codes: G06F 16/735 Filtering based on additional data, e.g. user or group profiles
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

The subject matter of this specification can be embodied in, among other things, a method that includes inferring labels for videos, users, advertisements, groups of users, and other entities included in a social network system. The inferred labels can be used to generate recommendations such as videos or advertisements in which a user may be interested. Inferred labels can be generated based on social or other relationships derived from, for example, profiles or activities of social network users. Inferred labels can be advantageous when explicit information about these entities is not available. For example, a particular user may not have clicked on any online advertisements, so the user is not explicitly linked to any advertisements.

Claims

1. A computer-implemented method comprising:

receiving, at a computer system, user information associated with users of a social network and associated with media accessed by the users;

generating, by the computer system, a graph that links first representations of the users and second representations of the media based on relationships derived from the user information, wherein the first representations and the second representations comprise nodes in the graph that are linked by edges;

selecting one or more advertising labels that are descriptive of one or more advertisements;

iteratively propagating values for the one or more advertising labels among the first representations of the users and the second representations of the media using the graph that links the first representations and the second representations; and

identifying an advertisement to provide in association with a particular representation based, at least in part, on magnitudes of one or more advertising label values for the particular representation that were determined by the iterative propagation, wherein the magnitudes of the one or more advertising label values indicate how likely a user is to select one or more corresponding advertisements, wherein the particular representation comprises a representation of a particular user of the social network, and wherein the advertisement is selected for presentation in a document that is to be presented to the particular user.

2. The method of claim 1, wherein, for a particular node in the graph, the iteratively propagating comprises iteratively combining values for the one or more advertising labels that are associated with one or more neighboring nodes, wherein the one or more neighboring nodes are linked to the particular node by one or more of the edges.

3. The method of claim 2, wherein the graph includes one or more ad nodes that represent the one or more advertisements, and wherein at least a portion of the edges that link the one or more ad nodes to other nodes in the graph represent selections or impressions of the one or more advertisements in association with entities represented by the other nodes.

4. The method of claim 2, wherein one or more dummy label values are used during the iterative propagation to limit distances by which the values are propagated across the graph.

5. The method of claim 1, wherein the user information associated with the users of the social network comprises user identifiers, group identifiers for groups of users, demographic information for the users, and activity indicators that specify how active users are on the social network.

6. The method of claim 1, wherein the user information associated with the media accessed by the users includes information about videos watched by users, genres associated with the videos, advertisements (ads) selected by or displayed to users, email communications sent or received by the users, and comments posted or read by the users.

7. The method of claim 1, wherein the relationships derived from the user information comprise friendships specified on user profiles, common membership in communities or groups on the social network, common genre classifications, common ads selected by the users, common classifications inferred from demographic information specified on user profiles, inferred relationships based on a first user posting content to a second user'"'"'s web page, or relationships inferred from users'"'"' access to media.

8. The method of claim 1, wherein relationships among the first and second representations are weighted based on user ratings of the media or a number of times users accessed the media, a correlation of media to a genre based on user or online database ratings, whether video media includes advertising media, a correlation of video media to advertising media based on advertisers'"'"' input or the video media authors'"'"' input, whether users list each other as friends on a social network, or how active a particular user is on the social network.

9. The method of claim 8, wherein the weighting affects a determination of the one or more advertising label values for the particular representation.

10. The method of claim 1, wherein the document comprises a page of the social network that the particular user has requested.

11. The method of claim 1, wherein the document comprises a page of a third-party website that includes an area that is reserved for information regarding the social network, wherein the page has been requested by the particular user.

12. The method of claim 1, wherein the particular representation further comprises a representation of a particular video, and wherein the advertisement is selected for presentation in the document further based on the document including the particular video.

13. The method of claim 12, wherein the document comprises a page of a third-party website that includes the particular video, wherein the page has been requested by the particular user.

14. A computer-implemented method comprising:

receiving, at a computer system, user information associated with users of a social network and associated with videos accessed by the users;

generating, by the computer system, a graph that links graph nodes based on relationships derived from the user information, the graph nodes comprising i) user nodes representing the users, ii) ad nodes representing advertisements, and iii) video nodes representing the videos, wherein the graph includes edges that link the graph nodes together and that represent relationships among the graph nodes;

selecting one or more advertising labels to associate with the at least a portion of graph nodes, wherein the one or more advertising labels are descriptive of one or more advertisements;

iteratively propagating values for the one or more advertising labels among the graph nodes using the edges; and

identifying an advertisement to provide in association with a first graph node based, at least in part, on magnitudes of one or more advertising label values for the first graph node that were determined by the iterative propagation, wherein the magnitudes of the one or more advertising label values indicate how likely a user is to select one or more corresponding advertisements, wherein the first graph node comprises a user node that represents a particular user of the social network, and wherein the advertisement is selected for presentation in a document that is to be presented to the particular user.

15. A system comprising:

a computer system;

an interface of the computer system to receive social network information associated with users of a social network and media accessed by the users;

a data structure generator of the computer system to generate a graph that includes representations of entities associated with the social network and that links the representations based on relationships derived from the social network information, wherein the representations comprise nodes in the graph that are linked by edges;

an inferred label generator of the computer system i) to select one or more advertising labels that are descriptive of one or more advertisements, and ii) to iteratively propagate values for the one or more advertising labels among the representations of the entities associated with the social network using the graph; and

an ad server of the computer system to identify an advertisement to provide in association with a particular representation based, at least in part, on magnitudes one or more advertising label values for the particular representation that were determined by the iterative propagation, wherein the magnitudes of the one or more advertising label values indicate how likely a user is to select one or more corresponding advertisements, wherein the particular representation comprises a representation of a particular user of the social network, and wherein the advertisement is selected for presentation in a document that is to be presented to the particular user.

16. The system of claim 15, wherein the document comprises a page of the social network that the particular user has requested.

17. The system of claim 15, wherein the document comprises a page of a third-party website that includes an area that is reserved for information regarding the social network, wherein the page has been requested by the particular user.

18. The system of claim 15, wherein the particular representation further comprises a representation of a particular video, and wherein the advertisement is selected for presentation in the document further based on the document including the particular video.

19. The system of claim 18, wherein the document comprises a page of a third-party website that includes the particular video, wherein the page has been requested by the particular user.