Automatically Generating Nodes and Edges in an Integrated Social Graph

• US 20120221581A1
• Filed: 05/07/2012
• Published: 08/30/2012
• Est. Priority Date: 04/19/2010
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Eric Sun, Nandagopal Venkataramanan, Srinivas Narayanan
• Inventors: Narayanan, Srinivas, Venkataramanan, Nandagopal, Sun, Eric
• Granted Patent: US 9,002,898 B2
• Time in Patent Office: Days
• US Class Current: 707/748
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/903 Querying for retrieval from the web G06F16/953
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06F 3/0482 Interaction with lists of selectable items, e.g. menus
• CPC Class Codes: G06F 3/04842 Selection of displayed objects or displayed text elements G06F3/0482 takes precedence
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04W 4/21 for social networking applications

Abstract

In one embodiment, a method includes maintaining a data store of nodes and edges and for each of one or more users: scanning items of content associated with the corresponding user node; identifying a candidate item of content; searching for matches between the candidate item of content and existing nodes; determining whether or not a match between the candidate item of content and an existing node exists; and when it is determined that at least one match exists, generating an edge from the user node to the existing node for which the best match is determined; and when it is determined that no match exists, generating a new node based on the candidate item of content, and generating an edge from the user node to the new node.

Claims

1. A method comprising:

scanning, by one or more processors associated with one or more computing systems, one or more items of content stored in a data store of information, the 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 (1) a set of user nodes that each correspond to a respective user and (2) a set of concept nodes that each correspond to a respective concept, each node of the plurality of nodes being associated with a corresponding structured document, and each of the one or more items of content being associated with at least one node of the plurality of nodes; 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 processors, a request from a user of the social network environment for at least one item of content;

determining, by the one or more processors, that the requested at least one item of content matches one or more nodes of the plurality of nodes;

determining, by the one or more processors, one or more nodes to recommend based on the requested at least one item of content and the one or more matching nodes; and

transmitting, by the one or more processors, information to display the requested at least one item of content and information associated with the one or more recommended nodes.

2. The method of claim 1, further comprising:

receiving an indication that the user clicked on the information associated with one of the recommended nodes; and

generating, by the one or more processors, an edge from the node corresponding to the user to the one of the recommended nodes.

3. The method of claim 1, wherein one or more of the items of content stored in the data store of information comprises one or more strings of textual characters.

4. The method of claim 3, wherein one or more of the items of content stored in the data store of information each comprises one or more strings of textual characters stored with the associated node for display in a profile page of the node hosted, at least in part, by the social network environment.

5. The method of claim 4, wherein the one or more strings of textual characters were entered by a user in one or more respective user input forms hosted, at least in part, by the social network environment for display in the profile page of the node.

6. The method of claim 5, further comprising performing, by the one or more computer systems, preprocessing of the one or more strings of textual characters.

7. The method of claim 6, wherein preprocessing of the one or more strings of textual characters comprises applying a set of heuristic rules to parse, separate, or delimit the one or more strings into one or more separate words or phrases each to be considered and identified as a candidate item of content.

8. The method of claim 7, wherein determining that the requested at least one item of content matches an existing node of the plurality of nodes comprises using one or more string matching algorithms to attempt to match the requested at least one item of content with a string of characters associated with the existing node.

9. The method of claim 8, wherein determining that the requested at least one item of content matches an existing node of the plurality of nodes comprises computing a confidence score for each attempted match based on one or more of:

a determination of how well the text in the string of textual characters of the requested at least one item of content match the text in the string of characters associated with the existing node.

10. 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;

scan one or more items of content stored in a data store of information, the 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 (1) a set of user nodes that each correspond to a respective user and (2) a set of concept nodes that each correspond to a respective concept, each node of the plurality of nodes being associated with a corresponding structured document, and each of the one or more items of content being associated with at least one node of the plurality of nodes; 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 user of the social network environment for at least one item of content;

determine that the requested at least one item of content matches one or more nodes of the plurality of nodes;

determine one or more nodes to recommend based on the requested at least one item of content and the one or more matching nodes; and

transmit information to display the requested at least one item of content and information associated with the one or more recommended nodes.

11. The system of claim 10, further comprising logic operable to:

receive an indication that the user clicked on the information associated with one of the recommended nodes; and

generate, by the one or more processors, an edge from the node corresponding to the user to the one of the recommended nodes.

12. The system of claim 10, wherein one or more of the items of content stored in the data store of information comprises one or more strings of textual characters.

13. The system of claim 12, wherein one or more of the items of content stored in the data store of information each comprises one or more strings of textual characters stored with the associated node for display in a profile page of the node hosted, at least in part, by the social network environment.

14. The system of claim 13, wherein the one or more strings of textual characters were entered by a user in one or more respective user input forms hosted, at least in part, by the social network environment for display in the profile page of the node.

15. The system of claim 14, further comprising logic operable to perform, by the one or more computer systems, preprocess the one or more strings of textual characters.

16. The system of claim 15, wherein preprocessing of the one or more strings of textual characters comprises applying a set of heuristic rules to parse, separate, or delimit the one or more strings into one or more separate words or phrases each to be considered and identified as a candidate item of content.

17. The system of claim 16, wherein the logic operable to determine that the requested at least one item of content matches an existing node of the plurality of nodes comprises using one or more string matching algorithms to attempt to match the requested at least one item of content with a string of characters associated with the existing node.

18. The system of claim 17, wherein the logic operable to determine that the requested at least one item of content matches an existing node of the plurality of nodes comprises computing a confidence score for each attempted match based on one or more of:

a determination of how well the text in the string of textual characters of the requested at least one item of content match the text in the string of characters associated with the existing node.

19. One or more computer-readable non-transitory storage media embodying software that is operable when executed by one or more processors associated with one or more computer systems to

scan, by the one or more processors, one or more items of content stored in a data store of information, the 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 (1) a set of user nodes that each correspond to a respective user and (2) a set of concept nodes that each correspond to a respective concept, each node of the plurality of nodes being associated with a corresponding structured document, and each of the one or more items of content being associated with at least one node of the plurality of nodes; and

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

receive, by the one or more processors, a request from a user of the social network environment for at least one item of content;

determine, by the one or more processors, that the requested at least one item of content matches one or more nodes of the plurality of nodes;

determine, by the one or more processors, one or more nodes to recommend based on the requested at least one item of content and the one or more matching nodes; and

transmit, by the one or more processors, information to display the requested at least one item of content and information associated with the one or more recommended nodes.