Dynamically generating recommendations based on social graph information

• US 8,180,804 B1
• Filed: 04/19/2010
• Issued: 05/15/2012
• Est. Priority Date: 04/19/2010
• Status: Active Grant

• 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): Mofiz, Apu
• Assistant Examiner(s): Jacob, Ajith
• Application Number:
  US12/763,132
• Time in Patent Office: 757 Days
• Field of Search: 707/798
• US Class Current: 707/798
• 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:

maintaining, by one or more computing systems, access to a data store of information corresponding to one or more of a plurality of users of a social network environment and one or more of a plurality of concepts and comprising;

a plurality of nodes including a set of user nodes that each correspond to a respective user, and a set of concept nodes that each correspond to a respective concept, each node of the sets of nodes being associated with a corresponding structured document; and

a plurality of edges that each define a connection between a corresponding pair of nodes from the plurality of nodes;

receiving, by the one or more computing systems, a request from a first user corresponding to a first user node for a structured document corresponding to a first concept node;

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

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

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

selecting, by the one or more computing systems, one or more concept nodes based on their respective scores as recommended nodes; and

transmitting to the client device, 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.

2. The method of claim 1, wherein the data store of information is indexed into one or more indexes to facilitate the determining of the first and second data sets.

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

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

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

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

7. The method of claim 2, wherein:

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.

8. The method of claim 1, wherein generating a score for each concept node comprises generating and summing or otherwise combining:

one or more coefficient scores between each 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 concept node in the first and second data sets and the node corresponding to the first user;

one or more coefficient scores between each 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 concept node in the first or second data sets.

9. The method of claim 1, 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.

10. The method of claim 1, wherein transmitting to the client device the structured document comprises transmitting a first base structured document for rendering one or more portions of the profile page corresponding to the first concept node and subsequently transmitting one or more second portions of the structured document that include the code executable by a client application to render node names or other identifiers of the recommended nodes for display.

11. A system comprising:

one or more processors; and

logic encoded in one or more computer-readable tangible storage media that, when executed by the one or more processors, is operable to;

maintain access to a data store of information corresponding to one or more of a plurality of users of a social network environment and one or more of a plurality of concepts and comprising;

a plurality of nodes including a set of user nodes that each correspond to a respective user, and a set of concept nodes that each correspond to a respective concept, each node of the sets of nodes being associated with a corresponding structured document; and

a plurality of edges that each define a connection between a corresponding pair of nodes from the plurality of nodes;

receive a request from a first user corresponding to a first user node for a structured document corresponding to a first concept node;

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

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

generate a score for each concept node in the first and second data sets based at least in part on the number of user nodes connected to both the first user node and to the respective concept nodes in the first and second data sets;

select one or more concept nodes based on their respective scores as recommended nodes; and

transmit to the client device 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.

12. The system of claim 11, wherein the data store of information is indexed into one or more indexes to facilitate the determining of the first and second data sets.

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

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

15. The system of claim 12, wherein a one of the indexes comprises an index of all concepts indexed by corresponding concept IDs that includes, for each particular concept ID, the set of other concepts nodes identified by corresponding IDs that are connected to the particular concept node corresponding to the particular concept ID in the index.

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

17. The system of claim 12, wherein:

to determine the first data set, the logic, when executed by the one or more processors, is operable to send a first nested query to an indexing process that searches the one or more indexes; and

to determine the second data set, the logic, when executed by the one or more processors, is operable to send a second nested query to the indexing process that searches the one or more indexes.

18. The system of claim 11, wherein to generate a score for each concept node, the logic, when executed by the one or more processors, is operable to generate and sum or otherwise combine:

one or more coefficient scores between each 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 concept node in the first and second data sets and the node corresponding to the first user;

one or more coefficient scores between each 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 concept node in the first or second data sets.

19. The system of claim 11, 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.

20. The system of claim 11, wherein to transmit to the client device the structured document, the logic, when executed by the one or more processors, is operable to transmit a first base structured document for rendering one or more portions of the profile page corresponding to the first concept node and subsequently transmit one or more second portions of the structured document that include the code executable by a client application to render node names or other identifiers of the recommended nodes for display.