Ordering content items in a feed based on heights associated with the content items

A social networking system selects and presents content items to a user via a feed. Additionally, the social networking system predicts heights associated with various content items, such as content items selected for presentation via the feed. Characteristics of a content item (e.g., a type of content included in the content item, a language of the content item, and a number of comments associated with the content item) as well as characteristics of a client device associated with the user are used to predict a height associated with the content item. When selecting content items for presentation to the user, the social networking system accounts for the predicted heights of various content items when ordering the content items in the news feed.

BACKGROUND

This disclosure relates generally to social networking systems, and in particular to presenting content to users of a social networking system via a feed.

Users of a social networking system share their interests and engage with other users of the social networking system by sharing or generating content items such as photographs, status updates, and playing social games. While this allows users to easily exchange information with other social networking system users, the amount of information gathered from users is staggering. This causes a social networking system to receive a large amount of information from users describing a wide range of events ranging from events including recent moves to a new city, graduations, births, engagements, marriages, and the like, as well as more mundane content such as status messages, information about what music has been listened to by users, and recent check-in events at coffee shops.

A social networking system presents various content items to a user based on the information it receives from other users. For example, the social networking system presents a user with content items describing various actions performed by other social networking system users. Additionally, entities (e.g., a business) may present content items to online system users via the feed of content item along with the content items based on information received from other users to gain public attention for products or services or to persuade social networking system users to take an action regarding products or services provided by the entity. Because of the large amount of information received by a social networking system, a large number of content items may be presented to a user. However, because users often use different devices and/or applications, such as web browsers, with different display characteristics to view feeds provided by social networking systems, content items and advertisements in a feed appear in different sizes on different devices. This may be inconvenient to users viewing the feed provided by a social networking system and may cause a feed presented to users to be differently presented by different client devices, which may increase the difficulty for the user to identify content of interest in the feed.

SUMMARY

A social networking system presents content items to a user of the social networking system via a news feed. Content items presented via the news feed include news feed stories describing actions of other social networking system users and sponsored content items, such as advertisements. The social networking system scores content items. In various embodiments, the news feed stories and sponsored content items (i.e., advertisements) are differently scored. For example, the social networking system scores a news feed story based on an expected amount of user interaction with the news feed story. The expected amount of user interaction is a measure of the probability of the user interacting with the news feed story. In some embodiments, the social networking system scores an advertisement based at least in part on a bid amount associated with the advertisement and an expected amount of user interaction with the advertisement. For example, an expected value is determined for an advertisement based on the bid amount associated with the advertisement and the expected amount of user interaction with the advertisement, and the score for the advertisement is based at least in part on the bid amount.

Based on the scores, the social networking system selects a set of candidate content items for presentation to the user via the news feed. In one embodiment, the social networking system ranks the content items based on their associated scores and selects the set of candidate content items based on their associated ranking. For example, the set of candidate content items includes content items having at least a threshold position in the ranking. When the social networking system identifies the set of candidate content items, the social networking system also predicts a height associated with each candidate content item. For example, the social networking system predicts a height associated with a candidate content item based on the content included in the candidate content item, such as text or images. In one embodiment, the social networking system uses a prediction model to predict heights associated with the candidate content items.

The prediction model used to predict the height associated with a candidate content item may be based on characteristics of the candidate content item. Characteristics of a candidate content item used to predict the height of the candidate content item include: the height of the candidate content item is based on content included in the candidate content item (e.g., image data, video data, text data), a language associated with the content item, and a number of comments associated with the candidate content item. Additionally, information describing a client device on which a candidate content item is to be presented is also used to predict the height of the candidate content item. For example, the social networking system determines one or more dimensions of a display device used to present the candidate content item based on a client device associated with the user to whom the candidate content item is to be presented by the social networking system.

Based at least in part on the predicted heights of candidate content items, the social networking system orders the selected content items within the news feed. In some embodiments, the social networking system determines a value of presenting a candidate content item in different positions of the news feed. The value is based in part on the score of the candidate content and provides a measure of an expected amount of interaction with the content item when presented in a position of the news feed. Additionally, the value accounts for a decrease in value to the social networking system from positioning additional candidate content items in positions of the news feed below the position in which the candidate content item is presented. To account for the decrease in value from presenting the additional candidate content items in positions below the position in which the candidate content item is presented, the social networking system applies a position discount to the value of the presenting the candidate content in the position of the news feed. A position discount value is associated with a position in the news feed and reflects a predicted decrease in user interaction with a content item based on the position of the content in the news feed.

When a news feed is presented to a user, the likelihood of a user interacting with a content item presented via the news feed varies depending on the position in the news feed in which the content item is presented. Positions of the news feed may be determined based on a distance between the content item and a reference position, such as an upper boundary of the news feed. For example, a user has a higher likelihood of interacting with content items presented in positions within a threshold distance from an upper boundary (or “top”) of the news feed than of interacting with content items presented in positions greater than the threshold distance from the news feed. The position discount value associated with a content item may be based at least in part on a distance between the content item and a reference position in the news feed, such as the upper boundary of the news feed. For example, different position discounts are associated with different distances between a content item and the upper boundary of the news feed, so a distance between the content item and the upper boundary determines the position discount applied to a score associated with the content item.

The social networking system may determine different values associated with a candidate content item by modifying a score of the candidate content item by different position discounts associated with different distances between the candidate content item and the upper boundary of the news feed. The different distances may be determined by combining predicted heights of other candidate content items. In some embodiments, the social networking system orders the candidate content items by associating candidate content items with distances from the upper boundary of the news feed so a combination of values associated with candidate content items associated with distances from the upper boundary of the news feed is maximized.

DETAILED DESCRIPTION

System Architecture

FIG. 1is a block diagram of a system environment100for a social networking system140. The system environment100shown byFIG. 1comprises one or more client devices110, a network120, one or more third-party systems130, and the social networking system140. In alternative configurations, different and/or additional components may be included in the system environment100. The embodiments described herein can be adapted to online systems that are not social networking systems.

One or more third party systems130may be coupled to the network120for communicating with the social networking system140, which is further described below in conjunction withFIG. 2. In one embodiment, a third party system130is an application provider communicating information describing applications for execution by a client device110or communicating data to client devices110for use by an application executing on the client device. In other embodiments, a third party system130provides content or other information for presentation via a client device110. A third party system130may also communicate information to the social networking system140, such as advertisements, content, or information about an application provided by the third party system130.

FIG. 2is an example block diagram of an architecture of the social networking system140. The social networking system140shown inFIG. 2includes a user profile store205, a content store210, an action logger215, an action log220, an edge store225, news feed manager230, an advertisement (“ad”) request store235, a height prediction module240, and a web server245. In other embodiments, the social networking system140may include additional, fewer, or different components than those described in conjunction withFIG. 2. Conventional components such as network interfaces, security functions, load balancers, failover servers, management and network operations consoles, and the like are not shown so as to not obscure the details of the system architecture.

The action log220may be used by the social networking system140to track user actions on the social networking system140, as well as actions on third party systems130that communicate information to the social networking system140. Users may interact with various objects on the social networking system140, and information describing these interactions is stored in the action log220. Examples of interactions with objects include: commenting on posts, sharing links, and checking-in to physical locations via a mobile device, accessing content items, and any other suitable interactions. Additional examples of interactions with objects on the social networking system140that are included in the action log220include: commenting on a photo album, communicating with a user, establishing a connection with an object, joining an event to a calendar, joining a group, creating an event, authorizing an application, using an application, expressing a preference for an object (“liking” the object) and engaging in a transaction. Additionally, the action log220may record a user's interactions with advertisements on the social networking system140as well as with other applications operating on the social networking system140. In some embodiments, data from the action log220is used to infer interests or preferences of a user, augmenting the interests included in the user's user profile and allowing a more complete understanding of user preferences.

The action log220may also store user actions taken on a third party system130, such as an external website, and communicated to the social networking system140. For example, an e-commerce website that primarily sells sporting equipment at bargain prices may recognize a user of a social networking system140through a social plug-in enabling the e-commerce website to identify the user of the social networking system140. Because users of the social networking system140are uniquely identifiable, e-commerce websites, such as in the preceding example, may communicate information about a user's actions outside of the social networking system140to the social networking system140for association with the user. Hence, the action log220may record information about actions users perform on a third party system130, including webpage viewing histories, advertisements that were engaged, purchases made, and other patterns from shopping and buying.

In one embodiment, the edge store225stores information describing connections between users and other objects on the social networking system140as edges. Some edges may be defined by users, allowing users to specify their relationships with other users. For example, users may generate edges with other users that parallel the users' real-life relationships, such as friends, co-workers, partners, and so forth. Other edges are generated when users interact with objects in the social networking system140, such as expressing interest in a page on the social networking system140, sharing a link with other users of the social networking system140, and commenting on posts made by other users of the social networking system140.

In one embodiment, the social networking system140identifies stories and other content items, such as advertisements, likely to be of interest to a user through a “news feed” presented to the user. A news feed story presented to a user describes an action taken by an additional user connected to the user and identifies the additional user. Additionally, a news feed story may describe objects represented in the social networking system140, such as an image, a video, a comment from a user, a status message, an external link, content generated by the social networking system140, an application, a game, or other types of content items maintained by the content store210. In some embodiments, a news feed story describing an action performed by a user may be accessible to users who are not connected to the user that performed the action. The news feed manager230may generate stories for presentation to a user based on information in the action log220and in the edge store225or may select candidate organic news feed stories included in content store210. One or more of the candidate organic news feed stories are selected and presented to a user by the news feed manager230.

The news feed manager230generates the organic news feed stories for presentation in a news feed, selects content items for presentation via the news feed, and communicates the news feed to one or more client devices110for presentation to users. For example a web browser executing on a client device110or an application executing on the client device110and associated with the social networking system140presents a news feed received from the social networking system140. An example of generating a news feed is further described in U.S. patent application Ser. No. 14/031,453, filed on Sep. 19, 2013, which is hereby incorporated by reference in its entirety. In one embodiment, the news feed manager230receives a request to present one or more organic news feed stories to a social networking system user from an application executing on a client device110and accesses one or more of the user profile store205, the content store210, the action log220, and the edge store225to retrieve information about the user. For example, organic news feed stories, other content items, or other data associated with additional users or pages connected to the user are retrieved. The retrieved organic news feed stories or other data are analyzed by the news feed manager230to identify candidate content items, which include content having at least a threshold likelihood of being relevant to the user. For example, organic news feed stories associated with additional users not connected to the user or organic news feed stories associated with additional users for which the user has less than a threshold affinity are discarded as candidate organic news feed stories. Based on various criteria, the news feed manager230selects one or more of the candidate organic news feed stories for presentation to the identified user.

In various embodiments, the news feed manager230presents content items, including organic news feed stories, to a user through a news feed including a plurality of content items selected for presentation to the user. In some embodiments, the news feed includes a plurality of positions that are each configured to present a content item, such as a news feed story or an advertisement. The news feed may include a limited number of organic news feed stories or may include a complete set of candidate organic news feed stories. For example, the number of organic news feed stories included in a news feed may be determined in part by a user preference included in user profile store205. The news feed manager230may also determine an order in which selected organic news feed stories are presented via the news feed. In one embodiment, based on the user's preference, content items presented via the news feed are presented in reverse chronological order based on timestamps associated with the content items.

The news feed manager230may also account for actions by a user indicating a preference for types of organic news feed stories, or other content items, and selects organic news feed stories, or other content items, having the same, or similar, types for inclusion in the news feed. Additionally, the news feed manager230may analyze organic news feed stories received by the social networking system140from various users to obtain information about user preferences or actions. Similarly, the news feed manager230may analyze actions associated with a user, or with additional users connected to the user, to identify user preferences for content items. This information may be used to refine subsequent selection of organic news feed stories or other content items for news feeds presented to various users.

In addition to selecting organic news feed stories for presentation via a news feed, the news feed manager230may select one or more advertisements for presentation to a user via the news feed. For example, a news feed presented to a user may include one or more advertisements as well as organic news feed stories. To select organic news feed stories or advertisements for presentation via a news feed, the news feed manager determines scores for the advertisements and for the organic news feed stories. In one example, a score for an advertisement is based at least in part on a bid amount associated with the advertisement, a position in the news feed in which the advertisement is to be presented, and an expected amount of interaction with the advertisement. Similarly, a score for a news feed story is based at least in part on an expected amount of interaction with the news feed story and a position in the news feed in which the news feed story is to be presented. Based on the scores associated with organic news feed stories and advertisements, the news feed manager230selects one or more content items for presentation. For example, the news feed manager230ranks organic news feed stories and advertisements based on their scores and selects organic news feed stories or advertisements for presentation based on the ranking.

One or more advertisement requests (“ad requests”) are included in the ad request store235. An advertisement request includes advertisement content (also referred to as an “advertisement”) and a bid amount. The advertisement content is text, image, audio, video, or any other suitable data presented to a user. In various embodiments, the advertisement content also includes a landing page specifying a network address to which a user is directed when the advertisement is accessed. The bid amount is associated with an ad request by an advertiser and is used to determine an expected value, such as monetary compensation, provided by an advertiser to the social networking system140if advertisement content in the ad request is presented to a user, if the advertisement content in the ad request receives a user interaction when presented, or based on any other suitable condition. For example, the bid amount specifies a monetary amount that the social networking system140receives from the advertiser if advertisement content included in an ad request is displayed and the expected value is determined by multiplying the bid amount by a probability of the advertisement content being accessed by a user.

Additionally, an advertisement request may include one or more targeting criteria specified by the advertiser. Targeting criteria included in an advertisement request specify one or more characteristics of users eligible to be presented with advertisement content in the advertisement request. For example, targeting criteria are used to identify users having user profile information, edges or actions satisfying at least one of the targeting criteria. Hence, targeting criteria allow an advertiser to identify users having specific characteristics, simplifying subsequent distribution of content to different users.

In one embodiment, targeting criteria may specify actions or types of connections between a user and another user or object of the social networking system140. Targeting criteria may also specify interactions between a user and objects performed external to the social networking system140, such as on a third party system130. For example, targeting criteria identifies users that have taken a particular action, such as sending a message to another user, using an application, joining a group, leaving a group, joining an event, generating an event description, purchasing or reviewing a product or service using an online marketplace, requesting information from a third-party system130, or any other suitable action. Including actions in targeting criteria allows advertisers to further refine users eligible to be presented with content from an advertisement request. As another example, targeting criteria identifies users having a connection to another user or object or having a particular type of connection to another user or object.

In various embodiments, content items presented to the user via a news feed may have different heights. For example, different organic news feed stories or different advertisements vertically occupy different numbers of pixels when displayed to a user via a client device110. Because of different dimensions of display devices used by various client devices110or different resolutions of display devices used by various client devices110, heights of content items in a news feed may differ when the news feed is presented to a user by different client devices110. The height prediction module240predicts a height for each content item (e.g., news feed story or advertisement). For example, the height prediction module240predicts a height associated with a content item based on characteristics of the content item, such as a type of content (e.g., text or image) included in the content item, a language associated with the content item, and a number of comments associated with the content item. Characteristics of a client device110associated with a user to whom the content item is to be presented may also be identified and used by the height prediction module240to predict heights associated with content items in a news feed selected for the user. For example, a client device110associated with the user by a user profile in the user profile store205is retrieved, and characteristics (e.g., display device dimensions, display device resolution) of the client device110are used by the height prediction module240to predict heights of content items for presentation to the user. As another example, a request for content received from a user may include an identifier of a client device110, which the height prediction module240uses to retrieve characteristics of the client device110for predicting heights of content items to be presented based on the request.

In one embodiment, the height prediction module240trains a prediction model to predict the height associated with a content item. The prediction model may be one or more machine learned models. For example, the height prediction module240stores a set of features associated with a content item or with a user to be presented with the content item. The set of features may include characteristics of the content item. Example characteristics of the content item include: types of content in the content item (e.g., image, video, text), sizes of content in the content item (e.g., sizes of text, image or video data), a language used in the content item, and a number of comments associated with the content item. Features associated with the user may include a type of client device110associated with the user, dimensions of a display device of the client device110, a resolution of the display device of the client device110, and information describing applications executing on the client device110(e.g., a version of an application used by the client device110to display content items).

In one embodiment, the height prediction module240uses training sets of data to determine weights for the features associated with content items or with the user that are used by the prediction model. The training sets may include results of presenting content items to users that are used by the height prediction module240to determine weights associated with various features. For example, the height associated with a news feed story including an image when viewed by a user via a specific type of client device110is a result used to determine weights associated with various features. In this example, characteristics of the user and characteristics of the news feed story are used to associate weights with data from the training set, such as features associated with a news feed story having a height matching, or similar to, the height of the news feed story (e.g., a weight is associated with a type of client device110matching the specific type of client device110in the training set that is associated with a news feed story associated with a height matching the height of the presented news feed story). Weights associated with various features may be aggregated over multiple training sets to improve the accuracy of the weights. Alternatively, a height associated with advertisements including various types of content, such as images or text in a different language, may be an outcome based on the features of the type of content or the language of the content. The client device110associated with a user and most frequently or likely used by a user while viewing a news feed, may be another type of result from a model.

Based on the prediction model, the height prediction module240generates a predicted height associated with a content item (e.g., a news feed story or an advertisement). The predicted height represents the likely height of the content item when presented to the user via a client device110. The predicted height may be expressed as a number of pixels in various embodiments. In one embodiment, the news feed manager230may score content items based on the predicted height value associated with the content items by the height prediction module240. Further, the news feed manager230may order and select scored content items for presentation to a user via the news feed based at least in part on the predicted height values associated with the content items, as further described below in conjunction withFIGS. 3-5.

The web server245links the social networking system140via the network120to the one or more client devices110, as well as to the one or more third party systems130. The web server140serves web pages, as well as other web-related content, such as JAVA®, FLASH®, XML and so forth. The web server245may receive and route messages between the social networking system140and the client device110, for example, instant messages, queued messages (e.g., email), text messages, short message service (SMS) messages, or messages sent using any other suitable messaging technique. A user may send a request to the web server245via the client device110for content items, organic news feed stories, or advertisements to be presented to the user via the news feed. Additionally, the web server245may provide application programming interface (API) functionality to send data directly to native client device operating systems, such as IOS®, ANDROID™, WEBOS® or BlackberryOS.

Example Presenting Content Items in a News Feed

FIG. 3shows an example presentation of content to a social networking system user via a news feed presented on different client devices110. As used herein, “content items” refers to organic news feed stories, advertisements, or any combination thereof. In the example ofFIG. 3, a news feed310presented to a social networking system user includes organic news feed stories and advertisements; however, in other embodiments, other types of content items may be presented via the news feed310. The news feed310inFIG. 3includes multiple content items315A,315B,315C,315D (individually and collectively referred to using reference number315). Each content item315may have a different height when viewed by the user via the news feed310. The height associated with a content item315represents a number of vertical pixels associated with the content item315when presented to the user on a client device110. Different content items315may have different heights for a variety of reasons, for example, different content items315may include different content, such as images, text, or text language. Alternatively, different content items315may be associated with different numbers of comments, so the different content items315have different heights.

The news feed310may be viewed by the user on different client devices110. In the example ofFIG. 3, the news feed310is viewed on client device110A and client device110B. Content items315in the news feed310may have different heights when presented to the user on the different client devices110because of different dimensions of display devices of each client device or use of different applications to present the news feed310by different client device110. In the example ofFIG. 3, when presented to the user via client device110A, the news feed310includes content items315A,315B,315C, and315D, which respectively have heights330A,330B,330C, and330D (individually and collectively referred to using reference number330). Alternatively, inFIG. 3, when the news feed310is presented to the user via client device110B content items315A,315B,315C, and315D respectively have heights335A,335B,335C, and335D (individually and collectively referred to using reference number335).

In the example ofFIG. 3, client device110A has a display device with different dimensions than a display device of client device110B, causing the content items315to have heights330on client device110A and to have heights335on client device110B. In some embodiments, the content items315may have different heights330and335when presented to a user via the same client device110. For example, the content items315have heights330when viewed using a client device110oriented so its display device is in a portrait orientation having a vertical dimension larger than a horizontal dimension, and have heights335when viewed using the client device110oriented so its display device is in a landscape orientation having the vertical dimension larger than the horizontal dimension. As another example, content items315have different heights330,335when presented using different applications executing on a client device.

The social networking system140may predict a height330,335associated with a content item315when presented to a user via a client device110and determine a position of the content item315in the news feed310relative to other content items315based on the predicted height330,335. Use of predicted height330,335to determine an order of content items315in the news feed310is further described below in conjunction withFIG. 4andFIG. 5. For example, to enhance user interaction, the social networking system140may present a specified number of organic news feed stories to a user prior to providing the user with an advertisement via the news feed. To present the specified number of organic news feed stories, the social networking system140may determine a threshold distance (e.g., number of pixels) from an upper boundary of the news feed310and does not present an advertisement within the threshold distance of the upper boundary of the news feed310. Based on the predicted heights associated with organic news feed stories, the social networking system140selects a number of organic news feed stories so the aggregate predicted heights of the number of organic news feed stories equals or exceeds the threshold distance. Hence, predicting heights of organic news feed stories allows the social networking system140to present a threshold number of organic news feed stories within a threshold distance from the upper boundary of the news feed310before presenting an advertisement in the news feed310.

As another example, the social networking system140determines a threshold distance between advertisements presented in the news feed310to prevent a user from becoming inundated with advertisements in a portion of the news feed310. The social networking system140determines the number of organic news feed stories to include in the threshold distance between an advertisement and an additional advertisement so an aggregate of the predicted heights of the organic news feed stories equals or exceeds the threshold distance. In some embodiments, the social networking system140selects organic news feed stories based in part on their predicted heights so at least a threshold number of organic news feed stories are presented in the threshold distance between an advertisement and an additional advertisement.

As the social networking system140presents content items in a news feed to a user, a content item displaces the content items in lower positions in the news feed based on the height of the content item. Displacing a content item may reduce user engagement with the displaced content item by causing a user to navigate through the news feed310to view or otherwise access the displaced content item. To prevent from impairing user interaction with the news feed310, the social networking system140may score a content item in the news feed310based at least in part on an amount the content item displaces content items in lower positions in the news feed310based on the predicted height associated with the content item. Ordering presentation of content items in the news feed310based at least in part on their predicted heights is further described below in conjunction withFIG. 5.

Selecting Content Items for Inclusion in a News Feed

FIG. 4is a flow chart of one embodiment of a method for selecting content items for presentation to a social networking system user via a news feed. As used herein, “content items” refer to organic news feed stories, advertisements, or any combination thereof. In some embodiments, different and/or additional steps than those identified in conjunction withFIG. 4may be performed or the steps described in conjunction withFIG. 4may be performed in different orders.

The social networking system identifies405one or more content items for presentation to a user via the news feed. For example, new organic news feed stories are generated by the news feed manager230and maintained in a queue for presentation to the user. One or more organic news feed stories may be identified405from this queue as content items for inclusion in the news feed. Identification of organic news feed stories is further described in U.S. patent application Ser. No. 14/031,453, filed on Sep. 19, 2013, which is hereby incorporated by reference in its entirety. In another example, the social networking system140identifies405content items stored in the content store210or actions stored in the action log220associated with additional users for which the user has greater than a threshold affinity. Additionally, one or more advertisements included in the ad request store235may be identified405as content items. For example, advertisements associated with at least a threshold number of targeting criteria satisfied by the user are identified405from the ad request store235as content items for inclusion in the news feed.

The social networking system140predicts410a height associated with each of the identified content items based at least in part on characteristics of the identified content item. In various embodiments, the predicted height of a content item represents a number of pixels along a vertical axis used to present the content item via a client device110. For example, the social networking system140predicts410a height value associated with a content item based on the content, such as a type of content (e.g., image, text, video) included in the content item, a language of the content item, and a number of comments associated with the content item. Additionally, characteristics of a client device110associated with the user to whom the content item is to be presented may also be used to predict410the height associated with the content item. Example characteristics of a client device110used to predict410the height of a content item include dimensions of a display device of the client device110, a resolution of the display device of the client device110, and a type of application used by the client device110to present the content item. As described above in conjunction withFIG. 2, the social networking system140may use one or more machine learned models to predict410heights of various content items.

Based at least in part on expected user interaction with the identified content items, the social networking system140scores415the identified content items. In some embodiments, the social networking system140differently scores415different types of content items. For example, organic news feed stories and advertisements are differently scored415. In one embodiment, the social networking system140scores415a news feed story based on an expected amount of user interaction with a news feed story, which provides a measure of the probability of the user interacting with the news feed story. The expected amount of interaction may be based on an organic value associated with a news feed story; determining an organic value associated with a news feed story is further described in U.S. patent application Ser. No. 12/978,265, filed on Dec. 23, 2010, and U.S. patent application Ser. No. 13/545,266, filed on Jul. 10, 2012, each of which is hereby incorporated by reference in its entirety.

In some embodiments, the social networking system140scores415an advertisement based at least in part on a bid amount associated with the advertisement and an expected amount of user interaction with the advertisement. The social networking system140retrieves the bid amount associated with an advertisement from an ad request associated with the advertisement stored in the ad request store235. A conversion factor may be applied to one or more of the bid amount and the expected amount of user interaction with the advertisement by the social networking system140to score415the advertisement. Combining a bid amount and an expected amount of user interaction is further described in U.S. patent application Ser. No. 13/545,266, filed on Jul. 10, 2012, which is hereby incorporated by reference in its entirety.

The social networking system140may account for a predicted height associated with a content item when scoring415the content item. For example, a score associated with a content item having a predicted height greater than a threshold value is reduced, while a score associated with content item having a predicted height less than the threshold value is increased. The social networking system140may reduce scores associated with advertisements having greater than a threshold predicted height.

Based on the scores and predicted heights associated with content items, the social networking system140selects420one or more content items for presentation to the user via the news feed. In one embodiment, the social networking system140ranks the content items based on their associated scores and selects420content items based on their associated rank. For example, scores associated with organic news feed stories and scores associated with advertisements are converted into a common unit of measurement, and advertisements and organic news feed stories are together ranked in a single ranking, as further described in U.S. patent application Ser. No. 13/545,266, filed on Jul. 10, 2012, which is hereby incorporated by reference in its entirety. Alternatively, organic news feed stories and advertisements are separately ranked based on their associated scores. Based on the ranking, the social networking system140selects420one or more content items for presentation to the user via the news feed. For example, content items having at least a threshold position in a ranking are selected420.

Content items may be selected420using one or more rules based at least in part on predicted heights associated with content items. The one or more rules may also be based in part on a type associated with various content items. For example, a rule specifies a minimum number of content items to present within a threshold distance in a vertical dimension of the news feed, so the social networking system140selects420a number of content items based at least in part on their scores and their predicted heights so an aggregate of the predicted heights of the number of content items is less than or equal to the threshold vertical distance. In one embodiment, the threshold vertical distance is a distance from an upper boundary of the news feed.

One or more rules used to select420content items may be based on types associated with content items. For example, a rule specifies a threshold distance in a vertical dimension of the news feed between an upper boundary of the news feed and an initial advertisement presented in the news feed. When selecting420content items, the social networking system140initially selects420a number of content items that are organic news feed stories so an aggregation of the predicted heights of the number of content items that are organic news feed stories equals or exceeds the threshold distance. After the aggregated predicted heights of the selected organic news feed stories satisfies the threshold distance, the social networking system140identifies content items that are advertisements as eligible to be selected420and may select420an advertisement based on scores associated with advertisements. For example, the social networking system140selects420organic news feed stories having the highest relative scores to other organic news feed stories then determines whether an aggregation of the predicted heights of the organic news feed stories equals or exceeds the threshold distance. If the aggregation of the predicted heights or the organic news feed stories is less than the threshold distance, the social networking system140selects420alternative organic news feed stories based on their scores and their predicted heights. For example, the social networking system140may select alternative organic news feed stories having lower scores but larger predicted heights, or may maintain organic news feed stories having maximum scores and select420alternative organic news feed stories having lower scores and larger predicted heights than originally selected420organic news feed stories.

As another example, after selecting420a news feed story having a maximum score relative to other organic news feed stories, the social networking system determines a difference between the threshold distance and the predicted height of the selected news feed story, the determined difference is used along with scores and predicted heights to select420additional organic news feed stories until the aggregation of the predicted heights of the selected organic news feed stories equals or exceeds the threshold distance. In some embodiments, a rule also specifies a minimum number of organic news feed stories to present in the threshold distance between the upper boundary of the news feed and the initial advertisement, so the social networking system140selects420organic news feed stories based on their scores and predicted heights so at least the threshold number of organic news feed stories are selected and the total of the predicted heights of the selected organic news feed stories equals or exceeds the threshold distance; hence, the social networking system140selects420at least the threshold number of organic news feed stories so a combination of the predicted heights of the selected organic news feed stories equals or exceeds the threshold distance. For example, if the predicted height associated with a news feed story having a second highest score is greater than the difference between the threshold distance and the predicted height of the selected news feed story having the maximum score, the social networking system140selects420a news feed story having a third highest score if the news feed story having the third highest score is associated with a predicted height less than the difference between the threshold distance and the predicted height of the selected news feed story having the maximum score relative to the other organic news feed stories. The social networking system140may repeat this process until the threshold number of organic news feed stories is selected420for presentation in the threshold distance between the upper boundary of the news feed and the initial advertisement presented in the news feed.

Another rule used by the social networking system140when selecting420content items may specify a threshold distance in a vertical dimension of the feed between advertisements presented in the news feed. Hence, after selecting420an advertisement for presentation via the news feed, the social networking system420selects content items other than advertisements, such as organic news feed stories, based on their scores. When an aggregation of the predicted heights of selected content items other than advertisements selected420by the social networking system equals or exceeds the threshold distance, the social networking system420determines advertisements are again eligible for selection for presentation via the news feed. Alternatively, the social networking system140selects420organic news feed stories, or other content items, based on their scores and predicted heights, so an aggregate of the predicted heights of the selected content items equals or exceeds the threshold distance then selects420an advertisement for presentation via the news feed. In some embodiments, a rule specifies a minimum number of organic news feed stories, or other content items, for presentation using the threshold distance between advertisements, so the social networking system140selects content items for presentation in the threshold distance based on their scores and predicted heights as described above. The threshold distance between consecutive advertisements presented via the news feed may be determined by the social networking system140based at least in part on predicted heights of one or more advertisements, such as advertisements having at least a threshold score or having a threshold position in a ranking.

After selecting420content items for presentation via the news feed, the social networking system140provides425the selected content items to a client device110associated with the user for presentation via the news feed. In various embodiments, the selected content items are provided425to the client device110in response to a request for content items received by the social networking system140. Alternatively, the social networking system140provides425the selected content items to the client device110at periodic intervals or pushes the selected content items to the client device110when they are selected420.

WhileFIG. 4shows an example where the social networking system140predicts410heights of content items prior to selecting420content items for inclusion in the news feed, in other embodiments, the social networking system140initially scores415content items and selects420a set of candidate content items based at least in part on the scores. Heights are then predicted410for each of the candidate content items in the set, and the social networking system140selects425candidate content items from the set for presentation via the news feed based at least in part on the predicted heights of the candidate content items as well as the scores of the candidate content items, as further described above. Predicting410heights of candidate content items after selecting the candidate content items allows the social networking system140to conserve computing resources by predicting410heights for a smaller number of content items.

Ordering Content Items for Presentation in a News Feed

FIG. 5is a flow chart of one embodiment of a method for ordering content items selected for presentation to be presented to a social networking system user in a news feed. As used herein, “content items” refer to organic news feed stories, advertisements, or any combination thereof. In some embodiments, different and/or additional steps than those identified in conjunction withFIG. 4may be performed or the steps described in conjunction withFIG. 4may be performed in different orders.

The social networking system identifies505one or more content items for presentation to a user via the news feed. For example, new organic news feed stories are generated by the news feed manager230and maintained in a queue for presentation to the user. One or more organic news feed stories may be identified505from this queue as content items for inclusion in the news feed. Identification of organic news feed stories is further described in U.S. patent application Ser. No. 14/031,453, filed on Sep. 19, 2013, which is hereby incorporated by reference in its entirety. In another example, the social networking system140identifies505content items stored in the content store210or actions stored in the action log220associated with additional users for which the user has greater than a threshold affinity. Additionally, one or more advertisements included in the ad request store235may be identified505as content items. For example, advertisements associated with at least a threshold number of targeting criteria satisfied by the user are identified505from the ad request store235as content items for inclusion in the news feed.

Based at least in part on expected user interaction with the identified content items, the social networking system140scores510the identified content items. In some embodiments, the social networking system140differently scores510different types of content items. For example, organic news feed stories and advertisements are differently scored510. In one embodiment, the social networking system140scores510a news feed story based on an expected amount of user interaction with a news feed story, which provides a measure of the probability of the user interacting with the news feed story. The expected amount of interaction may be based on an organic value associated with a news feed story; determining an organic value associated with a news feed story is further described in U.S. patent application Ser. No. 12/978,265, filed on Dec. 23, 2010, and U.S. patent application Ser. No. 13/545,266, filed on Jul. 10, 2012, each of which is hereby incorporated by reference in its entirety.

In some embodiments, the social networking system140scores510an advertisement based at least in part on a bid amount associated with the advertisement and an expected amount of user interaction with the advertisement. The social networking system140retrieves the bid amount associated with an advertisement from an ad request associated with the advertisement stored in the ad request store235. A conversion factor may be applied to one or more of the bid amount and the expected amount of user interaction with the advertisement by the social networking system140to score510the advertisement. Combining a bid amount and an expected amount of user interaction is further described in U.S. patent application Ser. No. 13/545,266, filed on Jul. 10, 2012, which is hereby incorporated by reference in its entirety.

Based on the scores, the social networking system140selects515a set of candidate content items for presentation via the news feed. In one embodiment, the social networking system140ranks the content items based on their associated scores and selects515the set of candidate content items based on their associated rank. For example, scores associated with organic news feed stories and scores associated with advertisements are converted into a common unit of measurement, and advertisements and organic news feed stories are together ranked together in a single ranking, as further described in U.S. patent application Ser. No. 13/545,266, filed on Jul. 10, 2012, which is hereby incorporated by reference in its entirety. Content items having at least a threshold position in the ranking are selected515as candidate content items. Alternatively, organic news feed stories and advertisements are separately ranked based on their associated scores. Based on the ranking, the social networking system140selects515one or more content items as candidate content items. For example, content items having at least a threshold position in the ranking are selected515as candidate content items.

The social networking system140also predicts520heights associated with each of the candidate content items in the set of candidate content items based at least in part on characteristics of the identified content item. In various embodiments, the predicted height of a candidate content item represents a number of pixels along a vertical axis used to present the content item via a client device110. For example, the social networking system140predicts520a height value associated with a candidate content item based on the content, such as a type of content (e.g., image, text, video) included in the content item, a language of the content item, and a number of comments associated with the content item. Additionally, characteristics of a candidate client device110associated with the user to whom the content item is to be presented may also be used to predict520the height associated with the candidate content item. Example characteristics of a client device110used to predict520the height of a candidate content item include dimensions of a display device of the client device110, a resolution of the display device of the client device110, and a type of application used by the client device110to present the candidate content item. Prediction of heights associated with candidate content items is further described above in conjunction withFIGS. 2 and 4.

Based on the predicted height values associated with the selected content items the social networking system140orders525the candidate content items for presentation via the news feed. In one example, the social networking system140orders525candidate content items so candidate content items associated with less than a threshold height have higher positions in the news feed than candidate content items associated with greater than the threshold height. In another example, the social networking system140orders525the candidate content items based at least in part on the predicted heights associated with various candidate content items. A type associated with the candidate content items may be used along with the predicted heights when ordering525the candidate content items. For example, candidate content items that are advertisements are ordered525so they are greater than a threshold distance from an upper boundary of the news feed. In one embodiment, the social networking system140orders525candidate content items so a combination of predicted heights of candidate content items that are not advertisements equals or exceeds the threshold distance before an initial advertisement is included in the news feed. A threshold number of content items, such as organic news feed stories, may be included in the threshold distance between the initial advertisement and the upper boundary of the news feed when ordering525the candidate content items. Selection of content items based on predicted heights and threshold distances is further described above in conjunction withFIG. 4.

In some embodiments, the social networking system140determines a value to the social networking system140of presenting a candidate content item in different positions of the news feed. The value is based in part on the score of the candidate content and provides a measure of an expected amount of interaction with the content item when presented in a position of the news feed. Additionally, the value accounts for a decrease in value to the social networking system from positioning additional candidate content items in positions of the news feed below the position in which the candidate content item is presented. To account for the decrease in value from presenting the additional candidate content items in positions below the position in which the candidate content item is presented, the social networking system140applies a position discount to the value of the presenting the candidate content in the position of the news feed. A position discount value is associated with a position in the news feed and reflects a predicted decrease in user interaction with a content item based on the position of the content in the news feed. When a news feed is presented to a user, the likelihood of a user interacting with a content item presented via the news feed varies depending on the position in the news feed in which the content item is presented. Positions of the news feed may be determined based on a distance between the content item and a reference position, such as an upper boundary of the news feed. For example, a user has a higher likelihood of interacting with content items presented in positions within a threshold distance from an upper boundary (or “top”) of the news feed than of interacting with content items presented in positions greater than the threshold distance from the news feed. The position discount value associated with a content item may be based at least in part on a distance between the content item and a reference position in the news feed, such as the upper boundary of the news feed. For example, different position discounts are associated with different distances between a content item and the upper boundary of the news feed, so a distance between the content item and the upper boundary determines the position discount applied to a score associated with the content item. Determining a position discount value associated with a position in a news feed is further described in U.S. patent application Ser. No. 14/049,429, filed on Oct. 9, 2013, which is hereby incorporated by reference in its entirety.

When ordering525the candidate content items, the social networking system140determines values for presenting a candidate content item in different positions of the news feed based on the score associated with the candidate content item modified by position discounts based on distances between the candidate content item and an upper boundary of the news feed. The position discount may be determined based on the predicted heights of one or more additional candidate content items, such as additional candidate content items presented nearer to the upper boundary of the news feed (i.e., predicted heights of additional candidate content items in higher positions of the news feed). For example, predicted heights of one or more additional candidate content items are combined, with a position discount for presenting a candidate content item lower in the news feed than the additional candidate content items determined based on the combined predicted heights and applied to a score for the candidate content item to determine a value for the candidate content item. Values for various candidate content items presented different distances from the upper boundary of the news feed are determined, and the social networking system140orders525the candidate content items to maximize an aggregation of the values of the candidate content items. For example, the social networking system140determines a value for a candidate content item presented a distance from a reference location using a position discount associated with the distance and one or more alternative values for the content item presented in alternative locations from the reference location based on alternative position discounts associated with the alternative locations. The value and alternative values are stored in association with the content item and the distance and alternative distances. As the position discounts are based on a distance between a content item and the upper boundary of the news feed (or any other suitable reference location), the position discount used to determine a value for presenting a candidate content item is determined based on an aggregation of predicted heights of additional candidate content items presented nearer to the upper boundary of the news feed than the candidate content item. In some embodiments, the social networking system140orders525the selected content items so a combination of the values associated with content items and distances from the reference location is maximized.

After selecting420content items for presentation via the news feed, the social networking system140provides425the selected content items to a client device110associated with the user for presentation via the news feed. In various embodiments, the selected content items are provided425to the client device110in response to a request for content items received by the social networking system140. Alternatively, the social networking system140provides425the selected content items to the client device110at periodic intervals or pushes the selected content items to the client device110when they are selected420.

SUMMARY