SYSTEMS, METHODS AND SOFTWARE FOR COMPUTING REACHABILITY IN LARGE GRAPHS

摘要

Embodiments disclosed herein provide systems and methods for scaling reachability computations on relatively large graphs. In an embodiment, a method provides for scaling reachability computations on relatively large graphs, the method comprising, identifying an initial graph comprising a plurality of vertices and a plurality of edges, processing at least a portion of the plurality of vertices and at least a portion of the plurality of edges to generate a plurality of reachability indices for the at least a portion of the plurality of vertices, and generating a backbone graph comprising a scaled-down version of the initial graph, based at least in part on at least one of the plurality of reachability indices.

主权项

1. A method for scaling reachability computations on relatively large graphs, the method comprising:
identifying an initial graph comprising a plurality of vertices and a plurality of edges;
identifying a backbone graph within the initial graph at least in part by a graph creation module; creating a subsequent graph comprising a scaled-down version of the initial graph, based at least in part on the backbone graph, at least in part by the graph creation module; and computing the reachability of at least two of the vertices using at least the subsequent graph at least in part with a processor and a reachability analytics module.