PARTIAL GRAPH INCREMENTAL UPDATE IN A SOCIAL NETWORK

• US 20160125093A1
• Filed: 11/18/2014
• Published: 05/05/2016
• Est. Priority Date: 10/31/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: LinkedIn Corporation (Microsoft Corporation)
• Inventors: Cho, SungJu, Sachdev, Sanjay, Niu, Qingpeng, Carter, Andrew Joseph
• Granted Patent: US 9,892,210 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 65/403 Arrangements for multi-party communication, e.g. for conferences data switching systems for conference H04L12/18; arrangements for connecting several subscribers to a common circuit, i.e. affording conference facilities H04M3/56; television conferencing systems H04N7/15

Abstract

A social graph is divided into a series of partial graphs having limited hops and reference counts. For each of a plurality of nodes in the social graph, a partial graph for the node is created having a first degree list of nodes reachable in one hop and a second degree list of nodes reachable in two hops. Reference counts of how many paths exist between the node and each node reachable in two hops are also added to the second degree list. A global inverted index is maintained containing a list of all nodes in the social graph and for each node in the social graph a list of nodes that directly connect to the node. The partial graphs created for each of the plurality of nodes are distributed across a plurality of data servers. An index of which partial graphs are stored on which data servers is maintained.

Claims

1. A computer-implemented method comprising:

retrieving a social graph including a plurality of nodes and a plurality of edges, each of the nodes corresponding to a member in a social network service and each of the edges representing a connection between members of the social network service;

for each node of the plurality of nodes in the social graph;

creating a partial graph for the node;

determining a list of the nodes reachable in one hop from the node;

adding the list of nodes reachable in one hop to a first degree list for the partial graph;

determining a list of nodes reachable in two hops from the node, and reference counts as to how many paths exist between the node and each of the nodes reachable in two hops from the node; and

adding the list of nodes reachable in two hops and the reference counts to a second degree list for the partial graph;

maintaining a global inverted index containing a list of all nodes in the social graph and for each node in the social graph a list of nodes that directly connect to the node in the social graph;

distributing the partial graphs created for each of the plurality of nodes across a plurality of data servers; and

maintaining an index of which partial graphs are stored on which data servers.

2. The computer-implemented method of claim 1, further comprising:

receiving a request to add a connection from a first node to a second node in the social graph;

using the index of which partial graphs are stored on which data servers to determine a data server storing a partial graph corresponding to the first node;

obtaining the partial graph corresponding to the first node from the data server storing the partial graph corresponding to the first node;

determining whether the first degree list in the partial graph corresponding to the first node contains the second node;

in response to a determination that the first degree list in the partial graph corresponding to the first node does not contain the second node, adding the second node to the first degree list in the partial graph corresponding to the first node;

for each node that the global inverted index lists as directly connecting to the first node;

using the index of which partial graphs are stored on which data servers to determine a data server storing a partial graph corresponding to the node that the global inverted index lists;

obtaining the partial graph corresponding to the node from the data server storing the partial graph corresponding to the node; and

incrementing a reference count corresponding to the second node in the second degree list in the partial graph corresponding to the node; and

updating the global inverted index to add the first node to the list of nodes that directly connect to the second node.

3. The computer-implemented method of claim 1, further comprising:

receiving a request to delete a connection from a first node to a second node in the social graph;

using the index of which partial graphs are stored on which data servers to determine a data server storing a partial graph corresponding to the first node;

obtaining the partial graph corresponding to the first node from the data server storing the partial graph corresponding to the first node;

removing the second node from the first degree list in the partial graph corresponding to the first node;

for each node that the global inverted index lists as directly connecting to the first node;

using the index of which partial graphs are stored on which data servers to determine the data server storing the partial graph corresponding to the node in the social graph;

obtaining the partial graph corresponding to the node from the data server storing the partial graph corresponding to the node;

decrementing a reference count corresponding to the second node in the second degree list in the partial graph corresponding to the node; and

updating the global inverted index to remove the first node from the list of nodes that directly connect to the second node.

4. The computer-implemented method of claim 1, wherein the second degree list in the partial graph corresponding to a node in the social graph contains the node in the social graph if appropriate.

5. The computer-implemented method of claim 1, wherein each of the plurality of data servers stores more than one partial graph.

6. The computer-implemented method of claim 1, wherein the global inverted index is stored on each of the plurality of data servers.

7. The computer-implemented method of claim 1, wherein the global inverted index is stored on a central controller.

8. A data server comprising:

a content store containing one or more partial graphs, each partial graph corresponding to a different node in a social graph, the social graph including a plurality of nodes and a plurality of edges, each of the nodes corresponding to a member in a social network service and each of the edges representing a connection between members of the social network service, the partial graph for a particular node including a first degree list of the nodes reachable in one hop from the particular node and also including a second degree list of nodes reachable in two hopes from the particular node, as well as reference counts as to how many paths exist between the particular node and each node reachable in two hops from the node; and

a logic component comprising one or more processors configured to

alter the one or more partial graphs stored in the content store, including the first degree lists, second degree lists, and reference counts, in response to the addition or deletion of a connection from a first node in the social graph to a second node; and

cause the altering of an inverted index entry corresponding the first node in a global inverted index.

9. The data server of claim 8, wherein the logic component is further configured to:

based on additional nodes in the social graph contained in an entry corresponding to the first node in the global inverted index, obtain locations of one or more additional data servers storing partial graphs pertaining to the additional nodes and pass instructions to alter the partial graphs pertaining to the additional nodes to the one or more additional data servers.

10. The data server of claim 8, wherein the altering of the one or more partial graphs includes, in response to a request to add a connection from the first node to the second node:

obtaining the partial graph corresponding to the first node;

determining whether the first degree list in the partial graph corresponding to the first node contains the second node;

in response to a determination that the first degree list in the partial graph corresponding to the first node does not contain the second node, adding the second node to the first degree list in the partial graph corresponding to the first node;

11. The data server of claim 9, wherein the instructions include instruction to:

for each node that the global inverted index lists as directly connecting to the first node;

obtain the partial graph corresponding to the node contained in the inverted index entry corresponding to the first node; and

increment the reference count corresponding to the second node in the second degree list in the partial graph corresponding to the node contained in the inverted index entry corresponding to the first node.

12. The data server of claim 8, wherein the altering of the one or more partial graphs includes, in response to a request to delete the connection from the first node to the second node:

obtaining the partial graph corresponding to the first node; and

remove the second node to the first degree list in the partial graph corresponding to the first node;

13. The data server of claim 9, wherein the instructions include instruction to:

for each node that the global inverted index lists as directly connecting to the first node;

obtain the partial graph corresponding to the node contained in the inverted index entry corresponding to the first node; and

decrement the reference count corresponding to the second node in the second degree list in the partial graph corresponding to the node contained in the inverted index entry corresponding to the first node.

14. A non-transitory computer-readable medium storing executable instructions thereon, which, when executed by a processor, causes the processor to perform operations comprising:

retrieving a social graph including a plurality of nodes and a plurality of edges, each of the nodes corresponding to a member in a social network service and each of the edges representing a connection between members of the social network service;

for each node of the plurality of nodes in the social graph;

creating a partial graph for the node;

determining a list of the nodes reachable in one hop from the node;

adding the list of nodes reachable in one hop to a first degree list for the partial graph;

determining a list of nodes reachable in two hops from the node, and reference counts as to how many paths exist between the node and each of the nodes reachable in two hops from the node; and

adding the list of nodes reachable in two hops and the reference counts to a second degree list for the partial graph;

maintaining a global inverted index containing a list of all nodes in the social graph and for each node in the social graph a list of nodes that directly connect to the node in the social graph;

distributing the partial graphs created for each of the plurality of nodes across a plurality of data servers; and

maintaining an index of which partial graphs are stored on which data servers.

15. The non-transitory computer-readable medium of claim 14, wherein the operations further comprise:

receiving a request to add a connection from a first node to a second node in the social graph;

using the index of which partial graphs are stored on which data servers to determine the data server storing the partial graph corresponding to the first node;

obtaining the partial graph corresponding to the first node from the data server storing the partial graph corresponding to the first node;

determining whether the first degree list in the partial graph corresponding to the first node contains the second node;

in response to a determination that the first degree list in the partial graph corresponding to the first node does not contain the second node, adding the second node to the first degree list in the partial graph corresponding to the first node;

for each node that the global inverted index lists as directly connecting to the first node;

using the index of which partial graphs are stored on which data servers to determine the data server storing the partial graph corresponding to the node;

obtaining the partial graph corresponding to the node from the data server storing the partial graph corresponding to the node; and

incrementing a reference count corresponding to the second node in the second degree list in the partial graph corresponding to the node; and

updating the global inverted index to add the first node to the list of nodes that directly connect to the second node.

16. The non-transitory computer-readable medium of claim 14, wherein the operations further comprise:

receiving a request to delete a connection from a first node to a second node in the social graph;

using the index of which partial graphs are stored on which data servers to determine a data server storing a partial graph corresponding to the first node;

obtaining the partial graph corresponding to the first node from the data server storing the partial graph corresponding to the first node;

removing the second node from the first degree list in the partial graph corresponding to the first node;

for each node that the global inverted index lists as directly connecting to the first node;

using the index of which partial graphs are stored on which data servers to determine a data server storing a partial graph corresponding to the node;

obtaining the partial graph corresponding to the node from the data server storing the partial graph corresponding to the node;

decrementing the reference count corresponding to the second node in the second degree list in the partial graph corresponding to the node; and

updating the global inverted index to remove the first node to the list of nodes that directly connect to the second node.

17. The non-transitory computer-readable medium of claim 14, wherein the second degree list in the partial graph corresponding to the node contains the node if appropriate.

18. The non-transitory computer-readable medium of claim 14, wherein each of the plurality of data servers stores more than one partial graph.

19. The non-transitory computer-readable medium of claim 14, wherein the global inverted index is stored on each of the plurality of data servers.

20. The non-transitory computer-readable medium of claim 14, wherein the global inverted index is stored on a central controller.