Graph Theory

Now that we have got a taste of linear algebra, calculus, statistics, and optimization, it is time to move on to a very fascinating topic, known as graph theory. This involves, as the name suggests, the study of graphs, which we use to model relationships between objects. We use these graphs to help visualize and analyze problems, which in turn helps us solve them.

Graph theory is a very important field and is used for a variety of problems, including page ranking in search engines, social network analysis, and in a GPS to find the best route home. It is also important for us to further our understanding of deep neural networks since the majority of them are based on a type of graph known as a directed acyclic graph (DAG).

Covering everything in graph theory goes beyond the scope of this chapter (and this book), but we will cover everything that is important for...

Understanding the basic concepts and terminology

Graph theory was first introduced in the 18th century by Leonhard Euler to solve a famous problem known as the Königsberg bridge problem, which asks whether it is possible to walk around the Königsberg bridge while crossing over each of the seven bridges exactly once. The bridge looks as follows:

Before we move on, try it out for yourself by using your finger to trace along the path or draw it and trace it with a pencil. Did you manage to find a solution? It's alright if you didn't!

Let's stop for a moment and ask ourselves what exactly a graph is. A graph (G) is a mathematical structure made up of two sets—vertices (V(G)) and edges (E(G)). Two vertices (v₁ and v₂) are connected if there is an edge (e or (v₁, v₂)) between them. Now that that's settled, there are some rules associated with graphs...

Adjacency matrix

As you can imagine, writing down all the pairs of connected nodes (that is, those that have edges between them) to keep track of the relationships in a graph can get tedious, especially as graphs can get very large. For this reason, we use what is known as the adjacency matrix, which is the fundamental mathematical representation of a graph.

Let's suppose we have a graph with n nodes, each of which has a unique integer label () so that we can refer to it easily and without any ambiguity whatsoever. For the sake of simplicity, in this example, n = 6. Then, this graph's corresponding adjacency matrix is as follows:

Let's take a look at the matrix for a moment and see why it is the way it is. The first thing that immediately pops out is that the matrix has a size of 6 × 6 (or n × n) because size is important to us. Next, we notice that...

Types of graphs

In the previous section, we learned about the basics of graph theory, and as you saw, this is a very powerful mathematical tool that can be used for a plethora of tasks in various fields. However, there is no one-size-fits-all solution and so we need additional tools to help us because each problem is unique. In this section, we will learn about the various types of graphs and their use cases and strengths. This includes weighted graphs, directed graphs, multilayer graphs, dynamic graphs, and tree graphs.

Weighted graphs

So far, we have seen graphs that have a sort of binary representation, where 1 represents the existence of an edge between two nodes and 0 signifies that there is no connection between two...

Graph Laplacian

Earlier in this chapter, in the Adjacency matrix section, we learned about the adjacency matrix and how we can use it to tell what the structure of a graph is. However, there are other ways of representing graphs in matrix form.

Now, let's suppose we have an undirected, unweighted graph. Then, its Laplacian matrix will be a symmetric n × n matrix, L, whose elements are as follows:

Here, . We can also write this as follows:

Here, A_i,j is the adjacency matrix and δ_i,j is the Kronecker delta. We can rewrite this in matrix form, as follows:

Here, we have the following:

Similarly, we can also write the graph Laplacian matrix for a weighted graph by replacing the adjacency matrix here with the one we defined previously for weighted graphs.

Summary

In this chapter, we learned about a very fascinating topic in mathematics that has applications in nearly every field, from social sciences, to social networking, to the World Wide Web, to artificial intelligence—but particularly, in our case of neural networks.

In the next chapter, we will learn about linear neural networks, which are the simplest type of neural networks and are used most frequently in statistical learning.