Lý thuyết phổ đồ thị I -- Spectral Graph Theory I

Lý thuyết phổ của đồ thị nghiên cứu gì, tại sao?

Lý thuyết phổ đồ thị là một nhánh nghiên cứu các tính chất đồ thị thông qua các công cụ đại số, mà cụ thể ở đây là ma trận, trị riêng và véc tơ riêng (gọi là phổ). Ngành lý thuyết này đã tồn tại từ những năm 50 [1], và những người quan tâm lý thuyết này chủ yếu là những nhà toán học. Bây giờ, lý thuyết này đã được quan tâm hơn bởi cả các nhà khoa học máy tính vì nó có tính ứng dụng rất cao trong thực tế. Ví dụ như thuật toán Google Pakge Rank hay các thuật toán phát hiện cộng đồng (community detection) trong mạng xã hội đều có thể ứng dụng lý thuyết phổ.

Tại sao đến bây giờ các nhà khoa học máy tính mới quan tâm nhiều hơn? Một trong những lí do hàng đầu đó là tốc độ tính toán. Chúng ta đã nghiên cứu đại số tuyến tính cả trăm, và có lẽ cả ngàn năm rồi, và chúng ta có rất nhiều những công cụ đại số vô cùng mạnh, cho phép chúng ta xử lí ma trận cực kì hiệu quả. Lý thuyết phổ sử dụng đại số để nghiên cứu các tính chất tổ hợp của đồ thị, và một hệ quả tất nhiên đó là chúng ta có thể áp dụng các công cụ đại số sẵn có vào lý thuyết này, qua đó, thu được những thuật toán vô cùng hiệu quả.

Liệu có giới hạn nào mà lý thuyết này không thể áp dụng được? Daniel Spielman, một nhà nghiên cứu nổi tiếng về lý thuyết phổ của đồ thị đã nói : "I'm now shocked when any important property of a graph is not revealed by its eigenvalues and eigenvectors" (tạm dịch: tôi sẽ sốc nếu một tính chất quan trọng bất kì nào của đồ thì mà không thể giải thích được thông qua trị riêng và véc tơ riêng). Điều đó cho thấy phổ của đồ thị gần như bao quát tất cả những tính chất quan trọng của một đồ thị.

Remarks: Loạt bài về lý thuyết phổ này được mình lược dịch trong tập các notes của Dan Spielman [2]. Mình khuyến khích bạn đọc xem bản gốc. Những gì mình viết ra đây trước hết là để mình tự học, sau đó là để các bạn có thể tham khảo thêm, đặc biệt là khi các bạn có vấn đề đọc hiểu bản gốc. Bố cục trình bày của mình cũng khác với bản gốc.

Một số khái niệm cơ bản

Bài này chúng ta làm quen với những khái niệm đầu tiên về lý thuyết phổ của đồ thị. Một số khái niệm cơ bản về đồ thị mình sẽ không nhắc lại nữa mà khuyến khích bạn đọc xem thêm tại đây. Trọng tâm của lý thuyết phổ đó là xem xét đồ thị thông qua ma trận kề. Phần lớn lý thuyết này áp dụng cho đồ thị không có hướng và không có trọng số (lý thuyết này có thể mở rộng một cách tự nhiên cho đồ thị có trọng số, do đó, để đơn giản, ta thường bỏ qua đồ thị có trọng số.)

Một số đồ thị đặc biệt mà chúng ta sẽ thường xuyên áp dụng trong bài đó là:

  1. $K_n$: Là đồ thị đầy đủ (complete graph) có $n$ cạnh, ${n \choose 2}$ cạnh (hình 1a, 1b).
  2. $C_n$: Là đồ thị vòng (cycle graph), có $n$ đỉnh và $n$ cạnh nối các đỉnh tạo thành một vòng (hình 1c).
  3. Đồ thị chính quy bậc $k$ ($k$ regular graph): Là đồ thị trong đó mọi đỉnh của đồ thị đều có bậc $k$ (hình 1d). Bậc của một đỉnh là tổng số cạnh kề với đỉnh đó.

Ta sẽ kí hiệu đồ thị đầu vào là $G(V,E)$ với $n,m$ lần lượt là số đỉnh, cạnh của đồ thị và các đỉnh được đánh số từ $1$ tới $n$.

Ma trận kề: Gọi $A$ là ma trận kề (kích thước $n \times n$) của đồ thị, i.e, $A[i,j] = 1$ nếu $i,j$ kề với nhau và $A[i,j] = 0$ nếu ngược lại. Quy ước $A[i,i] = 0$ với mọi $i$ của đồ thị.

Ma trận bậc: Gọi $D$ là ma trận đường chéo có kích thước $n \times n$ trong đó $D[i,i] = d[i]$ ($d[i]$ là bậc của đỉnh $i$) với mọi $i$ và $D[i,j] = 0$ với mọi $i \not= j$.

Ta kí hiệu $\mathbb{R}^V$ là không gian vector $n$ chiều, trong đó mỗi chiều ứng với một đỉnh của đồ thị. Thông thường, ta sẽ kí hiệu vector bằng chữ thường và in đậm, để phân biệt với các biến. Khi ta viết $\mathbf{x} \in \mathbb{R}^V $, điều đó có nghĩa là vector $\mathbf{x}$ nằm trong không gian $\mathbb{R}^V$, và mỗi đỉnh $i$ của đồ thị sẽ có một đại lượng tương ứng là $\mathbf{x}[i]$.

Trị riêng và véc tơ riêng

Cho $M$ là một ma trận $n \times n$, một vector $\mathbf{v}$ được gọi là vector riêng (eigenvector) tương ứng với trị riêng (eigenvalue) $\lambda$ nếu:

$M\mathbf{v} = \lambda \mathbf{v} \qquad (1)$

Hay nói cách khác, ma trận $M - \lambda I$ là một ma trận suy biến, i.e, các hàng của ma trận $M - \lambda I$ phụ thuộc tuyến tính. Ở đây, $I$ là ma trận đơn vị có đường đường chéo toàn 1 và 0 mọi vị trị trí khác. Do đó, $\lambda$ là nghiệm của phương trình $det(M - x I) = 0$. Phương trình này có $n$ nghiệm thực (các nghiệm có thể là kép) nếu $M$ là một ma trận thực đối xứng. Đó là định lý phổ (spectral theorem), và định lý này là trọng tâm của lý thuyết mà ta nghiên cứu. Định lý phát biểu như sau:

Spectral Theorem: Nếu $M$ là một ma trận đối xứng, kích thước $n \times n$, với các phần tử nằm trong tập số thực $\mathbb{R}$, thì $M$ có $n$ giá trị riêng thỏa mãn $\lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n $ và $n$ vector riêng đơn vị tương ứng $\mathbf{v}_1,\mathbf{v}_2 \ldots, \mathbf{v}_n$ đôi một vuông góc với nhau, i.e, $\mathbf{v}_i^T\mathbf{v}_j = 0$ với mọi $i \not= j$ và $||\mathbf{v}_i|| = 1$ với mọi $i$.

 

Remark: Mặc dù tập các trị riêng là duy nhất, nhưng tập các vector riêng lại không duy nhất. Để thấy điều này, từ định nghĩa của vector riêng, nếu $\mathbf{v}$ là một vector riêng tương ứng với trị riêng $\lambda$ thì ta dễ dàng suy ra với mọi $a \not= 0$, $a\mathbf{v}$ cũng là một vector riếng ứng với trị riêng $\lambda$.

Ma trận Laplace

Ma trận Laplace của đồ thị, kí hiệu là $L$ là một ma trận $n \times n$ được định nghĩa như sau:

$L = D - A \qquad (2)$

Hình 2 minh họa các ma trận $A,D$ và $L$.

Một số tính chất của ma trận Laplace:

  1. $\sum_{1 \leq j \leq n \in V}L[i,j] = 0 \quad \forall 1 \leq i \leq n\qquad (3)$
  2. Dạng toàn phương (quadratic form):

    $\mathbf{x}^TL\mathbf{x} = \sum_{(i,j) \in E}(x[i] - x[j])^2 \quad \forall \mathbf{x} \in \mathbb{R}^V \qquad (4)$

  3. Ma trận Laplace có trị riêng nhỏ nhất $\lambda_1 = 0$ và vector riêng tương ứng là $\mathbf{1}$ ($\mathbf{1}$ là vector mọi tọa độ đều là $1$ )

Chứng minh: Tính chất đầu tiên ta có thể dễ thấy ngay từ ví dụ ở trên, và chứng minh coi như bài tập cho bạn đọc.

Tính chất thứ 2 cần một chút biến đổi đại số, sử dụng hằng đẳng thưc "đáng nhớ" sau:

$\mathbf{x}^TM\mathbf{x} = \sum_{i,j} x[i]M[i,j]x[j] \qquad (5)$

Tính chất 2. Ta có:

$\begin{array} {l} \mathbf{x}^TL\mathbf{x} & = \mathbf{x}^T (D-A)\mathbf{x} \\ & = \mathbf{x}^TD\mathbf{x} - \mathbf{x}^TA\mathbf{x} \\ & = \sum_{i} D[i,i]x[i]^2 - \sum_{i,j}A[i,j]x[i]x[j] \\ & = \sum_{i} D[i,i]x[i]^2 - \sum_{(i,j) \in E}A[i,j]x[i]x[j] \\ & = \sum_{i} D[i,i]x[i]^2 - 2\sum_{(i,j) \in E, i < j}A[i,j]x[i]x[j] \\ & = \sum_{(i,j) \in E} (x[i]^2 - 2x[i]x[j] + x[j]^2) \\ &= \sum_{(i,j) \in E} (x[i] - x[j])^2 \end{array} \qquad (6)$

Từ dòng thứ 2 xuống dòng thứ 3, ta áp dụng hằng đẳng thức $(4)$. Từ dòng thứ 3 xuống dòng thứ 4, ta loại bỏ các ô $i,j$ trong ma trận $A$ mà $A[i,j] = 0$. Các dòng sau đó thì ta chỉ sử dụng phép tách và nhóm.

Tính chất 3. Trước hết, từ tính chất 1 ta suy ra $0$ là một trị riêng với vector riêng $\mathbf{1}$. Thật vậy : $L\mathbf{1} = \sum_{1 \leq i \leq n} \sum_{1 \leq j \leq n \in V}L[i,j] = \sum_{1\leq i \leq n} = 0$, do đó, $L\mathbf{1} = 0\cdot \mathbf{1}$.

Giờ ta chỉ cần chứng minh mọi trị riêng đều lớn hơn hoặc bằng 0. Gọi $\mathbf{v}$ là một vector riêng bất kì với trị riêng $\lambda$. Ta có: $\mathbf{v}^T M \mathbf{v} = \mathbf{v}^T \lambda \mathbf{v} = \lambda ||\mathbf{v}||_2^2$. Theo tính chất 2, $\mathbf{v}^T M \mathbf{v}\geq 0$, do đó, $ \lambda ||\mathbf{v}||_2^2 \geq 0$. Từ đó suy ra $\lambda \geq 0$.


Dạng toàn phương có một ý nghĩa rất hay. Bằng cách áp dụng ma trận Laplace, ta đo được sự bất cân bằng, hay nói cách khác, là độ lệch, giữa các giá trị của các đỉnh.

Ứng dụng ma trận Laplace trong hiển thị đồ thị

Một trong những ứng dụng của phép phổ đó là hiển thị (vizualize) đồ thị. Ví dụ làm thế nào ta hiển thị được một mạng xã hội với trong không gian 2 chiều giống hình dưới đây (nguồn Wikipedia)?
network-viz

Ta có thể ứng dụng phép phân tích phổ vào bài toán này như sau:

  1. Xây dựng ma trận kề và tính ma trận Laplace cho mạng
  2. Tính 2 vector riêng $\mathbf{v}_{n},\mathbf{v}_{n-1}$ ứng với 2 trị riêng có giá trị lớn nhất $\lambda_n,\lambda_{n-1}$ của ma trận Laplace.
  3. Với mỗi đỉnh $i$ của mạng, ta gán cho tọa độ $(\mathbf{v}_{n}[i], \mathbf{v}_{n-1}[i])$ trong không gian 2 chiều, và thêm cạnh giữa các điểm nếu tồn tại cạnh giữa 2 đỉnh tương ứng.

Trong lecture 1, Dan còn minh họa phương pháp này với một số đồ thị khác. Các bạn có thể xem và tự tham khảo thêm.

Bài tập

Bài 1 (Các vector riêng trực giao): Gọi $M$ là một ma trân thực, đối xứng, và $\mathbf{u}, \mathbf{v}$ là hai vector riêng ứng với 2 trị riêng $\lambda, \mu$. Chứng minh rằng nếu $\lambda \not= \mu$ thì $\mathbf{u}$ và $\mathbf{v}$ trực giao (vuông góc).

Bài 2 (Tính bất biến với phép lấy hoán vị): Gọi $\pi$ là một hoán vị của tập đỉnh $V$, i.e, $\pi: V \rightarrow V$. Ma trậ hoán vị (permutation matrix) $\Pi$ tương ứng với $\pi$ được định nghĩa như sau:

$ \Pi[i,j] = \begin{cases} 1, & \mbox{if } i = \pi(j) \\ 0, & \mbox{otherwise }\end{cases} \qquad (7)$

Chứng minh rằng nếu $A\mathbf{v} = \lambda \mathbf{v}$ thì $(\Pi A \Pi^T) (\Pi\mathbf{v}) = \lambda (\Pi\mathbf{v})$. Hay nói cách khác, trị riêng không thay đổi sau khi lấy hoán vị tập đỉnh của đồ thị.

Bài 3 (Tính bất biến với phép quay): Gọi $Q$ là một ma trận trực giao, i.e, là ma trận thỏa mãn $Q^TQ = I$. Chứng minh rằng nếu $A\mathbf{v} = \lambda \mathbf{v}$ thì $(Q A Q^T) (Q\mathbf{v}) = \lambda (Q\mathbf{v})$. Hay nói cách khác, trị riêng không thay đổi sau khi ta quay hệ trục tọa độ đỉnh.

Bài 4 (Các ma trận đồng dạng): Một ma trận $A$ được gọi là đồng dạng (similar) với ma trận $B$ nếu tồn tại một ma trận không suy biến $M$ thỏa mãn: $M^{-1}AM = B$ (ma trận không suy biến là ma trận có det khác 0). Chứng minh rằng trị riêng của $A$ cũng là trị riêng của $B$.

Bài 5 (Phép phân tích phổ): Gọi $M$ là một ma trận thực, đối xứng, với $n$ trị riêng $\lambda_1, \ldots, \lambda_n$ và bộ $n$ vector riêng trực chuẩn (othonormal eigenvectors) tương ứng $\mathbf{v}_1, \ldots, \mathbf{v}_n$. Gọi $\Phi$ là ma trận trong đó cột thứ $i$ của $\Phi$ là vector $\mathbf{v}_i$, và $\Lambda$ là ma trận đường chéo trong đó phần tử thứ $i$ của đường chéo là $\lambda_i$ (các phần tử khác của ma trận là 0). Chứng minh rằng:

$ \Phi^T M \Phi = \Lambda \qquad (8)$

Từ đó suy ra:

$ M = \Phi \Lambda \Phi^T = \sum_{i \in V} \lambda_i \mathbf{v}_i\mathbf{v}_i^T \qquad (9)$

Chú ý: một bộ vector $\{\mathbf{v}_1,\ldots, \mathbf{v}_n\}$ được gọi là trực chuẩn nếu chúng là trực giao và mọi vector là vector đơn vị.

Bài 6 (Vết của ma trận): Vết (Trace) của một ma trận vuông $A$ kích thước $n \times n$, kí hiệ là $\mathrm{Tr}(A)$, là tổng các phần tử trên đường chéo chính của $A$, i.e, $\mathrm{Tr}(A) = \sum_{1 \leq i \leq n} A[i,i]$. Chứng minh rằng:

$\mathrm{Tr}(AB) = \mathrm{Tr}(BA) \qquad (10)$

trong đó $A,B$ là hai ma trận vuông bất kì. Sử dụng tính chất này và các bài tập từ 1-5 để chứng minh:

$\mathrm{Tr}(A) = \sum_{1 \leq i \leq n} \lambda_i \qquad (11)$

Trong đó $\lambda_1, \ldots, \lambda_n$ là các trị riêng của $A$.

Tham khảo
[1] Wikipedia: Spectral Graph Theory, accessed 08 Aug, 2016.
[2] Daniel Speilman. Spectral Graph Theory, Fall 2015

Facebook Comments

Tags: , ,

  1. HTS’s avatar

    1 - Bác ad thiếu chèn link vào chỗ cái khúc "Một số khái niệm cơ bản".
    2 - Cám ơn bác ad.

    Reply

  2. HTS’s avatar

    Ui, thấy còn nhiều lỗi typo quá. Bác ad xóa comment trên giùm em. Em đọc xong rồi tống hợp lại luôn ạ.

    Reply

    1. Hùng Lê’s avatar

      Hi bạn,
      Một số hình vẽ mình chưa có thời gian vẽ nên để trống. Bạn phát hiện lỗi thì post lên đây để mình sửa. Cám ơn bạn.

      Hùng

      Reply

    2. hoangduy’s avatar

      em chào anh hùng!
      Cái ma trận Tương Tự trong bài 4 ở mình dịch là đồng dạng anh ạ.

      Reply

      1. Hùng Lê’s avatar

        Hi,
        Cám ơn em. Nhiều thuật ngữ tiếng Việt anh không biết. Từ đồng dạng nghe rất hay. Sẽ sửa ngay.

        Hùng

        Reply

Reply to Hùng Lê Cancel reply

Your email address will not be published. Required fields are marked *