Partial graph incremental update in a social network

• US 9,892,210 B2
• Filed: 11/18/2014
• Issued: 02/13/2018
• Est. Priority Date: 10/31/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Cho, SungJu, Niu, Qingpeng, Carter, Andrew Joseph, Sachdev, Sanjay
• Primary Examiner(s): Chen, Susan
• Application Number:
  US14/546,790
• Publication Number:
  US 20160125093A1
• Time in Patent Office: 1,183 Days
• Field of Search: None
• 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 vertex-centric partial graph for the node, the vertex-centric partial graph identifying the node as a vertex with a specific vertex node and containing nodes from the partial graph, the nodes from the partial graph being only nodes reachable within limited hops from the node, wherein a hop is a distance of one edge between nodes;

determining a list of the nodes reachable in one hop, without intermediate nodes, from the vertex;

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 exactly two hops from the vertex, and reference counts as to how many distinct paths exist, in the social graph, between the vertex and each of the nodes reachable in exactly two hops from the vertex; 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

distributing the global inverted index containing the list of all directly connected nodes to the data servers to facilitate a network computer breadth-first distance traversal.

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 for 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 for 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 for the partial graph corresponding to a node in the social graph contains the node in the social graph.

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 vertex-centric partial graphs, each vertex-centric partial graph corresponding to a different node in a social graph, identifying the node as a vertex with a specific vertex node identifier, and containing nodes from the partial graph that are only reachable within limited hops from the node, 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, without intermediate nodes, from the particular node and also including a second degree list of nodes reachable in exactly two hopes from the particular node, as well as reference counts as to how many distinct paths exist, in the social graph, 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, the global inverted index being distributed to data servers to facilitate a network computer breadth-first distance traversal.

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 for 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 vertex-centric partial graph for the node, the vertex-centric partial graph identifying the node as a vertex with a specific vertex node and containing nodes from the partial graph, the nodes from the partial graph being only nodes reachable within limited hops from the node, wherein a hop is a distance of one edge between nodes;

determining a list of the nodes reachable in one hop, without intermediate nodes, from the vertex;

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 exactly two hops from the vertex, and reference counts as to how many distinct paths exist, in the social graph, between the vertex and each of the nodes reachable in exactly two hops from the vertex; 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

distributing the global inverted index containing the list of all directly connected nodes to the data servers to facilitate a network computer breadth-first distance traversal.

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 for 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 for the partial graph corresponding to the node contains the node.

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.