3
$\begingroup$

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

enter image description here

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}$

$\endgroup$
1
  • $\begingroup$ When you want to calculate Laplacian matrix by $D−A$, you must use symmetric adjacency matrix which is come from undirected graph (section 1.2) not directed graph (section 1.1). Now: $L=\tilde{D}\tilde{D}^\intercal =D−A$ $\endgroup$ Jun 6 at 21:14
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Could you refer to some of these papers? $\endgroup$ Jun 6 at 20:17
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.