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:
- Represent the graph as a matrix
- 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