Prev: tensor-methods Next: spectral-techniques
Spectral graph theory is the theory that arises from the following:
These notes consider undirected unweighted graphs that don’t have self-loops.
Given a graph, \(G = (V,E) with \bar V \bar = n\) vertices, the Laplacian matrix associated to \(G\) is the \(n x n\) matrix \(L_G = D - A\) where \(D\) is the degree matrix, a diagonal matrix where \(D(i,i)\) is the degree of the \(i\)th node in \(G\) and \(A\) is the adjacency matrix, with \(A(i,j) = 1\) iff \((i, j) \in E\). So:
\[ L_G(i, j) = \begin{cases} deg(i) & if i = j \\ -1 & if (i, j) \in E \\ 0 & otherwise \end{cases} \]
For ease of notation, the laplacian will be referred to as \(L\).
Prev: tensor-methods Next: spectral-techniques