【图论】Laplacian matrix_综合

原文阅读

Laplacian matrix

Laplacian matrix是图论数学领域的一个概念，又名graph Laplacian, admittance matrix, Kirchhoff matrix或discrete Laplacian，是一个图的矩阵表示。

Definition

Laplacian matrix for simple graphs

给定一个有 $n$ 个节点的简单图 $G$ ，它的Laplacian矩阵 $Ln×n\bf{L}_{n\times n}$ 可以定义为
$L=D?A,{\bf L} = {\bf D} - {\bf A},$
其中， $D\bf{D}$ 是一个degree矩阵， $A\bf{A}$ 是一个adjacency矩阵。对于simple图， $A\bf{A}$ 是一个对角线上元素为0的二值矩阵。

对于directed图，indegree或outdegree都可能用到，完全取决于应用。

$L\bf{L}$ 元素为
$vi?vj0otherwise,{\bf L}_{i,j} := \left \{ \begin{aligned}\deg(v_i) ~~~ & \text{if} ~ i = j\\-1 ~~~ & \text{if} ~ i \neq j ~\text{and}~ v_i \sim v_j \\0 ~~~ & \text{otherwise}\end{aligned}\right.,$
其中， $?\sim$ 表示 $v_i$ 与 $v_j$ 邻接。

Symmetric normalized Laplacian

对称归一化Laplacian矩阵被定义为
$Lsys:=D?12LD?12=I?D?12AD?12.{\bf L}^{\text{sys}} := {\bf D}^{-\frac{1}{2}} {\bf L} {\bf D}^{-\frac{1}{2}} = {\bf I} - {\bf D}^{-\frac{1}{2}} {\bf A} {\bf D}^{-\frac{1}{2}}.$
$Lsys{\bf L}^{\text{sys}}$ 元素为
$vi?vj0otherwise.{\bf L}_{i,j}^{\text{sys}} := \left \{ \begin{aligned}1 ~~~ & \text{if} ~ i = j ~ \text{and} \deg(v_i) \neq 0\\-\frac{1}{\sqrt{\deg(v_i) \deg(v_j)}} ~~~ & \text{if} ~ i \neq j ~\text{and}~ v_i \sim v_j \\0 ~~~ & \text{otherwise}\end{aligned}\right..$

Random walk normalized Laplacian

随机游走归一化Laplacian矩阵定义为
$Lrw:=D?1L=I?D?1A.{\bf L}^{\text{rw}} := {\bf D}^{-1} {\bf L} = {\bf I} - {\bf D}^{-1} {\bf A}.$
$rwsys{\bf rw}^{\text{sys}}$ 元素为
$vi?vj0otherwise.{\bf L}_{i,j}^{\text{rw}} := \left \{ \begin{aligned}1 ~~~ & \text{if} ~ i = j ~ \text{and} \deg(v_i) \neq 0\\-\frac{1}{\sqrt{\deg(v_i)}} ~~~ & \text{if} ~ i \neq j ~\text{and}~ v_i \sim v_j \\0 ~~~ & \text{otherwise}\end{aligned}\right..$

Generalized Laplacian

广义Laplacian被定义为
$otherwise.{\bf Q}_{i,j}^{\text{rw}} := \left \{ \begin{aligned}< 0 ~~~ & \text{if} ~ i = j ~ \text{and} \deg(v_i) \neq 0\\= 0 ~~~ & \text{if} ~ i \neq j ~\text{and}~ v_i \sim v_j \\\text{any number} ~~~ & \text{otherwise}\end{aligned}\right..$

Notice the ordinary Laplacian is a generalized Laplacian.

Example

Labelled graph

一个labelled graph

Degree matrix

$(200000030000002000000300000030000001)\left (\begin{matrix}2 & 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 & 0\\0 & 0 & 0 & 0 & 0 & 1\\\end{matrix}\right )$

Adjacency matrix

$(010010101010010100001011110130000100)\left (\begin{matrix}0 & 1 & 0 & 0 & 1 & 0\\1 & 0 & 1 & 0 & 1 & 0\\0 & 1 & 0 & 1 & 0 & 0\\0 & 0 & 1 & 0 & 1 & 1\\1 & 1 & 0 & 1 & 3 & 0\\0 & 0 & 0 & 1 & 0 & 0\\\end{matrix}\right )$

Laplacian matrix

$(2?100?10?13?10?100?12?10000?13?1?1?1?10?130000?101)\left (\begin{matrix}2 & -1 & 0 & 0 & -1 & 0\\-1 & 3 & -1 & 0 & -1 & 0\\0 & -1 & 2 & -1 & 0 & 0\\0 & 0 & -1 & 3 & -1 & -1\\-1 & -1 & 0 & -1 & 3 & 0\\0 & 0 & 0 & -1 & 0 & 1\\\end{matrix}\right )$

Properties

对于无向图 $G$ ，其Laplacian矩阵为 $L{\bf L}$ ， $L{\bf L}$ 特征值为 $λ0≤λ1≤?λn?1\lambda_0 \leq \lambda_1 \leq \cdots \lambda_{n - 1}$ ，则有：

$L{\bf L}$ 是对称的；
$L{\bf L}$ 是正定的（ $λi≥0,?i\lambda_i \geq 0, \forall i$ ）；
$∑i=0n?1Li,j=∑j=0n?1Li,j=1\sum_{i = 0}^{n - 1} {\bf L}_{i,j} = \sum_{j = 0}^{n - 1} {\bf L}_{i,j} = 1$ ；
$λ0=0,v0=(1,1,?,1)\lambda_0 = 0,~ \pmb{v}_0 = (1, 1, \cdots, 1)$ ；
Laplacian是 $n$ 维向量空间上的函数算子 $V}\rightarrow\mathbb{R}$ ；

$Lf(vi)=∑vj?viwi,j(f(vi)?f(vj){\bf L} f(v_i) = \sum_{v_j \sim v_i} w_{i,j} (f(v_i) - f(v_j)$
二次型：

$fTLf(vi)=12∑ei,jwi,j(f(vi)?f(vj){f^T {\bf L} f}(v_i) = \frac{1}{2}\sum_{e_{i,j}} w_{i,j} (f(v_i) - f(v_j)$
……

Incidence matrix

Incidence matrix刻画了两类对象之间的关系，在graph theory中有广泛的应用。

Undirected and directed graphs

对于图 $G = (V, E)$ ， $n$ 个顶点， $m$ 条边（$|V| \times |E| = m \times n $），有两种incidence矩阵：

Unoriented incidence matrix
- 对于无向图
$Bi,j:={1vi?ej0otherwise.{\bf B}_{i,j} := \left \{ \begin{aligned} 1 ~~~ &v_i - e_j\\ 0 ~~~ &\text{otherwise} \end{aligned} \right. .$
- 对于有向图
$Bi,j:={1vi→ej1vi←ej0otherwise.{\bf B}_{i,j} := \left \{ \begin{aligned} 1 ~~~ &v_i \rightarrow e_j\\ 1 ~~~ &v_i \leftarrow e_j\\ 0 ~~~ &\text{otherwise} \end{aligned} \right. .$
Oriented incidence matrix
- 对于无向图：无向图的有向关联矩阵是图的任何方向的关联矩阵。
- 对于有向图
$Bi,j:={1vi→ej?1vi←ej0otherwise.{\bf B}_{i,j} := \left \{ \begin{aligned} 1 ~~~ &v_i \rightarrow e_j\\ -1 ~~~ &v_i \leftarrow e_j\\ 0 ~~~ &\text{otherwise} \end{aligned} \right. .$

Boundary operator

图的boundary operator定义为：
$?:E(G)→V(G)\vartheta:E(G) \rightarrow V(G)$
而图的co-boundary operator定义为：
$π:V(G)→E(G)\pi:V(G) \rightarrow E(G)$

Discrete differential operator

Incidence矩阵是离散的微分算子。

$\rightarrow {\bf B} f$ 是一个co-boundary mapping；
特别地， $(Bf)(ei,j)f(vj)?f(vi)({\bf B} f) (e_{i,j})f(v_j) - f(v_i)$
Example：
$(f(2)?f(1)f(1)?f(3)f(3)?f(2)f(4)?f(2))=(?110010?100?1100?101)(f(1)f(2)f(3)f(4))\left (\begin{matrix}f(2) - f(1) \\f(1) - f(3) \\f(3) - f(2) \\f(4) - f(2)\end{matrix}\right )= \left (\begin{matrix}-1 & 1 & 0 & 0\\1 & 0 & -1 & 0\\0 & -1 & 1 & 0\\0 & -1 & 0 & 1\\\end{matrix} \right )\left (\begin{matrix}f(1) \\f(2) \\f(3) \\f(4)\end{matrix}\right )$

Laplacian & incidence

$L=BBT{\bf L} = {\bf B} {\bf B}^T$