= Weighted graph Laplacian
{c}
{title2=$L_w$}
For a finite <undirected graph> without <self-loops>, give each <edge> a symmetric nonnegative weight $w_{ij}=w_{ji}$. In the <weighted graph>, set $(A_w)_{ij}=w_{ij}$ for an <edge> and zero otherwise, and $(D_w)_{ii}=\sum_jw_{ij}$ with all other entries zero. The <Weighted graph Laplacian> is
$$
L_w=D_w-A_w,\qquad
(L_wx)_i=\sum_jw_{ij}(x_i-x_j),\qquad
x^TL_wx=\sum_{\{i,j\}\in E}w_{ij}(x_i-x_j)^2.
$$
Each <edge> appears once in the <quadratic form>. For the <path graph> $A-B-C$ with weights $w_{AB}=2$ and $w_{BC}=3$,
$$
L_w=\begin{pmatrix}2&-2&0\\-2&5&-3\\0&-3&3\end{pmatrix},\qquad
x=\begin{pmatrix}2\\0\\-1\end{pmatrix},\qquad
x^TL_wx=2(2-0)^2+3(0-(-1))^2=11.
$$
The <Weighted graph Laplacian> is still a <positive semidefinite matrix>. Its <kernel> consists of <vectors> constant on each <connected component of a graph> after zero-weight <edges> are removed: an <edge> of weight zero imposes no constraint. In an <electrical network>, taking the weights to be <electrical conductances> makes $x^TL_wx$ the total power dissipated by <Joule heating> when $x$ gives the <voltages> at the <vertices>. This physical interpretation explains why stronger connections penalize disagreement more heavily.https://www.cs.yale.edu/homes/spielman/PAPERS/SGTChapter.pdf[Spielman, Spectral Graph Theory, Section 16.3.2: resistor networks]{ref}
Back to article page
