Tag Archives for graph-theory

The graph Laplacian 2

In the previous blog, we saw the Laplacian defined in the context of solving for current flowing through an electrical circuit. We mentioned that the Laplacian is used in studying diffusion on graphs. Now, how could one possibly see it as a diffusion operator on a structure which does not allow differentiation? We should ask ourselves what the key aspect of diffusion is that is modeled by the heat equation. Sticking to the one-dimensional version for ease (though the intuition applies to more dimensions), we note that the second derivative can be approximated by

\frac{d^2 f}{dx^2} \approx \frac{f(x+h) - 2f(x) + f(x-h)}{h^2} = \frac{(f(x+h) - f(x)) + (f(x-h) - f(x)}{h^2}.

Seen this way, the second derivative can be seen as an average changes of the function values around a reference point. The diffusion equation therefore can be interpreted to mean something like, “The rate of change in time of a quantity (which we take to be concentration) at a point is proportional to the average of the change of concentration values around the point”.

Not very precise, but that’s okay – I’m not going for rigour here. Suppose now we have a discrete set of nodes, what could this mean? First of all, we let a node be at a distance of 1 from any of its neighbours, and allow no closer distances. To each of these nodes we assign a value, representing the concentration of some substance at that node. (Technically, since we’re working in a network now, there are better concepts than concentration, but I want to stick close to the original intuition.) Remembering our definition of the (unweighted) Laplacian as

L=D−AL = D – A

with D the diagonal degree matrix and A the incidence matrix, suppose that we have values \mathbf{x} = (x_1, x_2, \dots ,x_n) assigned to vertices v_1,v_2,\dots ,v_n. Looking at just the first entry of the matrix L\mathbf{x}, we get

\text{deg}(v_1)x_1 - A_{12}x_2 - \cdots - A_{1n}x_n .

Supposing that x_1 is connected to k vertices v_{i_1} ,\dots ,v_{i_k}, this gives us

(x_1 - x_{i_1}) + (x_1 - x_{i_2}) + \dots + (x_1 - x_{i_k}).

This is exactly what we want to describe diffusion-like phenomena, since it encodes the differences between the values at v_1 and all the nodes connected to it. Compared with the earlier approximation of the second derivative however, we notice a sign difference. This is easily fixed by multiplying with a negative, and we get the graph diffusion equation

\frac{dx}{dt} = -Lx.

This is all very nice, but have we not just in effect written a system of differential equations in a neat matrix form? Where does this get us? The point of formulating this system as a Laplacian is that we will be able to say things without solving the system, by only analyzing the algebraic properties of the operator L. These properties will tell us a lot about the topology of the graph itself, which is where we’ll go next.

The graph Laplacian 1

The heat equation is an important thing, as I have hopefully conveyed, even in a small part, by posting on Fourier analysis. Most readers would be fairly familiar with the Laplacian \nabla^2, making its appearance in the heat equation as

\frac{\partial x}{\partial t} = k \nabla^2 x.

Ed Nelson said, “The Laplace operator, or Laplacian, is the most important of all differential operators.” Since I regard Nelson as someone with excellent taste, I think we should pay attention. Indeed, this is such an important concept that it has even made its way into graph theory. When ideas migrate from one field to another; it shows their vitality and depth. Much of the work on the hypergraph Laplacian was in fact inspired by the use of the Laplacian in compact Riemann surfaces, but let’s not get ahead of ourselves… At the same time, concepts should not be migrated to other areas without justification; this might lead to meaninglessly generating results that benefit no one. So we should probably ask ourselves why the Laplacian makes sense in a graph-theoretic context. Fortunately, this turns out to be an easy one. The graph Laplacian has quite an esteemed pedigree, being invented (discovered?) by Gustav Kirchoff (whom we shall soon meet again in another post) in 1847 whilst formulating his circuit laws, which led to an examination of spanning trees. Since then, applications have burgeoned, especially in the modern age where analysis of networks has become vitally important.

Before going on to the links with diffusion, I am going to approach this in the spirit of Kirchoff. He was not interested in spanning trees, as such. Rather, he was trying to simplify computation of current at different points in electric circuits. (A mathematical breakthrough so often comes about in an attempt to make calculation easier.) Whilst I’m not going to retrace his steps exactly, I thought it would be worthwhile to look at the Laplacian in this context.

Kirchoff’s current law states simply that:

The total current flowing into a node equals the total current flowing out of a node.

Let us now take a very simple circuit, consisting of three resistors.

In the above, we imagine that the nodes each have a resistor between them, and we want to determine the current flowing through each node. For now, let’s ignore the power source and assume there is an electrical potential at each of the nodes A, B and C, which we denote v_1, v_2 and v_3 (we will be working with the potential differences only, so we don’t need to establish a reference for the potential). We assume the resistors between the nodes have resistances r_{12}, r_{23} and r_{31}, respectively. The (multiplicative) inverse of resistance is conductance, denoted by g_{ij} = g_{ji}. Applying Ohm’s law I = V/R = GV, we have the system of equations

I_{12} = g_{12}(v_1 - v2)

I_{23} = g_{23}(v_2 - v_3)

I_{31} = g_{13}(v_3 - v_1)

Applying Kirchoff’s circuit law, we have the following expressions for the current through each node:

I_1 = g_{13}(v_1 - v_3) + g_{12}(v_1 - v2)

I_2 = g_{23}(v_2 - v_3) + g_{12}(v_2 - v1)

I_3 = g_{23}(v_3 - v_2) + g_{13}(v_3 - v_1).

(Convince yourself that this makes sense.) We can write this as

\begin{bmatrix} I_1 \\ I_2 \\ I_3 \end{bmatrix} = \begin{bmatrix} g_{12}+g_{13} & -g_{12} & -g_{13}\\ -g_{12} & g_{12}+g_{23}&-g_{23}\\ -g_{13}&-g_{23}& g_{13}+g_{23} \end{bmatrix} \begin{bmatrix}v_1 \\ v_2 \\v_3 \end{bmatrix} = L\mathbf{v}

Looking at this system, we can start to make a few guesses about what the Laplacian is good for. Obviously, we have ended up with a simple system of linear equations. The first thing to notice is that our matrix has determinant 0. A 3 \times 3 matrix with determinant 0 signifies three vectors in ℝ3\mathbb{R}^3 that form a parallelepiped with 0 volume, meaning we have actually have a two- or one-dimensional figure. In other words, these linear equations are not independent. Indeed, it is easily seen that row 1 + row 2 = – row 3. What this means for the graph is that forming the system out of a loop introduces redundancy. We could have constructed our system by only using a spanning tree, saving us some computational time.

The matrix/operator L is what we would call a weighted Laplacian. To get the normal graph-theoretic Laplacian, we take all the resistances above to be equal to 1. It is then evident that we can write the Laplacian as

L = D - A,

with D the diagonal matrix with the degree of vertex i at D_{ii} and A is the incidence matrix, with A_{ij} = 1 if vertices i and j are connected (i \neq j) and 0 otherwise. Setting all edge weights to be 1 in the above graph, compute the determinant of each matrix obtained by removing the kth column and row, for k = 1,2,3. How does this correspond to the number of spanning trees? What can we say about the number of independent loops in the graph, remembering that adding any edge to a spanning tree creates a loop? Try this with a graph on 4 vertices, and formulate some conjectures. Compute the eigenvalues of L. Now do the same thing for a graph with two components, and see if you can come up with more conjectures. If you are very adventurous, try to prove them…

Relevant reading:

Kirby, E.C., Mallion, R.B., Pollak, P. and Skrzyński, P.J., 2016. What Kirchhoff actually did concerning spanning trees in electrical networks and its relationship to modern graph-theoretical work. Croatica Chemica Acta, 89(4), pp.403-417.