Databases Reference
In-Depth Information
CHAPTER 7
Predictive Analysis with Graph Theory
In this chapter we're going consider analytical techniques and algorithms for processing
graph data. Both graph theory and graph algorithms are mature and well-understood
fields of computing science and we'll demonstrate how both can can be used to mine
sophisticated information from graph databases. Although the reader with a back‐
ground in computing science will no doubt recognize these algorithms and techniques,
the discussion in this chapter is handled without recourse to mathematics, to encourage
the curious reader to dive in.
Depth- and Breadth-First Search
Before we look at higher-order analytical techniques we need to reacquaint ourselves
with the fundamental
breadth-first search
algorithm, which is the basis for iterating over
an entire graph. Most of the queries we've seen throughout this topic have been
depth-
first
rather than
breadth-first
in nature. That is, they traverse outward from a starting
node to some end node before repeating a similar search down a different path from
the same start node. Depth-first is a good strategy when we're trying to follow a path to
discover discrete pieces of information.
Informed Depth-First Search
The classic depth-first algorithm search is
uninformed
in that it simply searches a path
until it finds the end of the graph. Once at the end, it backtracks to the start node and
tries a different path. Because graph databases are semantically rich, however, we can
terminate a search along a particular branch early (for example, once we've found a node
with no compatible outgoing relationships, or have traversed “far enough”). Such
in‐
formed
searches can result in lower execution times. These are exactly the kinds of
searches performed by our Cypher matches and traversals in previous chapters.
