Learning Neo4j

Chapter 1. Graphs and Graph Theory – an Introduction

People have different ways of learning new topics. We know that background information can contribute greatly to a better understanding of new topics. That is why, in this chapter of our Learning Neo4j book, we will start with quite a bit of background information, not to recount the tales of history, but to give you the necessary context that can lead to a better understanding of topics.

In order to do so, we will address the following topics:

Graphs: What they are and where they came from. This section will aim to set the record straight on what exactly our subject will contain and what it won't.
Graph theory: What it is and what it is used for. This section will give you quite a few examples of graph theory applications, and it will also start hinting at applications for graph databases such as Neo4j later on.

So, let's dig right in.

Introduction to and history of graphs

Many people might have used the word graph at some point in their professional or personal lives. However, chances are that they did not use it in the way that we will be using it in this book. Most people—obviously not you, my dear reader, otherwise you probably would not have picked up this book—actually think about something very different when talking about a graph. They think about pie charts and bar charts. They think about graphics, not graphs.

In this book, we will be working with a completely different type of subject—the graphs that you might know from your math classes. I, for once, distinctly remember being taught the basics of discrete Mathematics in one of my university classes, and I also remember finding it terribly complex and difficult to work with. Little did I know that my later professional career will use these techniques in a software context, let alone that I would be writing a book on this topic.

So, what are graphs? To explain this, I think it is useful to put a little historic context around the concept. Graphs are actually quite old as a concept. They were invented, or at least first described, in an academic paper by the well-known Swiss mathematician Leonhard Euler. He was trying to solve an age-old problem that we now know as the 7 bridges of Königsberg. The problem at hand was pretty simple to understand.

Königsberg has a beautiful medieval city in the Prussian empire, situated on the river Pregel. It is located between Poland and Lithuania in today's Russia. If you try to look it up on any modern-day map, you will most likely not find it as it is currently known as Kaliningrad. The Pregel not only cut Königsberg into a left- and right-bank side of the city, but it also created an island in the middle of the river, which was known as the Kneiphof. The result of this peculiar situation was a city that was cut into four parts. We will refer to them as A, B, C and D, which were connected by seven bridges (labeled a, b, c, d, e, f, and g in the following diagram).This gives us the following situation:

The seven bridges are connected to the four different parts of the city
The essence of the problem that people were trying to solve was to take a tour of the city, visiting every one of its parts and crossing every single one of its bridges, without having to walk a single bridge or street twice

In the following diagram, you can see how Euler illustrated this problem in his original 1736 paper:

Illustration of the mentioned problem as mentioned by Euler in his paper in 1736

Essentially, it was a pathfinding problem, like there are many others (for example, the knight's ride problem or the travelling salesman problem). It does not seem like a very difficult assignment at all now does it? However, at the time, people really struggled with it and were trying to figure it out for the longest time. It was not until Euler got involved and took a very different, mathematical approach to the problem that it got solved once and for all.

Euler did the following two things that I find really interesting:

First and foremost, he decided not to take the traditional brute force method to solve the problem (that is, in this case, drawing a number of different route options on the map and trying to figure out—essentially by trial and error—if there was such a route through the city), but decided to do something different. He took a step back and took a different look at the problem by creating what I call an abstract version of the problem at hand, which is essentially a model of the problem domain that he was trying to work with. In his mind at least, Euler must have realized that the citizens of Königsberg were focusing their attention on the wrong part of the problem—the streets. Euler quickly came to the conclusion that the streets of Königsberg really did not matter to find a solution to the problem. The only things that mattered for his pathfinding operation were the following:
- The parts of the city
- The bridges connecting the parts of the city
Now, all of a sudden, we seem to have a very different problem at hand, which can be accurately represented in what is often regarded as "the world's first graph":
Secondly, Euler solved the puzzle at hand by applying a mathematical algorithm on the model that he created. Euler's logic was simple: if I want to take a walk in the town of Königsberg, then:
- I will have to start somewhere in any one of the four parts of the city
- I will have to leave that part of the city; in other words, cross one of the bridges to go to another part of the city
- I will then have to cross another five bridges, leaving and entering different parts of the city
- Finally, I will end the walk through Königsberg in another part of the city

Therefore, Euler argues, the case must be that the first and last parts of the city have an odd number of bridges that connect them to other parts of the city (because you leave from the first part and you arrive at the last part of the city), but the other two parts of the city must have an even number of bridges connecting them to the first and last parts of the city because you will arrive and leave from these parts of the city.

This "number of bridges connecting the parts of the city" has a very special meaning in the model that Euler created, the graph representation of the model. We call this the degree of the nodes in the graph. In order for there to be a path through Königsberg that only crossed every bridge once, Euler proved that all he had to do was to apply a very simple algorithm that will establish the degree (in other words, count the number of bridges) of every part of the city. This is shown in the following diagram:

This is how Euler solved the famous "Seven bridges of Königsberg" problem. By proving that there was no part of the city that had an even number of bridges, he also proved that the required walk in the city cannot be done. Adding one more bridge would immediately make it possible, but with the current state of the city, and its bridges at the time, there was no way one could take such an Eulerian Walk of the city. By doing so, Euler created the world's first graph. The concepts and techniques of his research, however, are universally applicable; in order to do such a walk on any graph, the graph must have zero or two vertices with an odd degree, and all intermediate vertices must have an even degree.

To summarize, a graph is nothing more than an abstract, mathematical representation of two or more entities, which are somehow connected or related to each other. Graphs model pairwise relations between objects. They are, therefore, always made up of the following components:

The nodes of the graph, usually representing the objects mentioned previously: In math, we usually refer to these structures as vertices; but for this book, and in the context of graph databases such as Neo4j, we will always refer to vertices as nodes.
The links between the nodes of the graph: In math, we refer to these structures as edges, but again, for the purpose of this book, we will refer to these links as relationships.
The structure of how nodes and relationships are connected to each other makes a graph: Many important qualities, such as the number of edges connected to a node, what we referred to as degree, can be assessed. Many other such indicators also exist.

Now that we have graphs and understand a bit more about their nature and history, it's time to look at the discipline that was created on top of these concepts, often referred to as the graph theory.

Definition and usage of graph theory

When Euler invented the first graph, he was trying to solve a very specific problem of the citizens of Königsberg, with a very specific representation/model and a very specific algorithm. It turns out that there are quite a few problems that can be:

Described using the graph metaphor of objects and pairwise relations between these objects
Solved by applying a mathematical algorithm to this structure

The mechanism is the same, and the scientific discipline that studies these modeling and solution patterns, using graphs, is often referred to as the graph theory, and it is considered to be a part of discrete Mathematics.

There are lots of different types of graphs that have been analyzed in this discipline, as you can see from the following diagram.

Graph theory, the study of graph models and algorithms, has turned out to be a fascinating field of study, which has been used in many different disciplines to solve some of the most interesting questions facing mankind. Interestingly enough, it has seldom really been applied with rigor in the different fields of science that can benefit from it; maybe scientists today don't have the multidisciplinary approach required (providing expertise from graph theory and their specific field of study) to do so.

So, let's talk about some of these fields of study a bit, without wanting to give you an exhaustive list of all applicable fields. Still, I do believe that some of these examples will be of interest for our future discussions in this book and work up an appetite for what types of applications we will use a graph-based database such as Neo4j for.

Social studies

For the longest time, people have understood that the way humans interact with one another is actually very easy to describe in a network. People interact with people every day. People influence one another every day. People exchange ideas every day. As they do, these interactions cause ripple effects through the social environment that they inhabit. Modeling these interactions as a graph has been of primary importance to better understand global demographics, political movements, and—last but not least—commercial adoption of certain products by certain groups. With the advent of online social networks, this graph-based approach to social understanding has taken a whole new direction. Companies such as Google, Facebook, Twitter, LinkedIn (see the following diagram featuring a visualization of my LinkedIn network), and many others have undertaken very specific efforts to include graph-based systems in the way they target their customers and users, and in doing so, they have changed many of our daily lives quite fundamentally.

Biological studies

We sometimes say it in marketing taglines: "Graphs Are Everywhere". When we do so, we are actually describing reality in a very real and fascinating way. Also, in this field, researchers have known for quite some time that biological components (proteins, molecules, genes, and so on) and their interactions can accurately be modeled and described by means of a graph structure, and doing so yields many practical advantages. In metabolic pathways (see the following diagram for the human metabolic system), for example, graphs can help us to understand how the different parts of the human body interact with each other. In metaproteomics, researchers analyze how different kinds of proteins interact with one another and are used in order to better steer chemical and biological production processes.

A diagram representing the human metabolic system

Computer science

Some of the earliest computers were built with graphs in mind. Graph Compute Engines solved scheduling problems for railroads as early as the late 19th century, and the usage of graphs in computer science has only accelerated since then. In today's applications, the use cases vary from chip design, network management, recommendation systems, and UML modeling to algorithm generation and dependency analysis. The following is an example of such a UML diagram:

An example of a UML diagram

The latter is probably one of the more interesting use cases. Using pathfinding algorithms, software and hardware engineers have been analyzing the effects of changes in the design of their artifacts on the rest of the system. If a change is made to one part of the code, for example, a particular object is renamed; the dependency analysis algorithms can easily walk the graph of the system to find out what other classes will be affected by the former change.

Flow problems

Another really interesting field of graph theory applications is flow problems, also known as maximum flow problems. In essence, this field is part of a larger field of optimization problems, which is trying to establish the best possible path across a flow network. Flow networks are a type of graph in which the nodes/vertices of the graph are connected by relationships/edges that specify the capacity of that particular relationship. Examples can be found in fields such as telecom networks, gas networks, airline networks, package delivery networks, and many others, where graph-based models are then used in combination with complex algorithms. The following diagram is an example of such a network, as you can find it on http://enipedia.tudelft.nl/.

An example of a flow network

These algorithms are then used to identify the calculated optimal path, find bottlenecks, plan maintenance activities, conduct long-term capacity planning, and many other operations.

Route problems

The original problem that Euler set out to solve in 18th century Königsberg was in fact a route planning / pathfinding problem. Today, many graph applications leverage the extraordinary capability of graphs and graph algorithms to calculate—as opposed to finding with trial and error—the optimal route between two nodes on a network. In the following diagram, you will find a simple route planning example as a graph:

A simple route planning example between cities to choose roads versus highways

A very simple example will be from the domain of logistics. When trying to plan for the best way to get a package from one city to another, one will need the following:

A list of all routes available between the cities
The most optimal of the available routes, which depends on various parameters in the network, such as capacity, distance, cost, CO2 exhaust, speed, and so on

This type of operation is a very nice use case for graph algorithms. There are a couple of very well-known algorithms that we can briefly highlight:

The Dijkstra algorithm: This is one of the best-known algorithms to calculate the shortest weighted path between two points in a graph, using the properties of the edges as weights or costs of that link.
The A* (A-star) algorithm: This is a variation of Dijkstra's original ideas, but it uses heuristics to predict more efficiently the shortest path explorations. As A* explores potential graph paths, it holds a sorted priority queue of alternate path segments along the way, since it calculates the "past path" cost and the "future path" cost of the different options that are possible during the route exploration.

Depending on the required result, the specific dataset, and the speed requirements, different algorithms will yield different returns.

Web search

No book chapter treating graphs and graph theory—even at the highest level—will be complete without mentioning one of the most powerful and widely-used graph algorithms on the planet, PageRank. PageRank is the original graph algorithm, invented by Google founder Larry Page in 1996 at Stanford University, to provide better web search results. For those of us old enough to remember the early days of web searching (using tools such as Lycos, AltaVista, and so on), it provided a true revolution in the way the Web was made accessible to end users. The following diagram represents the PageRank graph:

The older tools did keyword matching on web pages, but Google revolutionized this by no longer focusing on keywords alone, but by doing link analysis on the hyperlinks between different web pages. PageRank, and many of the other algorithms that Google uses today, assumes that more important web pages, which should appear higher in your search results, will have more incoming links from other pages, and therefore, it is able to score these pages by analyzing the graph of links to the web page. History has shown us the importance of PageRank. Not only has Google, Inc. built quite an empire on top of this graph algorithm, but its principles have also been applied to other fields such as cancer research and chemical reactions.