Graphs as matrices and the Laplacian of a graph

Prev: tensor-methods Next: spectral-techniques

Spectral graph theory is the theory that arises from the following:

  1. Represent the graph as a matrix
  2. Study the eigenvectors/eigenvalues of the matrix

These notes consider undirected unweighted graphs that don’t have self-loops.

Graphs as Matrices

Given a graph, vertices, the Laplacian matrix associated to is the matrix where is the degree matrix, a diagonal matrix where is the degree of the th node in and is the adjacency matrix, with iff . So:

For ease of notation, the laplacian will be referred to as .

Prev: tensor-methods Next: spectral-techniques