A graph is a collection of vertices connected to each other using edges as shown in the following Figure 9.1. Vertex is a synonym for node, which can be a place or person with associated relationships expressed using edges. Jacob, Jessica, and Emily in the figure are vertices and their relationships are edges. This is a simple example of a social graph. Just imagine expressing the whole of Facebook as a social graph. Finding relationships between them can be a very complex task. In Chapter 3, Deep Dive into Apache Spark, we learned about creating the Directed Acyclic Graph (DAG) for Spark jobs that consist of Resilient Distributed Datasets (RDD) which are nothing but vertices, and transformations, which are nothing but edges. There are multiple ways to go from one place to another place. If we create places as vertices and roads as edges, graph processing can provide an optimized shortest path between these two places:

Figure 9.1: Representation of a family relationship graph

Weights in a graph provide strength to an edge, for example the distance between two cities can be closer or more distant. Graphs can be directed or undirected. RDD's DAG is directed because it goes only in one direction. Graphs can be cyclic or acyclic. For example, in a social network, you can start with one friendship and circle between different friends to get back to the original person.

Graphs are everywhere and almost everything can be represented as graphs. Graph processing can be implemented in telecoms, aviation, bio informatics, social networks, and many more fields.

There are two types of technologies in graph processing; graph databases and graph processing systems. Graph databases can be seen as OLTP databases that provide transactions, updates, deletes, and query language. Graph processing systems can be seen as OLAP systems that provide offline analytic capabilities. The following table shows the important graph databases and graph processing systems:

The GraphLab framework implements the Message Passing Interface (MPI) model to run complex graph algorithms using data in HDFS. Apache Giraph and Apache Hama are based on the Bulk Synchronous Parallel (BSP) model inspired by Google's Pregel project. GraphX is built on top of Spark and supports a variant of the Pregel API as well. This chapter focuses on graph processing systems and especially GraphX.

Apache Giraph, born at LinkedIn, is a stable system that can process a trillion edges on top of Hadoop, but Apache Giraph is not supported by all major Hadoop vendors. If your use case is a pure graph-related problem, you can use Apache Giraph as a robust and stable solution, but if graph processing is just a part of the solution, GraphX on top of Spark provides a great unified solution with the power of Spark core capabilities.

GraphX is a graph processing system built on top of Apache Spark, which can be easily integrated with other Spark modules to unify ETL, exploratory analytics, and graph analytics. GraphX creates graphs as another type of RDD such as VertexRDD and EdgeRDD. Spark's GraphX features such as speed of iterative processing and in-memory capabilities removed the issues of MapReduce that Apache Giraph and Pregel were designed to address. GraphX stores a graph's edges in one file and vertices in another file. This allows graph algorithms implemented in GraphX to view graphs either as graphs or as collections of edges or vertices to efficiently combine multiple processing types within the same program.

Typically, graphs would be too large to fit on a single machine and must use distributed systems such as HDFS and S3.

GraphX provides the following algorithms out-of-the-box in version 2.0. Some of these algorithms are practically implemented in the next section of this chapter: