Writing Algorithms

A common way to express algorithms in SGL is in the vertex-centric manner. In this approach, the developer adopts the ‘think like a vertex’ paradigm. This has the advantage to be easy to the user and reason about, as well as expose a large amount of parallelism in the problem. The user writes two operators -- a vertex-operator and a neighbor operator. These operators sufficiently express the graph algorithm -- the vertex operator performs computation of the algorithm on the vertex, producing a result, while the neighbor operator updates the neighboring vertices of this vertex with this result (figure-1). SGL provides multiple paradigms that can use these operators to efficiently process the graph:

  1. The k-Level Asynchronous (KLA) Paradigm -- unified asynchronous and BSP processing of general graphs.
  2. Hybrid Out-of-Core Paradigm -- for efficient processing of out-of-core graphs.
  3. Hierarchical Communication Reduction Paradigm -- for fast processing of Power-Law graphs.
  4. Hierarchical Graph Paradigm -- for expressing naturally hierarchical algorithms.

Using these, SGL provides 30+ commonly used graph algorithms as standard, using this paradigm, including various traversals, centrality metrics, and a multitude of graph mining and graph analytic algorithms. We will now go over how the computation proceeds to execute the algorithm.

First a computation is applied to an active vertex:

Then, the result of this computation is propagated to the vertex's neighbors (or other specified vertices):

Finally, the neighbors are updated with this information:

results matching ""

    No results matching ""