Automatically generating nodes and edges in an integrated social graph

• US 9,342,623 B2
• Filed: 10/08/2013
• Issued: 05/17/2016
• 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, Srinivasa, Nandagopal, Venkataramanan, Sun, Eric
• Primary Examiner(s): Jacob, Ajith
• Application Number:
  US14/049,117
• Publication Number:
  US 20140040300A1
• Time in Patent Office: 952 Days
• Field of Search: 707/798
• US Class Current: 1/1
• 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 access to a data store of information corresponding to nodes and edges; receiving a user-generated character string comprising one or more characters of text entered by a user in an input form as they are entered by the user; searching the stored information for matches between the user-generated character string and existing nodes; determining whether or not a match between the user-generated character string and an existing node exists; and when it is determined that at least one match exists, generating an edge between the node corresponding to the user and the node for which the best match is determined; and when it is determined that no match between the user-generated character string and an existing node exists, generating a new node based on the user-generated character string, and generating an edge between the node corresponding to the user and 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;

receiving, by one or more of the computing systems, from a client device, a user-generated character string comprising one or more characters of text entered by a user in an input form rendered at the client device as they are entered by the user;

searching, by one or more of the computing systems, the stored information for one or more matches between the user-generated character string and existing nodes from the set of concept nodes;

determining, by one or more of the computing systems, whether a match between the user-generated character string and an existing node from the set of concept nodes exists; and

generating, by one or more of the computing systems, in response to determining that at least one match exists, an edge between the node corresponding to the user and the node for which the best match is determined.

2. The method of claim 1, wherein the user-generated character string is received from a client-side process executing within the client device or from a client-side document rendering application in response to one or more instructions from the client-side process.

3. The method of claim 2, wherein the client-side process is transmitted from one or more of the computing systems to the client device in a first structured document transmitted to the client device in response to a request received by one or more of the computing systems for the first structured document.

4. The method of claim 1, further comprising receiving, by one or more of the computing systems, a section identifier that identifies a category of a section of a user profile page corresponding to the input form in which the user-generated character string was entered.

5. The method of claim 4, wherein searching the stored information for one or more matches between the user-generated character string and existing nodes from the set of concept nodes comprises searching the stored information for matches between the user-generated character string and existing nodes from the set of concept nodes that have corresponding category identifiers that match the category of the section identifier.

6. The method of claim 1, wherein searching the stored information for one or more matches between the user-generated character string and existing nodes from the set of concept nodes comprises using one or more string matching algorithms to attempt to match the user-generated character string with a string of characters associated with each of one or more of the existing nodes.

7. The method of claim 6, wherein determining whether or not a match between the user-generated character string 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 user-generated character string matches the text in the string of characters associated with the existing node.

8. The method of claim 7, wherein the confidence score is further computed based on one or more other factors including one or more of:

the number of the other users having respective user nodes connected to the user'"'"'s node and to the existing concept node, the number of total users having respective user nodes connected to the existing concept node, the number of other existing concept nodes connected to the existing node.

9. The method of claim 1, further comprising, when the one or more computing systems determine that at least one match exists, transmitting, by the one or more computing systems, a response to the client device that includes the name or other identifier of the node which the best match is determined;

and

auto-populating, by the client-side process, the input form with the name or other identifier of the node for which the best match is determined.

10. The method of claim 9, generating an edge between the node corresponding to the user and the node for which the best match is determined comprises generating an edge between the node corresponding to the user and the node for which the best match is determined in response to the user clicking or otherwise selecting the auto-populated name or other identifier of the node.

11. The method of claim 1, further comprising, in response to determining that no match between the user-generated character string 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 user-generated character string; and

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

12. 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 from a client device a user-generated character string comprising one or more characters of text entered by a user in an input form rendered at the client device as they are entered by the user;

search the stored information for one or more matches between the user-generated character string and existing nodes from the set of concept nodes;

determine whether or not a match between the user-generated character string and an existing node from the set of concept nodes exists; and

generate in response to determining that at least one match exists, an edge between the node corresponding to the user and the node for which the best match is determined.

13. The system of claim 12, wherein the user-generated character string is received from a client-side process executing within the client device or from a client-side document rendering application in response to one or more instructions from the client-side process.

14. The system of claim 13, wherein the client-side process is transmitted to the client device in a first structured document transmitted to the client device in response to a request for the first structured document.

15. The system of claim 12, wherein the logic operable when executed to receive the user-generated character string is further operable when executed to receive a section identifier that identifies a category of a section of a user profile page corresponding to the input form in which the user-generated character string was entered.

16. The system of claim 15, wherein the logic operable when executed to search the stored information for one or more matches between the user-generated character string and existing nodes from the set of concept nodes comprises logic operable when executed to search the stored information for matches between the user-generated character string and existing nodes from the set of concept nodes that have corresponding category identifiers that match the category of the section identifier.

17. The system of claim 12, wherein the logic operable when executed to search the stored information for one or more matches between the user-generated character string and existing nodes from the set of concept nodes comprises logic operable when executed to use one or more string matching algorithms to attempt to match the user-generated character string with a string of characters associated with each of one or more of the existing nodes.

18. The system of claim 17, wherein the logic operable when executed to determine whether or not a match between the user-generated character string and an existing node from the set of concept nodes exists comprises logic operable when executed to compute a confidence score for each attempted match based on one or more of:

a determination of how well the text in the user-generated character string matches the text in the string of characters associated with the existing node.

19. The system of claim 12, wherein the logic is further operable when executed to, in response to determining that no match between the user-generated character string and an existing node from the set of concept nodes exists:

generate a new node in the set of concept nodes based on the user-generated character string; and

generate an edge between the node corresponding to the user and the new node.

20. One or more computer-readable non-transitory storage media embodying software that is operable when executed 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 from a client device a user-generated character string comprising one or more characters of text entered by a user in an input form rendered at the client device as they are entered by the user;

search the stored information for one or more matches between the user-generated character string and existing nodes from the set of concept nodes;

determine whether or not a match between the user-generated character string and an existing node from the set of concept nodes exists; and

generate in response to determining that at least one match exists, an edge between the node corresponding to the user and the node for which the best match is determined.