Automatically generating nodes and edges in an integrated social graph

• US 8,185,558 B1
• Filed: 04/19/2010
• Issued: 05/22/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, Venkataramanan, Nandagopal, Sun, Eric
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): Jacob, Ajith
• Application Number:
  US12/763,145
• Time in Patent Office: 764 Days
• Field of Search: 707/798
• US Class Current: 707/798
• 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:

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;

for each of one or more users;

scanning, by one or more of the computing systems, one or more items of content stored or identified with the user node corresponding to the user;

identifying, by one or more of the computing systems, a candidate item of content from the one or more items of content;

searching, by one or more of the computing systems, the stored information for one or more matches between the candidate item of content and existing nodes from the set of concept nodes;

determining, by one or more of the computing systems, whether or not a match between the candidate item of content and an existing node from the set of concept nodes exists; and

when the one or more computing systems determine that at least one match exists;

generating, by one or more of the computing systems, an edge from the node corresponding to the user to the node from the set of concept nodes for which the best match is determined; and

when the one or more computing systems determine that no match between the candidate item of content and an existing node from the set of concept nodes exists;

generating, by one or more of the computing systems, a new node in the set of concept nodes based on the candidate item of content; and

generating, by the one or more computing systems, an edge from the node corresponding to the user to the new node.

2. The method of claim 1, wherein one or more of the items of content stored or identified with the user node corresponding to the user each comprises one or more strings of textual characters.

3. The method of claim 2, wherein one or more of the items of content stored or identified with the user node corresponding to the user each comprises one or more strings of textual characters stored with the user node for display in a user profile page of the user hosted, at least in part, by the social network environment.

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

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

6. The method of claim 5, 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.

7. The method of claim 5, wherein searching the stored information for one or more matches between the candidate item of content and existing nodes from the set of concept nodes comprises using one or more string matching algorithms to attempt to match each candidate item of content with a string of characters associated with each of the existing nodes.

8. The method of claim 7, wherein determining whether or not a match between the candidate item of content and an existing node from the set of concept nodes exists 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 candidate item of content match the text in the string of characters associated with the existing node.

9. The method of claim 1, wherein:

the data store further comprises concept information comprising a plurality of indexed data objects each of which correspond to a known concept; and

searching the stored information for one or more matches between the candidate item of content and existing nodes from the set of concept nodes and determining whether or not a match between the candidate item of content and an existing node from the set of concept nodes exists comprises;

searching, by one or more of the computing systems, the concept information for one or more matches between the candidate item of content and known concepts;

determining, by one or more of the computing systems, whether or not a match between the candidate item of content and a known concept exists; and

when the one or more computing systems determine that at least one match between the candidate item of content and known concept exists;

determining, by one or more of the computing systems, a best match of the at least one matches;

determining, by one or more computing systems, whether or not an existing node exists in set of concept nodes that corresponds to the best match; and

when the one or more computing systems determine that an existing node exists in the set of concept nodes that corresponds to the best match;

generating, by one or more of the computing systems, an edge from the node corresponding to the user to the node from the set of concept nodes for which the best match is determined; and

when the one or more computing systems determine that no existing node exists in the set of concept nodes that corresponds to the best match;

generating, by one or more of the computing systems, a new node in the set of concept nodes that corresponds to the best match; and

generating, by one or more of the computing systems, an edge from the node corresponding to the user to the existing node corresponding to the best match; and

when the one or more computing systems determine that a match between the candidate item of content and known concept does not exist;

generating, by one or more of the computing systems, a new node in the set of concept nodes that corresponds to the candidate item of content; and

generating, by one or more of the computing systems, an edge from the node corresponding to the user to the new node that corresponds to the candidate item of content.

10. The method of claim 1, wherein:

when the one or more computing systems determine that no match between the candidate item of content and an existing node from the set of concept nodes exists and the one or more of the computing systems generate a new node in the set of concept nodes based on the candidate item of content, the method further comprises;

displaying a user interface to the user in response to the user requesting a structured document corresponding to the new concept node, wherein the user interface includes a list of suggested matches corresponding to other existing concept nodes other than the new concept node; and

generating, by the one or more computing systems, an edge from the node corresponding to the user to the new node comprises generating an edge from the node corresponding to the user to the new node when the user does not select one of the suggested matches.

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;

for each of one or more users;

scan one or more items of content stored or identified with the user node corresponding to the user;

identify a candidate item of content from the one or more items of content;

search the stored information for one or more matches between the candidate item of content and existing nodes from the set of concept nodes;

determine whether or not a match between the candidate item of content and an existing node from the set of concept nodes exists; and

when the one or more computing systems determine that at least one match exists;

generate an edge from the node corresponding to the user to the node from the set of concept nodes for which the best match is determined; and

when the one or more computing systems determine that no match between the candidate item of content and an existing node from the set of concept nodes exists;

generate a new node in the set of concept nodes based on the candidate item of content; and

generate an edge from the node corresponding to the user to the new node.

12. The system of claim 11, wherein one or more of the items of content stored or identified with the user node corresponding to the user each comprises one or more strings of textual characters.

13. The system of claim 12, wherein one or more of the items of content stored or identified with the user node corresponding to the user each comprises one or more strings of textual characters stored with the user node for display in a user profile page of the user 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 the user in one or more respective user input forms hosted, at least in part, by the social network environment for display in the user profile page of the user.

15. The system of claim 14, wherein the logic is further operable when executed to preprocess the one or more strings of textual characters.

16. The system of claim 15, wherein to preprocess the one or more strings of textual characters, the logic is operable when executed to apply 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 15, wherein to search the stored information for one or more matches between the candidate item of content and existing nodes from the set of concept nodes, the logic is operable when executed to use one or more string matching algorithms to attempt to match each candidate item of content with a string of characters associated with each of the existing nodes.

18. The system of claim 17, wherein to determine whether or not a match between the candidate item of content and an existing node from the set of concept nodes exists, the logic is operable to compute 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 candidate item of content match the text in the string of characters associated with the existing node.

19. The system of claim 11, wherein:

the data store further comprises concept information comprising a plurality of indexed data objects each of which correspond to a known concept; and

the logic operable to search the stored information for one or more matches between the candidate item of content and existing nodes from the set of concept nodes and determine whether or not a match between the candidate item of content and an existing node from the set of concept nodes exists comprises logic operable when executed to;

search the concept information for one or more matches between the candidate item of content and known concepts;

determine whether or not a match between the candidate item of content and a known concept exists; and

when it is determined that at least one match between the candidate item of content and known concept exists;

determine a best match of the at least one matches;

determine whether or not an existing node exists in set of concept nodes that corresponds to the best match; and

when it is determined that an existing node exists in the set of concept nodes that corresponds to the best match;

generate an edge from the node corresponding to the user to the node from the set of concept nodes for which the best match is determined; and

when it is determined that no existing node exists in the set of concept nodes that corresponds to the best match;

generate a new node in the set of concept nodes that corresponds to the best match; and

generate an edge from the node corresponding to the user to the existing node corresponding to the best match; and

when it is determined that a match between the candidate item of content and known concept does not exist;

generate a new node in the set of concept nodes that corresponds to the candidate item of content; and

generate an edge from the node corresponding to the user to the new node that corresponds to the candidate item of content.

20. The system of claim 11, wherein:

when it is determined that no match between the candidate item of content and an existing node from the set of concept nodes exists and a new node is generated in the set of concept nodes based on the candidate item of content, the logic is further operable when executed to;

display a user interface to the user in response to the user requesting a structured document corresponding to the new concept node, wherein the user interface includes a list of suggested matches corresponding to other existing concept nodes other than the new concept node; and

the logic is operable when executed to generate an edge from the node corresponding to the user to the new node when the user does not select one of the suggested matches.