vertexcentric

Vertexcentric, sometimes written vertex-centric, refers to a model for parallel graph processing in which computation is expressed from the perspective of individual vertices. In this model, each vertex maintains local state and executes a user-defined function in repeated rounds called supersteps. During a superstep, a vertex processes incoming messages, updates its state, and sends messages to its neighbors for the next step. The approach is typically implemented within a bulk synchronous parallel (BSP) framework.

In a vertex-centric system the graph is distributed across multiple workers. In every superstep, all active vertices perform computation in parallel, consuming messages delivered in that step and emitting messages for the subsequent step. Computation converges when no vertex issues new messages and all vertices become inactive, at which point the global result is produced.

Prominent examples of vertex-centric systems include Google's Pregel, which popularized the model; Apache Giraph, an open-source implementation inspired by Pregel; and GraphX in Apache Spark, which provides a Pregel-like API. Other BSP-oriented frameworks, such as Hama and various GraphLab variants, also support vertex-centric programming. The model is well suited to a range of graph algorithms, including PageRank, shortest paths, connected components, label propagation, and community detection.

Advantages of the vertex-centric approach include natural expression of local computations, scalability to large graphs, and efficient communication through message passing on sparse structures. Limitations include potential inefficiency for algorithms requiring global state or heavy cross-vertex coordination, overhead from message traffic and barrier synchronization, sensitivity to graph partitioning and load balance, and debugging complexity. Some workloads may be better served by edge-centric or subgraph-centric execution models.