What's the full assumption for Laplacian matrix $L=BB^T=\Delta-A$?

Question

Graph with no-selfloop, no-multi-edges, unweighted.

directed

For directed graph Adjacency matrix is a non-symmetric matrix $A_{in}$ considering indegree or $A_{out}$ considering outdegree. Degree matrix $\Delta$ is diagonal matrix $\Delta=\Delta_{in}+\Delta_{out}$. The diagonal elements are sum of indegree and outdegree. The oriented incidence matrix $B_{oriented}$, $N\times M$. $b_{im}=1$ if edge $m$ start from $i$. $b_{im}=−1$ if edge $m$ ended to $i$. $b_{im}=0$ otherwise.

$\Delta-A_{in}\neq\Delta-A_{out}\neq B_{oriented}B_{oriented}^T$

undirected

For undirected graph and oriented incidence matrix $B_{oriented}$ have dimension $N\times 2M$. $B_{oriented}B_{oriented}^T=2\Delta-2A$.

unoriented incidence matrix: $b_{im}=1$ if link $m$ incident -- start from $i$ or end to $i$. $b_{im}=0$ otherwise. $B_{unoriented}B_{unoriented}^T=\Delta+A$.

Problem

When Laplacian matrix $L=BB^T=\Delta-A$? Many definitions I saw do not give clear assumption in the context. Say, undirected or directed, oriented or unoriented, $A_{in}$ or $A_{out}$ or $A$? or whatever ... ?

Any references would be greatly appreciated. Thank you.

EDIT

The reference which make me confused is 2011, P.V. Mieghem, Graph Spectra for Complex Networks Chapter 2 Algebraic graph theory P14. 2. The relation between adjacency and incidence matrix is given by the admittance matrix or Laplacian $Q=BB^T=\Delta-A$

EDIT2

1. adjacency matrix

unweighted, nomultiple-edges $A$, $N\times N$, noselfloop $a_{ii}=0$

1.1 directed

$A=\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}$

1.2 undirected

$A=\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 1\\ 1 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 1\\ 1 & 1 & 0 & 0 & 1 & 0 \end{pmatrix}$

2. incidence matrix $B$,

$N\times M$, $M$ are edges. lexicographically ordered.

2.1 directed

$N\times M$, $N=6$, $M=9$,

$e_1=1\rightarrow 2$, $e_2=1\rightarrow 3$, $e_3=1\leftarrow 6$,

$e_4=2\rightarrow 3$, $e_5=2\leftarrow 5$,$e_6=2\rightarrow 6$,

$e_7=3\rightarrow 4$,

$e_8=4\leftarrow 5$,

$e_9=5\leftarrow 6$

$$B_{oriented}=\begin{pmatrix} 1 & 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0\\ -1 & 0 & 0 & 1 & -1 & 1 &0 & 0 & 0\\ 0 & -1 & 0 & -1 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & -1 & -1 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & -1\\ 0 & 0 & 1 & 0 & 0 & -1 & 0 & 0 & 1 \end{pmatrix}$$

2.2 undirected

(oriented) $N\times 2M$

$N=6$, $M=18$,

$e_1=1\rightarrow 2$, $e_2=1\leftarrow 2$, $e_3=1\rightarrow 3$,

$e_4=1\leftarrow 3$, $e_5=1\rightarrow 6$, $e_6=1\leftarrow 6$,

$e_7=2\rightarrow 3$, $e_8=2\leftarrow 3$, $e_9=2\rightarrow 5$,

$e_{10}=2\leftarrow 5$, $e_{11}=2\rightarrow 6$, $e_{12}=2\leftarrow 6$,

$e_{13}=3\rightarrow 4$, $e_{14}=3\leftarrow 4$,

$e_{15}=4\rightarrow 5$, $e_{16}=4\leftarrow 5$,

$e_{17}=5\rightarrow 6$, $e_{18}=5\leftarrow 6$

$$B_{oriented}=\begin{pmatrix} 1 & -1 & 1 & -1 & 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 & 0 & 0 & 1 & -1 & 1 & -1 & 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & -1 & 1 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 1 & -1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 1 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & -1 & 1 & 1 & -1 \\ 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & -1 & 1\\ \end{pmatrix}$$

$$(oriented)~b_{im}= \begin{cases} 1, & \text{if link $e_m=i\rightarrow j$} \\ -1, & \text{if link $e_m=i\leftarrow j$} \\ 0, & \text{otherwise} \end{cases}$$

(unoriented) $N\times M$

$e_1=1 - 2$, $e_2=1 - 3$, $e_3=1 - 6$,

$e_4=2 - 3$, $e_5=2 - 5$,$e_6=2 - 6$,

$e_7=3 - 4$,

$e_8=4 - 5$,

$e_9=5 - 6$

$$B_{unoriented}=\begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 1 & 1 &0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}$$

$$(unoriented)~b_{im}= \begin{cases} 1, & \text{if link $e_m=i - j$ incident} \\ 0, & \text{otherwise} \end{cases}$$

3. degree matrix

$\Delta_{ii} =deg(i) = \sum_j A_{ij}$. $\Delta_{ij}=0$, $i\neq j$

3.1 directed

$\begin{pmatrix} 2＋1 & 0 & 0 & 0 & 0 & 0\\ 0 & 2＋2 & 0 & 0 & 0 & 0\\ 0 & 0 & 1＋2 & 0 & 0 & 0\\ 0 & 0 & 0 & 0＋2 & 0 & 0\\ 0 & 0 & 0 & 0 & 2＋1 & 0\\ 0 & 0 & 0 & 0 & 0 & 2＋1 \end{pmatrix}$

3.2 undirected

$\begin{pmatrix} 3 & 0 & 0 & 0 & 0 & 0\\ 0 & 4 & 0 & 0 & 0 & 0\\ 0 & 0 & 3 & 0 & 0 & 0\\ 0 & 0 & 0 & 2 & 0 & 0\\ 0 & 0 & 0 & 0 & 3 & 0\\ 0 & 0 & 0 & 0 & 0 & 3 \end{pmatrix}$

4. Laplacian matrix

4.1 directed

$B_{oriented}B_{oriented}^T$

$\begin{pmatrix} 3 & -1 & -1 & 0 & 0 & -1\\ -1 & 4 & -1 & 0 & -1 & -1\\ -1 & -1 & 3 & -1 & 0 & 0\\ 0 & 0 & -1 & 2 & -1 & 0\\ 0 & -1 & 0 & -1 & 3 & -1\\ -1 & -1 & 0 & 0 & -1 & 3 \end{pmatrix}$

4.2 undirected

(oriented)

$B_{oriented}B_{oriented}^T=2\Delta -2A$

$\begin{pmatrix} 6 & -2 & -2 & 0 & 0 & -2\\ -2 & 8 & -2 & 0 & -2 & -2 \\ -2 & -2 & 6 & -2 & 0 & 0 \\ 0 & 0 & -2 & 4 & -2 & 0 \\ 0 & -2 & 0 & -2 & 6 & -2 \\ -2 & -2 & 0 & 0 & -2 & 6 \end{pmatrix}$

(unoriented)

$B_{unoriented}B_{unoriented}^T=\Delta + A$

$\begin{pmatrix} 3 & 1 & 1 & 0 & 0 & 1\\ 1 & 4 & 1 & 0 & 1 & 1\\ 1 & 1 & 3 & 1 & 0 & 0\\ 0 & 0 & 1 & 2 & 1 & 0\\ 0 & 1 & 0 & 1 & 3 & 1\\ 1 & 1 & 0 & 0 & 1 & 3 \end{pmatrix}$

Answer 1

As far as I know Laplacians worthy of the name always assume undirected graphs, because you want them to be symmetric. If you want to define the Laplacian of a directed graph, it should end up being the Laplacian of the symmetrized (hence undirected) graph, a priori. There might be papers dealing with other definitions but they should make it clear then.

Answer 2

Here is one most closest to the expectation

Definition 2.5. Given a directed or undirected graph $G= (V,E)$, with $V=\{v_1,\cdots,v_m\}$,the adjacency matrix $A(G)$ of $G$ is the symmetric $m\times m$ matrix $(a_{ij})$ such that

(1) If $G$ is directed, then $a_{ij}=1$ (if there is some edge $(v_i,v_j)\in E$ or some edge $(v_j,v_i)\in E$), otherwise $a_{ij}=0$.

(2) Else if $G$ is undirected, then $a_{ij}=1$ (if there is some edge $(v_i,v_j)\in E$) , otherwise $a_{ij}=0$.

So that, the adjacency of directed graph is same with the undirected graph which is symmetric.

Proposition 2.1. Given any directed graph $G$ if $\tilde{D}$ is the incidence matrix of $G$, $A$ is the adjacency matrix of $G$, and $D$ is the degree matrix such that $D_{ii}=d(v_i)$, then $\tilde{D}\tilde{D}^\intercal=D−A$.

Well, for directed graph with same adjacency matrix of corresponding undirected graph, $\tilde{D}\tilde{D}^\intercal=D−A$.

Consequently, $\tilde{D}\tilde{D}^\intercal$ is independent of the orientation of $G$ and $D−A$ is symmetric, positive,semidefinite; that is, the eigenvalues of $D−A$ are real and nonnegative.

In my test, The symmetric of $\tilde{D}\tilde{D}^\intercal$ is independent of the orientation of $G$.

The matrix $L=\tilde{D}\tilde{D}^\intercal =D−A$ is called the (unnormalized) graph Laplacian of the graph $G$.