Video-related recommendations using link structure

• US 8,533,236 B1
• Filed: 07/26/2012
• Issued: 09/10/2013
• Est. Priority Date: 11/01/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Baluja, Shumeet, Jing, Yushi, Sivakumar, Dandapani, Yagnik, Jay
• Primary Examiner(s): Breene, John E
• Assistant Examiner(s): LODHI, ANDALIB FT
• Application Number:
  US13/559,302
• Time in Patent Office: 411 Days
• Field of Search: 707/791, 707/796, 707/800, 707/802
• 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:

obtaining, by a computer system, information that identifies interactions among users of a social network;

generating, by the computer system, a graph that is based at least in part on the obtained information and comprises i) nodes that represent the users of the social network and ii) edges that connect the nodes and that represent relationships between the users;

assigning, to at least a portion of the nodes in the graph and for one or more labels, initial label values that indicate levels of interest of users associated with the portion of the nodes in content associated with the one or more labels;

determining, for the nodes in the graph, label values for the one or more labels based on iterative propagation of the initial label values among the nodes using the edges of the graph, wherein iterative propagation comprises, for a particular node from the nodes in the graph, determining particular label values for the particular node at each of a plurality of iterations by combining, at each of the plurality of iterations, neighboring label values for neighboring nodes that are connected to the particular node by a portion of the edges of the graph; and

identifying, by the computer system for a particular label from the one or more labels, one or more users to provide with particular content that is associated with the particular label, wherein the one or more users are identified based on the determined label values for the particular label.

2. The computer-implemented method of claim 1, further comprising:

determining levels of interaction between the users of the social network based on the identified information; and

assigning weights to at least a portion of the edges of the graph based on the determined levels of interaction,

wherein the label values are determined using the weights that are assigned to the edges of the graph.

3. The computer-implemented method of claim 2, wherein the levels of interaction are determined based on, at least, frequencies with which the users visit profile pages for other users of the social network.

4. The computer-implemented method of claim 2, wherein the levels of interaction are determined based on, at least, amounts of time that the users spend visiting profile pages for other users of the social network.

5. The computer-implemented method of claim 2, wherein the levels of interaction are determined based on, at least, whether the users commented on profile pages for other users of the social network.

6. The computer-implemented method of claim 2, wherein the levels of interaction are determined based on, at least, quantities or lengths of messages that the users sent to other users of the social network.

7. The computer-implemented method of claim 6, wherein the messages include one or more of:

email messages and instant messages.

8. The computer-implemented method of claim 1, wherein combining the neighboring label values comprises adding and normalizing the neighboring label values.

9. The computer-implemented method of claim 1, wherein the particular content comprises a video and the determined label values for the particular label indicate levels of interests of the users in the video.

10. The computer-implemented method of claim 9, wherein a particular initial label value for the particular label that is assigned to the at least a portion of the nodes indicates that one or more corresponding users previously viewed the video.

11. The computer-implemented method of claim 9, wherein a particular initial label value for the particular label that is assigned to the at least a portion of the nodes indicates that one or more corresponding users previously selected the advertisement.

12. The computer-implemented method of claim 1, wherein the particular content comprises an advertisement and the determined label values for the particular label indicate levels of interests of the users in the advertisement.

13. The computer-implemented method of claim 1, wherein the graph:

is further generated based on video access information that identifies i) videos that have been accessed by the users of the social network; and

ii) particular users who have accessed the videos; and

further comprises i) video nodes that represent the videos and ii) additional edges that connect the video nodes to at least a portion of the nodes and that represent the particular users having accessed the videos.

14. The computer-implemented method of claim 1, wherein the graph is further generated based on relationship information that identifies relationships among the users that the particular ones of the users have explicitly identified in association with the social network.

15. The computer-implemented method of claim 1, wherein the iterative propagation over the plurality of iterations causes the particular label values to be based, at least in part, on other label values for other nodes that are connected in the graph by the edges to the neighboring nodes and that are not connected in the graph by the edges to the particular node.

16. A computer system comprising:

one or more computing devices each comprising one or more processors and memory;

an interface of the one or more computing devices to obtain information that identifies interactions among users of a social network;

a data structure generator that is programmed to generate a graph based at least in part on the obtained information, wherein the graph comprises i) nodes that represent the users of the social network and ii) edges that connect the nodes and that represent relationships between the users; and

an inferred label generator that is programmed to;

assign initial label values for one or more labels to at least a portion of the nodes in the graph, wherein the initial label values indicate levels of interest of users associated with the portion of the nodes in content associated with the one or more labels;

determine, for the nodes in the graph, label values for the one or more labels based on iterative propagation of the initial label values among the nodes using the edges of the graph, wherein iterative propagation comprises, for a particular node from the nodes in the graph, determining particular label values for the particular node at each of a plurality of iterations by combining, at each of the plurality of iterations, neighboring label values for neighboring nodes that are connected to the particular node by a portion of the edges of the graph; and

identify, for a particular label from the one or more labels, one or more users to provide with particular content that is associated with the particular label, wherein the one or more users are identified based on the determined label values for the particular label.

17. The computer system of claim 16, further comprising:

a relationship determination module that is programmed to determine levels of interaction between the users of the social network based on the identified information, and to assign weights to at least a portion of the edges of the graph based on the determined levels of interaction;

wherein the label values are determined by the inferred label generator using the weights that are assigned to the edges of the graph.

18. The computer system of claim 17, wherein the levels of interaction are determined based on, at least, frequencies with which the users visit profile pages for other users of the social network.

19. The computer system of claim 16, wherein particular label values for a particular node are determined by iteratively combining neighboring label values for one or more neighboring nodes that are connected to the particular node by one or more of the edges of the graph.

20. A computer program product embodied in a non-transitory computer-readable storage medium storing instructions that, when executed, cause a computer system that includes one or more processors to perform operations comprising:

obtaining information that identifies interactions among users of a social network;

generating a graph based at least in part on the obtained information and comprising i) nodes that represent the users of the social network and ii) edges that connect the nodes and that represent relationships between the users;

assigning initial label values for one or more labels to at least a portion of the nodes in the graph, wherein the initial label values indicate levels of interest of users associated with the portion of the nodes in content associated with the one or more labels;

determining, for the nodes in the graph, label values for the one or more labels based on iterative propagation of the initial label values among the nodes using the edges of the graph, wherein iterative propagation comprises, for a particular node from the nodes in the graph, determining particular label values for the particular node at each of a plurality of iterations by combining, at each of the plurality of iterations, neighboring label values for neighboring nodes that are connected to the particular node by a portion of the edges of the graph; and

identifying, for a particular label from the one or more labels, one or more users to provide with particular content that is associated with the particular label, wherein the one or more users are identified based on the determined label values for the particular label.