Construction of graph Laplacian

Question

I have a weighted undirected graph, and all the edge-weights are non-negative.

According to the definition of the graph Laplacian matrix, $L=D-W$. In literature, I found that $D$ is known as degree matrix, $D_{i}=\sum\limits_{j=1}^nW_{ij}$.

So, I am confused about the entries of the $W$ matrix. Let say, there is an edge between $i$th and $j$th node and the edge weight is $e_{ij}(\text{say } 0.5)$. So, my question is what should be the value of $W_{ij} \text{ or } W_{ji}$? Is it equal to $e_{ij} \text{ or } 1$?

Answer 1

Lets suppose your graph has vertices $v_1,\ldots, v_n$.

• $W$ is the weighted adjacency matrix, i.e. the value $W_{ij}$ is the weight of the edge $e = \{v_i,v_j\}$ ($W_{ij} = 0$ if there is no edge between $v_i$ and $v_j$).
• $D$ is the diagonal matrix s.t. $D_{ii} = W(i) := \sum_j W_{ij}$, i.e. $D_{ii}$ is the weighted vertex-degree of $v_i$.

The important thing is the following: Suppose you have a function $f$ on your set of vertices $V$. Then $f$ is nothing but a vector $$f = \begin{pmatrix} f(v_1) \\ \vdots \\ f(v_n) \end{pmatrix}$$ and applying the Laplacian to $f$ yields $$(Lf)(i) = W(i) f(i) - \sum_j W(i,j) f(j)$$