I know that for a simple undirected graph $\mathcal{G}(V,E) $ the Laplacian matrix $L$ is defined as:
$$ L:=D-A$$ where $D$ is the degree diagonal matrix and $A$ is the adjacency matrix of $\mathcal{G}$.
My question is: how can I define the Laplacian for a directed weighted graph $\mathcal{G}(V,W)$ ?
Best Answer
First let me give another common way of computing the Laplacian of an undirected graph $G=(V, E)$ that generalizes more easily to the directed weighted graphs you are interested in.
Suppose $V = (v_1, \dots, v_n)$ and $E = \{1, \dots, m\}$ and fix an arbitrary orientation on the edges. Consider the vertex space $\mathbb{R}^V$ with standard basis $\{\mathbf{e}_1, \dots, \mathbf{e}_n\}$ and, for each edge $i \in \{1,\dots,m\}$, let $\mathbf{n}_i = \mathbf{e}_j - \mathbf{e}_k$. Then the $n \times m$ matrix $N$ whose columns are the $\mathbf{n}_i$ ($i\in[m]$) is called the signed vertex-edge incidence matrix of $G$ (with respect to the fixed orientation).
The key fact is that the Laplacian $L$ of the $G$ is the (transpose of the) Gram matrix of $N$, that is, $L = NN^{\top}$. In particular, the matrix product $NN^{\top}$ does not depend on the orientation we fixed.
Now let $G$ be a weighted directed graph and let $W$ be the $m \times m$ diagonal matrix with entries $W_{ij}$ equal to the weight of edge $i$ if $i=j$ and zero else. Then we can define the Laplacian of $G$ as the matrix product $NWN^{\top}$ where $N$ is the signed vertex-edge incidence matrix of the underlying unweighted graph of $G$. And this definition generalizes the case for unweighted undirected graphs. See Section 3 of this paper for more on the subject.