線性代數在圖論的應用 (三):拉普拉斯矩陣

本文的閱讀等級:中級

G=(V,E) 為一個無向圖 (undirected graph),其中 V=\{v_1,\ldots,v_n\} 是頂點集合,n=\vert V\vert 稱為圖 G 的階 (order),E 是無向邊集合。若頂點 v_iv_j 之間存在一邊,記為 \{v_i,v_j\},我們稱 v_iv_j 鄰接 (adjacent),並稱該邊與二頂點有關聯 (incident)。無向邊不具方向性,\{v_i,v_j\} 是兩頂點組成的集合,即每一邊可視為一無序頂點對。以下考慮簡單無向圖,意思是不存在自迴路 (self-loop),即 \{v_i,v_i\},且不存在重邊 (multiedge),即任二相異頂點至多僅存在一關聯邊。對應 n 階圖 G=(V,E),鄰接矩陣 A=[a_{ij}] 為一 n\times n 階矩陣,定義如下:a_{ij}=1\{v_i,v_j\}\in E,否則 a_{ij}=0 (見“線性代數在圖論的應用 (一):鄰接矩陣”)。顯然,a_{ij}=a_{ji}A 是一對稱矩陣。表面上,鄰接矩陣是一圖的最自然的表示方式,但它的實用價值卻不大,原因在於鄰接矩陣的特徵值和特徵向量未能揭露圖結構的重要訊息,此外,鄰接矩陣的二次型亦缺乏明確的涵義。本文介紹一種適於建立矩陣譜 (相異特徵值集合,spectrum) 理論的無向圖表示矩陣,稱為拉普拉斯矩陣 (Laplacian)。對於頂點 v_i,分支度 (度數,degree) d_i 是所有與 v_i 有關聯的邊數,即鄰接矩陣 A 的第 i 列 (或行) 和,d_i=\sum_{j=1}^na_{ij}。對應無向圖 G,拉普拉斯矩陣 (Laplacian) 定義為 L=D-A,其中 D=\text{diag}(d_1,\ldots,d_n) 稱為分支度矩陣。因為 DA 是對稱矩陣,拉普拉斯矩陣 L 也是對稱矩陣。為簡化符號,頂點 v_i 可用下標 i 表示。下圖為一例:G=(V,E),其中 V=\{1,2,3,4\}E=\{\{1,2\},\{1,3\},\{1,4\},\{3,4\}\}

拉普拉斯矩陣

對應此圖的鄰接矩陣 A、分支度矩陣 D 和拉普拉斯矩陣 L 分別是

\displaystyle  A=\begin{bmatrix}  0&1&1&1\\  1&0&0&0\\  1&0&0&1\\  1&0&1&0  \end{bmatrix},~~D=\begin{bmatrix}  3&0&0&0\\  0&1&0&0\\  0&0&2&0\\  0&0&0&2  \end{bmatrix},~~L=\left[\!\!\begin{array}{rrrr}  3&-1&-1&-1\\  -1&1&0&0\\  -1&0&2&-1\\  -1&0&-1&2  \end{array}\!\!\right]

 
給定一 n 階簡單無向圖 G=(V,E)V=\{1,\ldots,n\},下面介紹三個重要的拉普拉斯矩陣性質。

 
性質一:對於任一 \mathbf{x}=(x_1,\ldots,x_n)^T\in\mathbb{R}^n

\displaystyle  \mathbf{x}^TL\mathbf{x}=\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^na_{ij}(x_i-x_j)^2=\sum_{\{i,j\}\in E}(x_i-x_j)^2

使用定義,直接計算即可證明:

\displaystyle  \begin{aligned}  \mathbf{x}^TL\mathbf{x}&=\mathbf{x}^TD\mathbf{x}-\mathbf{x}^TA\mathbf{x}\\  &=\sum_{i=1}^nd_ix_i^2-\sum_{i=1}^n\sum_{j=1}^na_{ij}x_ix_j\\  &=\frac{1}{2}\left(\sum_{i=1}^nd_ix_i^2-2\sum_{i=1}^n\sum_{j=1}^na_{ij}x_ix_j+\sum_{j=1}^nd_jx_j^2\right)\\  &=\frac{1}{2}\left(\sum_{i=1}^n\sum_{j=1}^na_{ij}x_i^2-2\sum_{i=1}^n\sum_{j=1}^na_{ij}x_ix_j+\sum_{j=1}^n\sum_{i=1}^na_{ji}x_j^2\right)\\  &=\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^na_{ij}(x_i-x_j)^2=\sum_{\{i,j\}\in E}(x_i-x_j)^2.  \end{aligned}

n 維向量 \mathbf{x}=(x_1,\ldots,x_n)^T 代表附著於頂點 1,\ldots,n 的度量值,性質一說明二次型 \mathbf{x}^TL\mathbf{x} 代表所有鄰接頂點的度量值總變異量,也就是度量值的分配平滑性 (smoothness)。明顯地,若 \mathbf{x} 的所有元皆相同,則 \mathbf{x}^TL\mathbf{x}=0

 
性質二:拉普拉斯矩陣 L 是一實對稱半正定矩陣。

對於任一 \mathbf{x}=(x_1,\ldots,x_n)^T\in\mathbb{R}^n,性質一給出 \mathbf{x}^TL\mathbf{x}=\sum_{\{i,j\}\in E}(x_i-x_j)^2\ge 0,故 L 是半正定矩陣。

 
性質三:拉普拉斯矩陣 L 的最小特徵值是 0,對應的特徵向量為 \mathbf{e}=(1,\ldots,1)^T

因為 L 的每一列和皆為 0,立得 L\mathbf{e}=\mathbf{0},即知 L 有特徵值 0,對應特徵向量 \mathbf{e}。半正定矩陣的特徵值必定不為負 (見“半正定矩陣的判別方法”),故 0L 的最小特徵值。

 
若一無向圖的任意兩頂點之間存在一序列的邊,則稱之為連通圖 (connective graph)。所謂連通元件是指圖 G=(V,E) 的頂點子集 S\subseteq V 及相關聯的邊子集 \{\{u,v\}\in E\vert u,v\in S\} 所構成連通圖,但任意 u\in Sv\in V\setminus S 之間不存在連通路徑。拉普拉斯矩陣是實對稱矩陣,故可正交對角化 (見“實對稱矩陣可正交對角化的證明”),這意味 L 的每一特徵值 \lambda_i 的代數重數等於幾何重數,即 L-\lambda_iI 的零空間維數 \dim N(L-\lambda_iI)。以下代數重數和幾何重數簡稱為相重數。

 
定理一:對應無向圖 G 的拉普拉斯矩陣 L 的特徵值 0 的相重數等於 G 的連通元件數。

證明於下:假設圖 G=(V,E)V=\{1,\ldots,n\},包含 p 個連通元件 G_k(V_k,E_k)k=1,\ldots,p,彼此互不連通。令 n 維向量 \mathbf{u}_k 的第 l 元為 1l\in V_k,否則設為 01\le k\le p1\le l\le n。不難驗證 L\mathbf{u}_k=\mathbf{0}1\le k\le p,且 \{\mathbf{u}_1,\ldots,\mathbf{u}_p\} 形成一正交集 (orthogonal set)。考慮 L\mathbf{x}=\mathbf{0},則 \mathbf{x}^TL\mathbf{x}=\sum_{\{i,j\}\in E}(x_i-x_j)^2=0,由此推斷每一 \{i,j\}\in E_k 滿足 x_i=x_j。換句話說,\mathbf{x} 可表示為 \mathbf{u}_1,\ldots,\mathbf{u}_p 的線性組合,故 \dim N(L)=p,證明 L 的特徵值 0 的相重數等於 G 的連通元件數。

 
舉一例說明,見下圖,G 包含連通元件 G_1(V_1,E_1)G_2(V_2,E_2),其中 V_1=\{1,3\}V_2=\{2,4,5\}E_1=\{\{1,3\}\}E_2=\{\{2,4\},\{2,5\}\}

拉普拉斯矩陣2

對應的拉普拉斯矩陣為

\displaystyle  L=\left[\!\!\begin{array}{rrrrr}  1&0&-1&0&0\\  0&2&0&-1&-1\\  -1&0&1&0&0\\  0&-1&0&1&0\\  0&-1&0&0&1  \end{array}\!\!\right]

\mathbf{u}_1=(1,0,1,0,0)^T\mathbf{u}_2=(0,1,0,1,1)^T。明顯地,L\mathbf{u}_1=\mathbf{0}L\mathbf{u}_2=\mathbf{0}\mathbf{u}_1\perp\mathbf{u}_2。為看清圖的連通結構,我們可將頂點排序 \{1,2,3,4,5\} 變更為 \{1,3,2,4,5\}。具體的作法是執行下列排列相似變換 (見“矩陣視覺化”):

\displaystyle  L\mapsto P^TLP

其中 P 是置換第 23 行 (或列) 的基本排列矩陣,即置換單位矩陣 I_523 行 (或列) 的結果。經過頂點排序後的拉普拉斯矩陣為分塊對角矩陣:

\displaystyle  P^TLP=\left[\!\!\begin{array}{rrcrrr}  1&-1&\vline&0&0&0\\  -1&1&\vline&0&0&0\\\hline  0&0&\vline&2&-1&-1\\  0&0&\vline&-1&1&0\\  0&0&\vline&-1&0&1  \end{array}\!\!\right]

其中每一對角分塊即所對應連通元件的拉普拉斯矩陣,有一個相重數為 1 的零特徵值。

 
以下設拉普拉斯矩陣 L 的特徵值按遞增順序排列,0=\lambda_1\le\lambda_2\le\cdots\le\lambda_n。定理一的必然結果:G 是一連通圖若且惟若 \lambda_2>0。在圖論中,\lambda_2 稱為 G 的代數連通度 (algebraic connectivity)。若一連通圖的 \lambda_2 數值小,只要刪除少許邊即可將將圖切割為兩個連通元件;反之,若 \lambda_2 的數值大,則必須刪除很多邊方能將圖切割為二。代數連通度 \lambda_2 涉及較為複雜的分析,下面僅列舉一些基本圖的拉普拉斯矩陣並計算矩陣譜,由此讀者可以略窺代數連通度與圖結構的關係。

 
例一:完全圖 (complete graph)

完全圖 K(V,E) 是指任兩個相異頂點皆有一連接邊,即 E=\{\{i,j\}\vert i,j\in V, i<j\}。完全圖的拉普拉斯矩陣為

\displaystyle  L_K=\left[\!\!\begin{array}{cccc}  n-1&-1&\cdots&-1\\  -1&n-1&\cdots&-1\\  \vdots&\vdots&\ddots&\vdots\\  -1&-1&\cdots&n-1  \end{array}\!\!\right]

完全圖是一個連通圖,定理一表明 L_K 的特徵值 0 的相重數為 1,特徵空間為 \text{span}\{\mathbf{e}=(1,\ldots,1)^T\},即知 L_Kn-1 個非零特徵值,特徵空間為 \text{span}\{\mathbf{e}\} 的正交補餘 \text{span}\{\mathbf{e}\}^{\perp} (因為 L_k 可正交對角化)。若 \mathbf{x}=(x_1,\ldots,x_n)^T\in\text{span}\{\mathbf{e}\}^{\perp},則 \mathbf{x}^T\mathbf{e}=x_1+\cdots+x_n=0。使用此性質,可得

\displaystyle\begin{aligned}  L_K\mathbf{x}&=\left[\!\!\begin{array}{cccc}  n-1&-1&\cdots&-1\\  -1&n-1&\cdots&-1\\  \vdots&\vdots&\ddots&\vdots\\  -1&-1&\cdots&n-1  \end{array}\!\!\right]\begin{bmatrix}  x_1\\  x_2\\  \vdots\\  x_n  \end{bmatrix}\\  &=\begin{bmatrix}  (n-1)x_1-\sum_{i\neq 1}x_i\\  (n-1)x_2-\sum_{i\neq 2}x_i\\  \vdots\\  (n-1)x_n-\sum_{i\neq n}x_i  \end{bmatrix}=\begin{bmatrix}  nx_1\\  nx_2\\  \vdots\\  nx_n  \end{bmatrix}=n\mathbf{x}.\end{aligned}

所以,L_K 有特徵值 0,相重數是 1,以及特徵值 n,相重數是 \dim N(L_K-nI)=\dim\text{span}\{\mathbf{e}\}^{\perp}=n-1。我們將 L_K 的矩陣譜記為 \{0,n^{(n-1)}\},上標括弧內的數字表示相重數 (當相重數不等於 1 時),並知 \lambda_2=n

 
例二:星狀圖 (star graph)

因為頂點標號可以隨意置換,設星狀圖 S(V,E) 的中心點為 v_1,外圍點為 v_2,\ldots,v_n,則 E=\{\{1,i\}\vert 2\le i\le n\}。星狀圖的拉普拉斯矩陣是

\displaystyle  L_S=\left[\!\!\begin{array}{crrrr}  n-1&-1&-1&\cdots&-1\\  -1&1&0&\cdots&0\\  -1&0&1&\cdots&0\\  \vdots&\vdots&\vdots&\ddots&\vdots\\  -1&0&0&\cdots&1  \end{array}\!\!\right]

定理一表明 L_S 的特徵值 0 的相重數為 1。令 n 維向量 \mathbf{x}_j 的第 2 元為 1,第 j 元為 -1,其餘元為 0,其中 j>2。很容易驗證 L_S\mathbf{x}_j=\mathbf{x}_j3\le j\le n,且 \{\mathbf{x}_3,\mathbf{x}_4,\ldots,\mathbf{x}_n\} 構成一線性獨立集,故 L_S 有特徵值 1,相重數至少為 n-2。然而,L_S 的特徵值和等於 \text{trace}L_S=2n-2,因此斷定 L_S 尚有一特徵值 n,相重數是 1。所以,L_S 的矩陣譜為 \{0,1^{(n-2)},n\},得知 \lambda_2=1

 
例三:環狀圖 (ring graph)

在不失一般性的前提下,設環狀圖 R(V,E) 的邊集合為 E=\{\{i,i+1\}\vert 1\le i<n\}\cup\{(1,n)\},則拉普拉斯矩陣為

\displaystyle  L_R=\left[\!\!\begin{array}{rrcrr}    2&-1&&&-1\\    -1&2&-1&&\\    &\ddots&\ddots&\ddots&\\    &&-1&2&-1\\    -1&&&-1&2  \end{array}\!\!\right]

觀察發現 L_R 為一循環矩陣,具有下列形式:

\displaystyle  \begin{bmatrix}      c_0&c_1&c_2&\cdots&c_{n-1}\\      c_{n-1}&c_0&c_1&\cdots&c_{n-2}\\      c_{n-2}&c_{n-1}&c_0&\cdots&c_{n-3}\\      \vdots&\vdots&\ddots&\ddots&\vdots\\      c_1&c_2&\cdots&c_{n-1}&c_0      \end{bmatrix}

比較可得 c_0=2c_1=c_{n-1}=-1,且 c_i=02\le i\le n-2。令 L_R 的特徵值為 \mu_mm=0,1,\ldots,n-1。套用循環矩陣的特徵值公式 (見“特殊矩陣 (7):循環矩陣”),

\displaystyle\begin{aligned}  \mu_m&=\sum_{k=0}^{n-1}c_ke^{-2\pi imk/n}\\  &=2-e^{-2\pi im/n}-e^{-2\pi im(n-1)/n}\\  &=2-e^{-2\pi im/n}-e^{2\pi im/n}e^{-2\pi im}\\  &=2-2\cos\left(\frac{2\pi m}{n}\right),\end{aligned}

其中 i=\sqrt{-1}。因為 \cos\left(\frac{2\pi m}{n}\right)=\cos\left(\frac{2\pi (n-m)}{n}\right),若 n 是奇數,L_R 矩陣譜為 \{0, 2-2\cos\left(\frac{2\pi m}{n}\right)^{(2)}, 1\le m\le \frac{n-1}{2}\},若 n 是偶數,矩陣譜為 \{0, 4, 2-2\cos\left(\frac{2\pi m}{n}\right)^{(2)}, 1\le m\le \frac{n}{2}-1\}。所以,\lambda_2=2-2\cos\left(\frac{2\pi}{n}\right)。對應特徵值 \mu_mm=0,1,\ldots,n-1,循環矩陣的特徵向量公式給出

\displaystyle\begin{aligned}  \displaystyle\mathbf{z}_m&=  \begin{bmatrix}      1\\      e^{-2\pi im/n}\\      \vdots\\      e^{-2\pi im(n-1)/n}      \end{bmatrix}=\begin{bmatrix}  1\\  \cos\left(\frac{2\pi m}{n}\right)-i\sin\left(\frac{2\pi m}{n}\right)\\  \vdots\\  \cos\left(\frac{2\pi m(n-1)}{n}\right)-i\sin\left(\frac{2\pi m(n-1)}{n}\right)  \end{bmatrix}\\  &=\begin{bmatrix}  1\\  \cos\left(\frac{2\pi m}{n}\right)\\  \vdots\\  \cos\left(\frac{2\pi m(n-1)}{n}\right)  \end{bmatrix}-i\begin{bmatrix}  0\\  \sin\left(\frac{2\pi m}{n}\right)\\  \vdots\\  \sin\left(\frac{2\pi m(n-1)}{n}\right)  \end{bmatrix}=\mathbf{x}_m-i\mathbf{y}_m,\end{aligned}

其中 \mathbf{x}_m=\text{Re}[\mathbf{z}_m]\mathbf{y}_m=\text{Im}[\mathbf{z}_m]。實矩陣 L_R 的特徵值 \mu_m 為實數,將上式代入 L_R\mathbf{z}_m=\mu\mathbf{z}_m,可得 L_R\mathbf{x}_m=\mu_m\mathbf{x}_mL_R\mathbf{y}_m=\mu_m\mathbf{y}_m。我們只要考慮線性獨立的 \mathbf{x}_m\mathbf{y}_m 作為特徵向量:若 n 是奇數,對應特徵值 2-2\cos\left(\frac{2\pi m}{n}\right)1\le m\le\frac{n-1}{2},的兩個特徵向量為 \mathbf{x}_m\mathbf{y}_m;若 n 是偶數,對應特徵值 4 的特徵向量為 \mathbf{x}_{n/2}=(1,-1,\ldots,1,-1)^T (\mathbf{y}_{n/2}=\mathbf{0}),對應特徵值 2-2\cos\left(\frac{2\pi m}{n}\right)1\le m\le\frac{n}{2}-1,的兩個特徵向量為 \mathbf{x}_m\mathbf{y}_m

 
例四:道路圖 (path graph)

道路圖 P(V,E) 是指 n 個頂點排成一列,每一頂點和相近頂點鄰接,也就是說 E=\{\{i,i+1\}\vert 1\le i<n\}。道路圖的拉普拉斯矩陣具有三對角形式:

\displaystyle  L_P=\left[\!\!\begin{array}{rrcrr}    1&-1&&&\\    -1&2&-1&&\\    &\ddots&\ddots&\ddots&\\    &&-1&2&-1\\    &&&-1&1  \end{array}\!\!\right]

給定 \mathbf{u}=(u_1,\ldots,u_n)^T,將 L_P 視為一線性變換,則

\displaystyle  L_P\mathbf{u}=\begin{bmatrix}  u_1-u_2\\  -u_1+2u_2-u_3\\  \vdots\\  -u_{n-2}+2u_{n-1}-u_n\\  -u_{n-1}+u_{n}  \end{bmatrix}

的第 1<i<n-u_{i-1}+2u_{i}-u_{i+1} 形如計算一維 Laplace 算子所採用的中央差分近似 (除了正負號相反,見“線性代數在數值分析的應用 (二):Dirichlet 問題”),此即拉普拉斯矩陣的命名由來。

 
利用環狀圖的結果可以導出 L_P 的特徵值。為方便說明,考慮 n=3 的情況,設包含 2n=6 個頂點的環狀圖 R(V,E) 的邊集合為 E=\{\{1,2\}, \{2,3\}, \{3,6\}, \{6,5\}, \{5,4\}, \{4,1\}\}。寫出 6\times 6L_R 矩陣的特徵多項式

\displaystyle  p_{L_R}(\lambda)=\begin{vmatrix}  2-\lambda&-1&0&\vline&-1&0&0\\  -1&2-\lambda&-1&\vline&0&0&0\\  0&-1&2-\lambda&\vline&0&0&-1\\\hline  -1&0&0&\vline&2-\lambda&-1&0\\  0&0&0&\vline&-1&2-\lambda&-1\\  0&0&-1&\vline&0&-1&2-\lambda  \end{vmatrix}

使用分塊矩陣的行列式公式 (見“分塊矩陣的行列式”)

\displaystyle  \begin{vmatrix}  A&B\\  B&A  \end{vmatrix}=\det (A+B)\det (A-B)

其中 AB 是同階方陣,可得

\displaystyle  p_{L_R}(\lambda)=\begin{vmatrix}  1-\lambda&-1&0\\  -1&2-\lambda&-1\\  0&-1&1-\lambda  \end{vmatrix}\cdot\begin{vmatrix}  3-\lambda&-1&0\\  -1&2-\lambda&-1\\  0&-1&3-\lambda  \end{vmatrix}=p_{L_P}(\lambda)\cdot q(\lambda)

表明 p_{L_P}(\lambda) 整除 p_{L_R}(\lambda)。換句話說,L_R 的特徵值即為下面二矩陣的特徵值的聯集:

\displaystyle  L_P=\left[\!\!\begin{array}{rrr}  1&-1&0\\  -1&2&-1\\  0&-1&1  \end{array}\!\!\right],~M=\left[\!\!\begin{array}{rrr}  3&-1&0\\  -1&2&-1\\  0&-1&3  \end{array}\!\!\right]

計算可得 L_P 的特徵值是 0,1,3M 的特徵值是 1, 3, 4。推廣至一般情況,道路圖 L_P 的矩陣譜即是 \{0,2-2\cos\left(\frac{\pi m}{n}\right),1\le m\le n-1\},故 \lambda_2=2-2\cos\left(\frac{\pi}{n}\right)。對應特徵值 2-2\cos\left(\frac{\pi m}{n}\right)m=0,1,\ldots,n-1,請讀者自行驗證 L_P 的特徵向量為

\displaystyle  \begin{bmatrix}  \cos\left(\frac{m\pi}{n}-\frac{m\pi}{2n}\right)\\  \cos\left(\frac{2m\pi}{n}-\frac{m\pi}{2n}\right)\\  \vdots\\  \cos\left(\frac{nm\pi}{n}-\frac{m\pi}{2n}\right)  \end{bmatrix}

 
拉普拉斯矩陣存在多種變化,譬如,我們可以考慮加權圖,其中每一邊附著一非負權重代表二鄰接頂點的相似性。拉普拉斯矩陣的特徵值和特徵向量理論統稱為圖譜分析,其中最具代表性的一項技術是目前廣泛應用於網絡分割 (分群) 的譜聚類分析 (spectral clustering),日後我們將探討這個主題。

相關閱讀:
廣告
本篇發表於 線性代數專欄, 圖論, 應用之道 並標籤為 , , , , 。將永久鏈結加入書籤。

2 Responses to 線性代數在圖論的應用 (三):拉普拉斯矩陣

  1. Meiyue Shao 說道:

    我觉得定理一还可以再加一些解释(或者说是另一种相对麻烦的证明),这样会比较直观地揭示出本质。

    首先,对于连通图而言Laplace矩阵只有一个零特征值(最快捷的证明或许是利用Cauchy交错定理)。然后对于一般的图,将顶点重新编号(或者对Laplace矩阵进行行列重排)可以得到分块对角阵,每个连通分支对应于一个零特征值重数为一的对角块。

    然后对例一之前的小例子的2,3两行两列交换可以看清上述分块对角结构。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s