Graphs and Linear Algebra
In this article I discuss matrices associated to graphs. As we will see, a graph can be represented as a matrix without any information loss. Hence, the properties of these matrices describe properties of the underlying graph.
Matrices associated to graphs
A graph
I will show examples on the following graph, named
---
config:
layout: elk
look: handDrawn
---
graph LR
vertex_1((1))
vertex_2((2))
vertex_3((3))
vertex_4((4))
vertex_1 === vertex_2
vertex_1 === vertex_3
vertex_1 === vertex_4
vertex_2 === vertex_3
Degree matrix
Vertex degree is ised to define the degree matrix
Incidence matrix
Incidence is used to define the incidence matrix
- If
is directed: if vertex and edge are not incident if edge originates at vertex if edge terminates at vertex
- If
is undirected:- If
is unoriented: if vertex and edge are not incident otherwise
- If
is oriented: we pick an orientation of the graph, and use the incidence matrix of the resulting directed graph.
- If
Adjacency matrix
Adjacency is used to define the adjacency matrix
if vertices and are not adjacent (note that in simple graphs vertices are not self-adjacent) otherwise
For
The adjacency matrix relates to the concept of paths in an unweighted graph:
Laplacian matrix
The Laplacian matrix
- For
: if vertices and are not adjacent otherwise
- For
, the degree of .
More concisely,
For
The Laplacian relates to the connectedness of a graph, giving rise to spectral graph theory. It also is connected to flows. The diagonal entries represent the total outflow capacity from a vertex, while off-diagonal entries encode pairwise connection strengths.
Normalized Laplacian matrices
The presence of hubs results in large diagonal entries in the Laplacian. There are normalized versions of the Laplacian that downweigh such vertices by dividing the entries by the vertex degree.
The symmetrically normalized Laplacian
The random walk normalized Laplacian
Spectral graph theory
Spectral graph theory studies how the eigenvalues and eigenvectors of a graph’s associated matrices relate to its properties. Looking more closely at two of the matrices described above, we can see they have interesting properties:
- If
is undirected, is both real and symmetric. Hence, it is diagonalizable and has only real values. - Since for an undirected graph both
and are symmetric, is also real and symmetric. In fact, is positive semi-definite. This implies that ’s eigenvalues are not only real, but also non-negative.
Spectral graph theory often focuses on studying the eigenvalues of the Laplacian.
Connectivity of the graph
The eigenvectors of
A simple, but ultimately insightful property of
More generally, less smooth eigenvectors (i.e., those in which consecutive elements change sharply) indicate a less connected. Equivalently, smaller eigenvalues correspond to smoother eigenvectors, and hence to better connected graphs.
Spectral clustering
The goal of spectral clustering is finding a partition of the graph into
Note: spectral clustering is often applied as a clustering technique on datasets. The aim is to divide the observation into
groups based on their pairwise similarities. In that case, the first step consists on obtaining the graph. It will be a complete weighted graph in which the vertices are the different observations and the edges are weighted according to the similarity between each pair of vertices, as measured by an arbitrary function.