Arranging stories on newsfeeds based on expected value scoring on a social networking system

• US 9,378,529 B2
• Filed: 12/14/2012
• Issued: 06/28/2016
• Est. Priority Date: 12/14/2012
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Rubinstein, Yigal Dan, Vickrey, David, Cathcart, Robert William, Backstrom, Lars Seren, Thibaux, Romain Jean
• Primary Examiner(s): Le, Thu-Nguyet
• Assistant Examiner(s): Sultana, Nargis
• Application Number:
  US13/715,999
• Publication Number:
  US 20140172875A1
• Time in Patent Office: 1,292 Days
• Field of Search: 707/748
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

A social networking system generates a newsfeed for a user to view when accessing the social networking system. Candidate stories associated with users of the social networking system are selected and an expected value score for each candidate story is determined. An expected value score is based on the probability of a user performing various types of interactions with a candidate story and a numerical value for each type of interaction. The numerical value for a type of interaction represents a value to the social networking system of the type of interaction. Based on the expected value scores, the candidate stories are ranked and the ranking used to select candidate stories for the newsfeed.

Claims

1. A method comprising:

receiving a request from a viewing user of a social networking system for a newsfeed;

selecting at least two candidate stories for the viewing user, the at least two candidate stories associated with a plurality of other users of the social networking system with whom the viewing user has established a connection;

receiving, for each of a plurality of types of interaction that the viewing user may have with each candidate story, a value to the social networking system of the viewing user performing the type of interaction on a candidate story;

for each of the plurality of types of interaction, determining a probability of the viewing user performing the type of interaction on a candidate story;

computing an expected value score for each of the selected at least two candidate stories, the expected value score based on;

for each of the plurality of types of interaction,

(1) the probability of the viewing user performing the type of interaction on a candidate story, and

(2) the value to the social networking system of the viewing user performing the type of interaction on a candidate story;

ranking the selected at least two candidate stories based at least in part on the expected value scores;

generating a newsfeed comprising one or more of the candidate stories, the generated newsfeed based at least in part on the ranking; and

sending the generated newsfeed for display to the viewing user.

2. The method of claim 1, wherein a type of interaction is selected from a group consisting of:

viewing a story, expressing a preference for the story, accessing the story, providing a comment associated with the story, accessing the story, sharing the story with another user, and any combination thereof.

3. The method of claim 1, wherein determining the probability that the viewing user performing the type of interaction on the candidate story comprises:

identifying one or more story attributes of the candidate story;

identifying one or more stories with which the user previously interacted having at least a threshold number of story attributes matching story attributes of the candidate story;

determining a number of interactions by the viewing user with the identified one or more stories;

determining a number of interactions having the type of interaction by the viewing user with the identified one or more stories; and

calculating the probability based on the number of interactions by the viewing user with the identified one or more stories and number of interactions having the type of interaction by the viewing user with the identified one or more stories.

4. The method of claim 3, wherein a story attribute is selected from a group consisting of:

a story type, story content, a type of connection between the viewing user and a user associated with the story, the user associated with the story, a time associated with the story, and any combination thereof.

5. The method of claim 4, wherein the story type is selected from a group consisting of:

a link, a photo, a video, an event, a comment, a note, a status updates, and any combination thereof.

6. The method of claim 1, wherein values for each of the plurality of types of interaction are specified by the social networking system.

7. The method of claim 1, wherein computing the expected value score for each of the selected at least two candidate stories comprises:

for each of the plurality of types of interaction, calculating a product of a value for a type of interaction and a probability that the viewing user will perform the type of interaction on the candidate story; and

calculating a sum of the products.

8. The method of claim 1, wherein generating the newsfeed comprises:

ordering the one or more candidate stories included in the newsfeed based at least in part on the ranking.

9. The method of claim 1, wherein ranking the selected at least two candidate stories based at least in part on the expected value scores comprises:

ranking the selected at least two candidate stories so candidate stories having higher expected value scores have a higher position in the ranking.

10. A method comprising:

receiving a plurality of posts of content from users of an online system;

receiving a request from a viewing user of the online system for posts associated with a plurality of other users of the online system;

selecting at least two candidate posts for the viewing user, the at least two candidate posts associated with one or more other users of the online system;

receiving, for each of a plurality of types of interaction that the viewing user may have with each candidate story, a value to the social networking system of the viewing user performing the type of interaction on a candidate story;

for each of the plurality of types of interaction, determining a probability of the viewing user performing the type of interaction on a candidate story;

computing an expected value score for each of the selected at least two candidate stories, the expected value score based on;

for each of the plurality of types of interaction,

(1) the probability of the viewing user performing the type of interaction on a candidate story, and

(2) the value to the social networking system of the viewing user performing the type of interaction on a candidate story;

ranking the selected at least two candidate posts based at least in part on the expected value scores;

selecting a set of the candidate posts based at least in part on the ranking; and

sending the selected candidate posts for display to the viewing user.

11. The method of claim 10, wherein the online system is an online shopping system.

12. The method of claim 10, wherein determining the probability that the viewing user performing perform each of the plurality of types of interactions on the candidate post comprises:

identifying one or more attributes of the candidate post;

identifying one or more posts with which the user previously interacted having at least a threshold number of attributes matching story attributes of the candidate post;

for each of the plurality of types of interactions;

determining a number of interactions by the viewing user with the identified one or more posts;

determining a number of interactions having a type of interaction by the viewing user with the identified one or more posts; and

calculating the probability based on the number of interactions by the viewing user with the identified one or more posts and number of interactions having the type of interaction by the viewing user with the identified one or more posts.

13. The method of claim 10, wherein values for each of the plurality of types of interaction are specified by the online system.

14. The method of claim 10, wherein computing the expected value score for each of the selected at least two candidate posts comprises:

for each of the plurality of types of interaction, calculating a product of a value for a type of interaction and a probability that the viewing user will perform the type of interaction on the candidate post; and

calculating a sum of the products.

15. The method of claim 10, wherein selecting the set of the candidate posts comprises:

ordering the one or more candidate posts included in the set of candidate posts based at least in part on the ranking.

16. The method of claim 10, wherein ranking the selected at least two candidate posts based at least in part on the expected value scores comprises:

ranking the plurality of candidate posts so candidate posts having higher expected value scores have a higher position in the ranking.

17. A computer program product comprising a non-transitory computer readable storage medium having instructions encoded therein that, when executed by a processor, cause the processor to:

receive a request from a viewing user of a social networking system for a newsfeed;

select at least two candidate stories for the viewing user, the at least two candidate stories associated with a plurality of other users of the social networking system with whom the viewing user has established a connection;

receive, for each of a plurality of types of interaction that the viewing user may have with each candidate story, a value to the social networking system of the viewing user performing the type of interaction on a candidate story;

for each of the plurality of types of interaction, determine a probability of the viewing user performing the type of interaction on a candidate story;

compute an expected value score for each of the selected at least two candidate stories, the expected value score based on;

for each of the plurality of types of interaction,

(1) the probability of the viewing user performing the type of interaction on a candidate story, and

(2) the value to the social networking system of the viewing user performing the type of interaction on a candidate story;

rank the selected at least two candidate stories based at least in part on the expected value scores;

generate a newsfeed comprising one or more of the candidate stories, the generated newsfeed based at least in part on the ranking; and

send the generated newsfeed for display to the viewing user.

18. The computer program product of claim 17, wherein a type of interaction is selected from a group consisting of:

viewing a story, expressing a preference for the story, accessing the story, providing a comment associated with the story, accessing the story, sharing the story with another user, and any combination thereof.

19. The computer program product of claim 17, wherein the instructions to compute the expected value score for each of the selected at least two candidate stories further comprise instructions to:

for each of the plurality of types of interaction, calculate a product of a value for a type of interaction and a probability that the viewing user will perform the type of interaction on the candidate story; and

calculate a sum of the products.

20. A computer program product comprising a non-transitory computer readable storage medium having instructions encoded therein that, when executed by a processor, cause the processor to:

receive a plurality of posts of content from users of an online system;

receive a request from a viewing user of the online system for posts associated with a plurality of other users of the online system;

select at least two candidate posts for the viewing user, the at least two candidate posts associated with one or more other users of the online system;

receive, for each of a plurality of types of interaction that the viewing user may have with each candidate story, a value to the social networking system of the viewing user performing the type of interaction on a candidate story;

for each of the plurality of types of interaction, determine a probability of the viewing user performing the type of interaction on a candidate story;

compute an expected value score for each of the selected at least two candidate stories, the expected value score based on;

for each of the plurality of types of interaction,

(1) the probability of the viewing user performing the type of interaction on a candidate story, and

(2) the value to the social networking system of the viewing user performing the type of interaction on a candidate story;

rank the selected at least two candidate posts based at least in part on the expected value scores;

select a set of the candidate posts based at least in part on the ranking; and

send the selected candidate posts for display to the viewing user.