Compressing dependency graphs in a social network

• US 8,997,072 B1
• Filed: 08/23/2012
• Issued: 03/31/2015
• Est. Priority Date: 07/13/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wong, Henry
• Primary Examiner(s): Bullock, Jr., Lewis A
• Assistant Examiner(s): GOORAY, MARK A
• Application Number:
  US13/593,406
• Time in Patent Office: 950 Days
• Field of Search: None
• US Class Current: 717/157
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]

Abstract

This technology is directed to compressing dependency graphs in online communities, e.g., social networks, by determining a dependency graph and by performing a transitive reduction on the dependency graph. The transitive reduction may be used in various applications, e.g., for loading software modules in social networks, without causing inefficiencies by loading the same modules multiple times. In some instances, the systems and methods include 1) sorting nodes (e.g., modules) in the dependency graph into a list in a valid dependency order (a node depends only on nodes earlier in the list), 2) iterating over the list while building a map from any node to all of its dependencies, 3) iterating through the dependency graph in reverse order, and for each node, iterating through its dependencies (also in reverse order) and removing each dependency if it is a transitive dependency of any of the previous dependencies of that node.

Claims

1. A computer-implemented method for compressing a dependency graph in a social network, by replacing the dependency graph with a transitive reduction, the method comprising:

receiving, using the one or more computing devices, the dependency graph;

sorting, using the one or more computing devices, one or more nodes in the dependency graph, into a valid dependency ordering, wherein nodes depend on nodes that appear earlier in a list of nodes for the dependency graph;

iterating, using the one or more computing devices, through the dependency graph in valid dependency ordering, by creating a dependency map of dependencies determined for each of the one or more nodes in the list;

iterating, using the one or more computing devices, through the dependency graph in valid dependency ordering, for each node in the dependency graph, in reverse order, wherein the iterating in reverse order further comprises;

starting at a last indicated dependency of an end node in the dependency map for each node in the dependency graph, and iterating, using the one or more computing devices, through the one or more dependent nodes in the dependency map to a beginning node in the dependency map, in reverse order to determine whether each single dependency of a dependent node is representative of a transitive dependency for any previous iterated dependencies, wherein a transitive dependency comprises a dependency on a node that is already dependent on another node; and

in response to determining a transitive dependency, removing, using the one or more computing devices, the single dependency.

2. A computer-implemented method for compressing a dependency graph in a social network, the method comprising:

receiving, using the one or more computing devices, the dependency graph;

sorting, using the one or more computing devices, one or more nodes in the dependency graph, into a valid dependency ordering, wherein nodes depend on nodes that appear earlier in a list of nodes for the dependency graph;

creating, using the one or more computing devices, a map from each of the one or more nodes of dependencies determined for each of the one or more nodes in the list, to iterate through the dependency graph in valid dependency ordering;

determining, using the one or more computing devices, one or more redundant dependencies for the one or more nodes in the dependency graph by iterating through the dependency graph in valid dependency ordering, for each node in the dependency graph, in reverse order, wherein the iterating in reverse order further comprises;

starting at a last indicated dependency of an end node in the dependency map for each node in the dependency graph, and iterating, using the one or more computing devices, through the one or more dependent nodes in the dependency map to a beginning node in the dependency map, in reverse order to determine whether each single dependency of a dependent node is representative of a transitive dependency for any previous iterated dependencies, wherein a transitive dependency comprises a dependency on a node that is already dependent on another node, and

replacing using the one or more computing devices, the dependency graph with a transitive reduction, removing the one or more redundant dependencies.

3. A computer-implemented method according to claim 2, wherein the one or more nodes include one or more software modules.

4. A computer-implemented method according to claim 3, further comprising:

in response to loading dependencies of the one or more nodes, loading the one or more software modules.

5. A computer-implemented method according to the claim 2, wherein the computer-implemented method is configured as a graph compressor application, at least a portion of which is hosted on one or more social network servers.

6. A computer-implemented method according to claim 2, wherein the computer-implemented method is configured as a graph compressor application, at least a portion of which is hosted on one or more third party servers.

7. A computer-implemented method according to claim 2, wherein the computer-implemented method is configured as a graph compressor application, at least a portion of which is hosted on a user device.

8. A computer-implemented method according to claim 2, wherein the computer-implemented method is configured as a graph compressor application, at least a portion of which is hosted on one or more of a social network server, a third party server, and a user device.

9. A computer-implemented method implemented by readable program code encoded in a non-transitory computer-readable medium, the program code further comprising instructions for:

receiving, computing devices, the dependency graph;

sorting, using the one or more computing devices, one or more nodes in the dependency graph, into a valid dependency ordering, wherein nodes depend on nodes that appear earlier in a list of nodes for the dependency graph;

iterating, using the one or more computing devices, through the dependency graph in valid dependency ordering, by creating a dependency map of dependencies determined for each of the one or more nodes in the list;

iterating, using the one or more computing devices, through the dependency graph in valid dependency ordering, for each node in the dependency graph, in reverse order, wherein the iterating in reverse order further comprises;

starting at a last indicated dependency of an end node in the dependency map for each node in the dependency graph, and iterating, using the one or more computing devices, through the one or more dependent nodes in the dependency map to a beginning node in the dependency map, in reverse order to determine whether each single dependency of a dependent node is representative of a transitive dependency for any previous iterated dependencies, wherein a transitive dependency comprises a dependency on a node that is already dependent on another node; and

in response to determining a transitive dependency, removing, using the one or more computing devices, the single dependency.

10. A computer-implemented method according to claim 9, wherein the one or more nodes include one or more software modules.

11. A computer-implemented method according to claim 9, wherein:

in response to loading dependencies of the one or more software modules, loading the one or more software modules.

12. A system, comprising:

a processor and a memory for storing instructions that cause the processor to compress a dependency graph by replacing the dependency graph with a transitive reduction, further comprising;

a graph receiver module configured to receive the dependency graph;

a sorting module configured to sort one or more nodes in the dependency graph into a valid dependency ordering, wherein nodes depend on nodes that appear earlier in a list of nodes for the dependency graph;

a dependency map module configured to iterate, through the one or more nodes in valid dependency order, by creating a dependency map of dependencies determined for each of the one or more nodes in the list; and

a dependency remover module configured to iterate, through the one or more nodes, in reverse order, determining one or more redundant dependencies for the one or more nodes in the dependency graph by iterating through the dependency graph in valid dependency ordering, for each node in the dependency graph, in reverse order, wherein the iterating in reverse order further comprises starting at a last indicated dependency of an end node in the dependency map for each node in the dependency graph, and iterating through the one or more dependent nodes in the dependency map to a beginning node in the dependency map, in reverse order to determine whether each single dependency of a dependent node is representative of a transitive dependency for any previous iterated dependencies, wherein a transitive dependency comprises a dependency on a node that is already dependent on another node, and

in response to a single dependency being a transitive dependency of any previous iterated dependencies, configured to remove, the single dependency.

13. A system according to claim 12, wherein the one or more nodes include one or more software modules.

14. A system according to claim 13, further comprising:

a program execution module, in response to loading dependencies of the one or more software modules, configured to execute the one or more software modules.

15. A system according to the claim 12, wherein at least a portion of the system is hosted on one or more social network servers.

16. A system according to claim 12, wherein at least a portion of the system is hosted on one or more third party servers.

17. A system according to claim 12, wherein at least a portion of the system is hosted on a user device.

18. A system according to claim 12, wherein at least a portion of the system is hosted one or more of a social network server, a third party server, and a user device.