What do you get with Print?

Instant access to your digital eBook copy whilst your Print order is Shipped

Paperback book shipped to your preferred address

Download this book in EPUB and PDF formats

Access this title in our online reader with advanced features

DRM FREE - Read whenever, wherever and however you want

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.

Description

Neo4j is the world's leading graph database and offers users a radical new way of dealing with connected data. This book has been created to help you get to grips with it, providing you with an accessible route through a tool built to contend with the complexity of modern data. Learn the fundamental concepts behind Neo4j, and put them into practice by following the featured examples and use cases that demonstrate how to apply your knowledge to real problems. Starting with a brief introduction to graph theory, this book will show you the advantages of using graph databases. Following on from that, you will be introduced to Neo4j and you will be shown how to install it on various operating systems. You will then be shown how you can model and import your data into Neo4j. This book has two use case examples that will show you how to model and implement a graph in Neo4j by analyzing a user case, and analyze the impact a change has on a process or a system. You will also gain an insight into graph visualization options and discover external sources where you can learn more about this exciting and popular graph database.

What you will learn

Background and specifications of graph databases

Install Neo4j on a variety of different platforms, locally and in the cloud

Model data for a graph database such as Neo4j

Import data into Neo4j

Learn about sample use cases for Neo4j

Discover the advantages of graph databases versus other database models

Find out where you can find additional information on Neo4j

What do you get with Print?

Instant access to your digital eBook copy whilst your Print order is Shipped

Paperback book shipped to your preferred address

Download this book in EPUB and PDF formats

Access this title in our online reader with advanced features

DRM FREE - Read whenever, wherever and however you want

Frequently bought together

$29.99

$54.99

$48.99

Total $ 133.97

Filter reviews by

All

Amazon verified reviews

Ken R. Adcock, Jr. Mar 31, 2015

If one follows software development, it's almost impossible to miss the buzz about NoSQL databases. Graph databases get mentioned along with the more familiar document and column-family NoSQL solutions. However, they seem to be frequently relegated to the periphery of the discussion given they are thought to address very specific problem domains - namely recommendation engines and social network analysis. More people, myself included, are now realizing that many real-world entities can be modeled as networks of data and that valuable insights can be realized if they could be understood better. Historically, modeling such networks via traditional relational databases has always been difficult. With all that said, graph databases are now being given more attention.I think few would disagree that whenever graph databases are mentioned, Neo4j gets mentioned first as an actual example. Therefore, I read Learning Neo4j, by Rik Van Bruggen and published by Packt Publishing, with great interest. I can say this is the first complete book I have read about Neo4j so I have not been influenced by any prior resources.The About the Author section states that Rik Van Bruggen is a Regional Territory Manager for Neo Technology - the company behind Neo4j. I expected a fair amount of product-specific evangelism when I first started to read the book. I was pleased to see that Rik kept that to a minimum and did so in a very professional manner. The focus stays on conveying the basic concepts and I never felt feel like I was reading a sales pitch from a vendor whitepaper.Rather than just provide a very high-level review, interested readers may find the following chapter-level detail to be more informative.Chapter 1 - (Graphs and Graph Theory - An Introduction) - The author sets the foundation by explaining graph theory in an understandable way. I really don't see how this could have been done better. Also included was some history going back to the famous mathematician Euhler who is considered by most to be the father of graph theory. By graphs, we mean nodes and edges- not graphics. I thought the illustration from Euhler's original 1736 paper was a nice touch. The author goes on to discuss the basic definitions of graphs and how they apply to real-world problems. The final message of this chapter: "Graphs Are Everywhere."Chapter 2 (Graph Databases - Overview) - This chapter discussed how the traditional relational database systems suffer when attempting to model data organized as networks. The author discusses the family of NoSQL databases and how they work such as key-value, column-family, and document stores along with graph-oriented databases. The author goes on to describe a key concept called the Property Graph model along with a description of what graph databases are good at and not so good at. The amount of territory covered in this chapter and the way it was written was nicely done.Chapter 3 (Getting Started with Neo4j) - In this chapter, one gets into Neo4j. Probably the biggest surprise for me was reading that Neo4j is an ACID-compliant database. The author spends some time discussing the differences between OLTP and OLAP databases along with the declaration that Neo4j falls into the OLTP category. Also, the reader gets their first introduction to Cypher - the query language for performing DDL and DML operations on Neo4j databases. Finally, the author provides installation steps for Windows, Mac, and Linux operating systems. The author also makes a brief mention of Neo4j in a cloud environment. I was very happy to read about a cloud-based "graph as a service" solution called GrapheneDB. I plan on checking into that further.Chapter 4 (Modeling Data for Neo4j) - I regard this chapter as a core part of this book and also the most difficult to internalize. In this chapter, the author goes into detail on how to model real world entities into the graph database structure. I feel the author makes a good case explaining the limitations and complexities associated with modeling the real-world through the use of entity-relationship (ER) diagrams used for relational database design. This is contrasted against the flexibility of a graph database. Hence, the title of one section: "A graph model - a simple, high-fidelity model of reality". I would say the critical point made in this chapter is the questions you are trying to answer drive the design of the data model. In other words, the queries drive the design. This is a complex chapter with difficult to teach subject matter. You could write an entire book on this one chapter. I do feel the author made a good effort here.Chapter 5 (Importing Data into Neo4j) - Put simply, this chapter describes multiple approaches on how to get data into a Neo4j database. Several tools are illustrated along with some pros and cons. This chapter focuses on tools and techniques and the author mentions the contents of this chapter are not an exhaustive list. However, there is plenty here to get you started.Chapter 6 (Use Case Example - Recommendations) - If you have read this far, you will find the author has done an excellent job making you very eager to read this chapter and the one to follow. In this chapter, you dive into the most familiar use case when the subject of graph databases comes up - recommender systems. The author sets the stage with a simple data model and demonstrates how Neo4j can issue queries against this data model to address recommendations regarding product purchases, brand loyalty, and social ties. The author provides informative Cypher queries along the way. Also included is what I regard as nice bonus material involving the same principles behind recommender systems - use case descriptions involving fraud detection, access control, and social networks. The author doesn't go into a lot of detail with these three use cases, but it was interesting to read about them.Chapter 7 (Use Case Example - Impact Analysis and Simulation) - I believe the goal of the author when writing this chapter was to expand the reader's horizons beyond the much more obvious and more commonly discussed use cases described in the prior chapter. In this chapter, the author begins by describing how Neo4j can help with business process management. In other words, we can model business processes as an interconnected system of workflows, software applications, departments, and physical assets such as buildings. Continuing along the same theme, the author demonstrates the usefulness of Neo4j as an impact simulation tool. One can better understand how an exogenous shock such as a price increase of a component can ripple through a complex product hierarchy and the associated product cost structure. Perhaps due to my own ignorance, I found this chapter to be the most esoteric part of the book, but I still found a lot of value from it. The moral of this story is that if a system can be mapped into a graph data structure, then Neo4j may be able to help.Chapter 8 (Visualizations for Neo4j) -From this point forward, the tempo of the book slows down. That's ok. For me, the intensity of the information from the prior chapters left me pretty full. In this chapter, the author goes through several tools, which includes JavaScript visualization libraries such as D3.js where you have to write code to solutions that have a graphical user interface. Even prior to reading this, I found that although graphical displays of large dense networks were cool to look at, it was really difficult to derive anything particularly actionable or insightful. The author even makes mention of that. This chapter provided me with some good information on visualization tools, but I still don't have a good understanding about how to use visualizations as a way to derive insights from complex networks. However, I don't hold that against the author.Chapter 9 (Other Tools Related to Neo4j) - In this chapter, the author surveys some data integration and business intelligence tools that can work with Neo4j databases. Of particular interest to me was learning about the existence of a JDBC driver for Neo4j. Finally, the chapter concludes with a brief discussion of graph modeling tools.Appendix A and Appendix B - The author provides some brief information on Neo4j community resources. What got my attention was the mention of the GraphGists website where people can post their own models and use cases. I plan on spending some time on that site. Also included is a helpful mention of a Cypher reference card along with a more detailed treatment of the Cypher key words. There isn't enough there to be a comprehensive explanation of Cypher, but there is enough to prepare you for a deeper dive.The author writes in a very clear style that is easy to read and follow. In fact, it was a pleasure to read. To be clear, this is an introductory book. You will come away with a firm foundation on graph databases and Neo4j as an implementation. I can say I would very much appreciate an advanced-level Neo4j book from the same author. If he decides to write such a book, I will certainly buy it.Finally, if the author's goal was to teach the basic concepts about graph databases via Neo4j in manner that peaks the reader's curiosity to learn more, then he was successful. If you already have some expertise with Neo4j, then this book may be much less of a benefit to you than it was for me. I maintain you should probably still check it out. I bet you will still learn some neat things you didn't know. This was a very well written book. I really enjoyed it and I recommend it. This book earns 5 stars from me.

Amazon Verified review

A. Zubarev Feb 09, 2015

One of the fascinated technical books I have ever read, while not difficult to understand (hint: Neo4J is well put together), it is very informative, yet elegantly written that to an able to learn on its own reader can open a whole slew of possibilities and opportunities.I need to step back and tell that I approached this book initially with some scepticism, and while I was on the very first pages of it one of my co-workers pryingly glanced over my shoulder and asked, what are you reading? I replied: “it is a book on a Graph database called Neo4J”. His reaction was, “I did not even know there are such a database type!”. As a database professional though I felt obliged to make myself aware and somewhat educated on alternative or niche databases, this is what I thought then, but now… read on.Ric Van Bruggen is definitely in love with Neo4J, but he is also a talented teacher, this book could much less of a technical reference than it is without him. Ric tastefully expands from the history and basics of Graph databases up to very practical, yet advance usages and ends the book with the tools ecosystem and even a neat Cypher ref-card. Besides, I think Cypher is the cornerstone to the successful operation of Neo4J. For the impatient reader, Cypher to Neo4J is as SQL to RDBMS’.The book reads like a story, it gradually builds your level of knowledge and at the same time makes you “feel at home” with Neo4J, it is a very welcoming database.My interest grew with every page I flipped.The database gets easily installed on any platform, and for the record, its graphing (visual) abilities are stunning! It can also output data in the tabular form. Yet, based on what Ric stated it is VERY fast – he processed 2.1 mil nodes in under 50 sec on a laptop (disclaimer: I did not run any Cypher code, but I am planning to).This book, especially its chapters 6 and 7 (use case examples), were of immense interest to me, the Recommendation Engine, Impact Analysis I loved both a lot. I think my case using Neo4J will be on finding the best driving path (based on more than 2 factors) that I want to experiment with.I figured, Neo4J is supported by a vast number of enterprise grade tools comprising a serious ecosystem in which Neo4J strives to take on new heights.After reading this book I must say the Graph Databases are seriously overlooked.Well done, Ric, Packt and etc. A 5 out of 5 from me!Take Neo4J for spin!

HockeyCanMan Jan 02, 2015

This book is a very good addition to the growing base of Neo4j documentation. Data import and use case examples are well written. Recommended.

Biju Mathews May 15, 2015

Good book

Arda Mar 31, 2015

This is a good introductory book for Neo4j for anyone considering a switch from RDBMS's. It gives a brief but very interesting history of Graph Theory and Databases, and how Graph Theory can solve some short comings of RDBMS's. The author presents solid use cases where a Graph Database could be preferred instead of a RDBMS, and vice versa. There is also some basic information about installation and setting up your environment, and basic Cypher usage. For advanced Cypher usage, you may want to look somewhere else.One of the short comings of the book is that there is no word about Operational perspective of Neo4j, scaling and maintenance, etc. Which are pretty important concerns when switching from an RDBMS. While I can understand that this is probably out of the scope of this introductory book, I would still expect at least some insight about scaling.Buy this book if you want to learn if a Graph Database is good for you or not, or if you need some help ideas about basic usage.

Learning Neo4j: Run blazingly fast queries on complex graph datasets with the power of the Neo4j graph database

What do you get with Print?

Learning Neo4j

Chapter 1. Graphs and Graph Theory – an Introduction

Introduction to and history of graphs

Definition and usage of graph theory

Social studies

Biological studies

Computer science

Flow problems

Route problems

Web search

Test questions

Summary

Page 1 of 5

Description

What you will learn

Product Details

What do you get with Print?

Product Details

Frequently bought together

Table of Contents

Recommendations for you

Customer reviews

Filter reviews by

People who bought this also bought

About the author

FAQs

Learning Neo4j: Run blazingly fast queries on complex graph datasets with the power of the Neo4j graph database

What do you get with Print?

Description

What you will learn

Product Details

What do you get with Print?

Product Details

Packt Subscriptions

Frequently bought together

Table of Contents

Recommendations for you

Customer reviews

Filter reviews by

People who bought this also bought

About the author

FAQs