Compressing dependency graphs in a social network

摘要

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.