Graph Algorithms

Chapter 2. Graph Theory and Concepts

In this chapter, we set the framework and cover terminology for graph algorithms. The basics of graph theory are explained, with a focus on the concepts that are most relevant to a practitioner.

We’ll describe how graphs are represented, and then explain the different types of graphs and their attributes. This will be important later, as our graph’s characteristics will inform our algorithm choices and help us interpret results. We’ll finish the chapter with an overview of the types of graph algorithms detailed in this book.

Terminology

The labeled property graph is one of the most popular ways of modeling graph data.

A label marks a node as part of a group. In Figure 2-1, we have two groups of nodes: Person and Car. (Although in classic graph theory a label applies to a single node, it’s now commonly used to mean a node group.) Relationships are classified based on relationship type. Our example includes the relationship types of DRIVES, OWNS, LIVES_WITH, and MARRIED_TO.

Properties are synonymous with attributes and can contain a variety of data types, from numbers and strings to spatial and temporal data. In Figure 2-1 we assigned the properties as name-value pairs, where the name of the property comes first and then its value. For example, the Person node on the left has a property name: "Dan", and the MARRIED_TO relationship has a property of on: Jan 1, 2013.

A subgraph is a graph within a larger graph. Subgraphs are useful as a filters ...