Graph Laplacian and other matrices associated with a graph

Posted on by John

There are several ways to associate a matrix with a graph. The properties of these matrices, especially spectral properties (eigenvalues and eigenvectors) tell us things about the structure of the corresponding graph. This post is a brief reference for keeping these various matrices straight.

The most basic matrix associated with a graph is its adjacency matrix, denoted A. For a graph with n nodes, create an n×n matrix filled with zeros, then fill in a 1 in the ith row and jth column if there is an edge between the ith and jth node.

Next let D be the diagonal matrix whose ith element is the degree of the ith node, i.e. the number of edges attached to the ith node. The Laplacian matrix of the graph is

L = A − D.

The Laplacian matrix of a graph is analogous to the Laplacian operator in partial differential equations. It is sometimes called the Kirchhoff matrix or the admittance matrix.

The signless Lapacian matrix is

Q = A + D.

There are connections between the signless Laplacian and bipartite components. For example, the multiplicity of 0 as an eigenvalue of Q equals the number of bipartite components in the graph.

There are other variations of the Laplacian matrix. The normalized Laplacian matrix has 1’s down the diagonal. If there is an edge between the ith and jth nodes, the ij entry is

−1/√didj

where di and dj are the degrees of the ith and jth nodes. If there is no edge between the ith and jth nodes, the ij entry is 0.

The distance matrix of a graph is the matrix D whose ijth entry is the distance from the ith node to the jth node. (Sorry, this D is different than the one above. Books often write this as a script D, something I can’t do in plain HTML.) The transmission of a node v, Tr(v), is the sum of the distances from v to every element connected to v. The distance Laplacian of a graph is Diag(Tr) − D where Diag(Tr) is the diagonal matrix whose ith entry is the transmission of the ith node and D here is the distance matrix. The signless distance Laplacian of a graph is Diag(Tr) + D.

Reference: Inequalities for Graph Eigenvalues

More spectral graph theory

13 thoughts on “Graph Laplacian and other matrices associated with a graph”

  5. GlennF

    “the multiplicity of 0 as an eigenvalue of Q equals the number of bipartite components in the graph”
    Does this just mean the nullity of Q is equal to the number of bipartite components of the graph, or an I misreading this?

  7. John

    Yes and no. MathJax will automate creating an image file from LaTeX and inserting it into your HTML, but it looks like a foreign symbol pasted into the text. That’s OK, and maybe that would be better than what I did, but it’s not great. I like to use LaTeX for displayed equations if necessary, but not in the middle of a paragraph.

  8. Shevach Riabtsev

    In most cases adjacency matrices are sparse and there are a lot of techniques to manipulate (multiply or store) sparse matrices.

    There is a method to know whether a given graph is connected (i.e. any two vertexes can achievable).
    Let A is adjacency matrix of the graph. if the matrix B = I+A+A^2+.. +A^n has zero entries the the graph is disconnected and vice versa

  13. Brandon

    I’ve noticed that the laplacian eigenvalues for weighted matrices, both all-positive as well as with signed (partial) correlation matrices do not have the smallest eigenvalue = 0.

    How does the interpretation of what you’ve written here change for weighted and signed networks?

    Thank you
    Brandon

Comments are closed.