Dynamically generating recommendations based on social graph information

• US 9,223,879 B2
• Filed: 05/14/2012
• Issued: 12/29/2015
• Est. Priority Date: 04/19/2010
• Status: Expired due to Fees

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Narayanan, Srinivas, Singh, Sanjeev, Li, Alex
• Primary Examiner(s): Jacob, Ajith
• Application Number:
  US13/471,427
• Publication Number:
  US 20120271831A1
• Time in Patent Office: 1,324 Days
• Field of Search: 707/798
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9536 Search customisation based on social or collaborative filtering

Abstract

In one embodiment, a method includes maintaining access to information comprising nodes and edges; receiving a request from a first user corresponding to a first user node for a structured document corresponding to a first concept node; determining a first data set that identifies concept nodes connected by edges with user nodes that are each connected by edges with both the first user node and the first concept node; determining a second data set that identifies concept nodes connected by edges with the first concept node and user nodes that are each connected to the first user node; generating a score for each concept node in the data sets; selecting one or more concept nodes based on their scores as recommended nodes; and transmitting to the client device the structured document and code executable by a client application to render node names or identifiers of the recommended nodes for display.

Claims

1. A method comprising:

receiving, by one or more computing systems, a request from a first user of a social network environment for a first structured document, wherein the social network environment comprises a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the plurality of nodes comprising;

a first user node corresponding to the first user;

a plurality of second user nodes corresponding to a plurality of second users, respectively;

a first concept node corresponding to the first structured document; and

a plurality of second concept nodes corresponding to a plurality of second concepts, respectively;

determining, by the one or more computing systems, a first data set that identifies one or more second concept nodes that correspond to one or more second structured documents, respectively, each second structured document being conceptually relevant to the first structure document corresponding to the first concept node requested by the first user, each second concept node in the first data set being identified at least in part on a relevance score for the second concept node in the first data set with respect to the first concept node calculated by the one or more processors based on connections in the social graph between the second concept node and the first concept node, each second concept node in the first data set having a relevance score greater than a threshold relevance score;

determining, by the one or more computing systems, a second data set that identifies one or more second concept nodes in the first data set, each concept node in the second data set being connected by respective edges with the first concept node and one or more second user nodes that are each connected to the first user node; and

selecting, by the one or more computing systems, one or more second concept nodes in the second data set to recommend to the first user responsive to the request.

2. The method of claim 1, further comprising transmitting, by the one or more computing systems, the structured document corresponding to the first concept node, wherein the structured document comprises code executable by a client application to render node names or other identifiers of the recommended nodes for display.

3. The method of claim 1, wherein the social network environment further comprises one or more data stores comprising information corresponding to one or more of a plurality of users of the social network environment, and wherein the data store of information is indexed into one or more indexes to facilitate the determining of the first data set.

4. The method of claim 3, wherein one of the indexes comprises an index of all users indexed by corresponding user IDs that includes, for each particular user ID, a first set of users identified by their respective user IDs whose respective user nodes are connected to the user node corresponding to the particular user ID.

5. The method of claim 3, wherein one of the indexes comprises an index of all users indexed by corresponding user IDs that includes, for each particular user ID, a first set of concept nodes identified by corresponding concept IDs that are connected to the user node corresponding to the particular user ID.

6. The method of claim 3, wherein one of the indexes comprises an index of all concepts indexed by corresponding concept IDs that includes, for each particular concept ID, a first set of concept nodes identified by corresponding IDs that are connected to the particular concept node corresponding to the particular concept ID.

7. The method of claim 3, wherein one of the indexes comprises an index of all concepts indexed by corresponding concept IDs that includes, for each particular concept ID, a first set of user identified by their respective user IDs whose respective user nodes are connected to the concept node corresponding to the particular concept ID.

8. The method of claim 1, wherein:

the social network environment further comprises one or more data stores comprising information corresponding to one or more of a plurality of users of the social network environment, the data store of information being indexed into one or more indexes;

determining the first data set comprises sending a first nested query to an indexing process that searches the one or more indexes; and

determining the second data set comprises sending a second nested query to the indexing process that searches the one or more indexes.

9. The method of claim 1, further comprising:

generating, by the one or more computing systems, for each second concept node in the first data set, a score based at least in part on the number of user nodes connected to both the second concept node and the first concept node;

wherein generating a score for each second concept node comprises (1) generating and (2) summing or otherwise combining;

one or more coefficient scores between each second concept node in the first and second data sets and each of the user nodes connected with the user node corresponding to the first user;

one or more coefficient scores between each second concept node in the first and second data sets and the node corresponding to the first user;

one or more coefficient scores between each second concept node in the first and second data sets and the first concept node;

or

one or more coefficient scores between the node corresponding to the first user and each of the user nodes connected with a second concept node in the first and second data sets.

10. The method of claim 1, further comprising:

generating, by the one or more computing systems, for each second concept node in the first data set, a score based at least in part on the number of user nodes connected to both the second concept node and the first concept node;

wherein each of one or more of the coefficient scores generated for a user node and a concept node, a pair of user nodes, or a pair of concept nodes, are generated based on one or more of;

a relationship of the user corresponding to the user node to a concept corresponding to the concept node;

a relationship of the user corresponding to the user node to the first user;

a level or frequency of interaction between the user corresponding to the user node and the concept profile corresponding to the concept node;

a level or frequency of interaction between the user corresponding to the user node and the first user;

a number of user nodes, concept nodes, or total nodes connected to both the user node and the concept node, or connected to both the user node and the node corresponding to the first user, or connected to both the concept node and the first concept node, or connected to both the concept node and the user node corresponding to the first user;

or the quantity or quality of shared content between the concept profile page corresponding to the concept node and the concept profile page corresponding to the first concept node.

11. The method of claim 1, wherein, for one or more of the second concept nodes in the first data set, the connections in the social graph between the second concept node and the first concept node comprise the second concept node and the first concept node both being connected by edges to at least a threshold number of intermediate nodes.

12. The method of claim 1, wherein, for one or more of the second concept nodes in the first data set, the connections in the social graph between the second concept node and the first concept node comprise the second concept node being connected to first concept node by at least a threshold number of edges.

13. The method of claim 1, wherein, for one or more of the second concept nodes in the first data set, the connections in the social graph between the second concept node and the first concept node comprise the second concept node being within a threshold degree of separation of the first concept node.

14. The method of claim 1, wherein each concept node of the social graph corresponds to a respective structured document comprising one or more items of content, and wherein each second concept node in the first data set being identified is further based on, for one or more of the second concept nodes in the first data set, whether a structured document corresponding to the second concept node comprises at least a threshold number of items of content that substantially match the one or more items of content of the structured document corresponding to the first concept node.

15. The method of claim 1, wherein each concept node of the social graph is indexed in a particular category, and wherein each second concept node in the first data set being identified is further based on, for one or more of the second concept nodes in the first data set, whether the second concept node and the first concept node are both indexed in the same category.

16. The method of claim 1, further comprising:

determining, by the one or more computing systems, a relevance score for the first concept node with respect to one or more second concept nodes; and

identifying, by the one or more computing systems, one or more of the second concept nodes having a relevance score greater than a threshold relevance score to include in the first data set.

17. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

receive a request from a first user of a social network environment for a first structured document, wherein the social network environment comprises a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the plurality of nodes comprising;

a first user node corresponding to the first user;

a plurality of second user nodes corresponding to a plurality of second users, respectively;

a first concept node corresponding to the first structured document; and

a plurality of second concept nodes corresponding to a plurality of second concepts, respectively;

determine a first data set that identifies one or more second concept nodes that correspond to one or more second structured documents, respectively, each second structured document being conceptually relevant to the first structure document corresponding to the first concept node requested by the first user, each second concept node in the first data set being identified at least in part on a relevance score for the second concept node in the first data set with respect to the first concept node calculated by the one or more processors based on connections in the social graph between the second concept node and the first concept node, each second concept node in the first data set having a relevance score greater than a threshold relevance score;

determine a second data set that identifies one or more second concept nodes in the first data set, each concept node in the second data set being connected by respective edges with the first concept node and one or more second user nodes that are each connected to the first user node; and

select one or more second concept nodes in the second data set to recommend to the first user responsive to the request.

18. A system comprising:

one or more processors; and

a memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to;

receive a request from a first user of a social network environment for a first structured document, wherein the social network environment comprises a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the plurality of nodes comprising;

a first user node corresponding to the first user;

a plurality of second user nodes corresponding to a plurality of second users, respectively;

a first concept node corresponding to the first structured document; and

a plurality of second concept nodes corresponding to a plurality of second concepts, respectively;

determine a first data set that identifies one or more second concept nodes that correspond to one or more second structured documents, respectively, each second structured document being conceptually relevant to the first structure document corresponding to the first concept node requested by the first user, each second concept node in the first data set being identified at least in part on a relevance score for the second concept node in the first data set with respect to the first concept node calculated by the one or more processors based on connections in the social graph between the second concept node and the first concept node, each second concept node in the first data set having a relevance score greater than a threshold relevance score;

determine a second data set that identifies one or more second concept nodes in the first data set, each concept node in the second data set being connected by respective edges with the first concept node and one or more second user nodes that are each connected to the first user node; and

select one or more second concept nodes in the second data set to recommend to the first user responsive to the request.