Thuật toán pagerank xếp hạng đồ thị | Ôn tập khai phá web
Pagerank là thuật toán xếp hạng đồ thị dựa trên cấu trúc tổng quát, chúng ta có cách để tính được chính xác thứ hạng của từng đỉnh, tuy nhiên khi số đỉnh càng lớn, việc tính toán chính xác là điều gây mất thời gian và không cần thiết. Trong bài viết này mình sẽ hướng dẫn 3 cách để xếp hạng các đỉnh cho đồ thị (mình gọi nhanh là 3 thuật toán pagerank). Về lý thuyết thì các bạn có thể xem slide bài giảng của các thầy/ cô TẠI ĐÂY.
Đề bài: Cho một đồ thị có 3 đỉnh và quan hệ giữa các đỉnh như hình dưới, với d = 1 (damping factor) hãy tính toán thứ hạng của từng đỉnh.
1. Tính chính xác pagerank bằng hệ phương trình
Ta có hệ phương trình sau:
$\begin{cases}r_a = r_c\\r_b = r_a / 2 \\r_c = r_a / 2 + r_b & (1)\\r_a + r_b + r_c = 1\end{cases}$
Mình giải thích qua tại sao lại có hệ phương trình này nha, đầu tiên là tổng thứ hạng của tất cả các đỉnh lúc nào cũng bằng 1 rồi, vậy ta luôn có được phương trình thứ 4 là $r_a + r_b + r_c = 1$.
Tiếp theo để giải được một hệ phương trình có 3 ẩn số thì ít nhất chúng ta phải cần thêm 2 phương trình nữa, ở đây chúng ta sẽ cứ tìm ra hết các phương trình có thể.
Với phương trình đầu $r_a = r_c$, nếu viết đầy đủ thì phải là $r_a = r_c / 1$, với CA là một cạnh của đồ thị và đỉnh C có 1 bậc ra. Với phương trình thứ 2 $r_b = r_a / 2$, với AB là một cạnh của đồ thị và đỉnh A có 2 bậc ra. Với phương trình thứ 3 $r_c = r_a / 2 + r_b$, với AC, BC là một cạnh của đồ thị và A, B lần lượt có 2 và 1 bậc ra.
Tiếp theo việc giải phương trình này thì dễ rồi, chúng ta thay thế xuống phương trình cuối sẽ có:
$r_a + r_a / 2 + r_a / 2 + r_a / 2 = 1$
$=> r_a = 2 / 5, r_b = 1/5, r_c = 2 /5 $.
Chắc là cũng có nhiều bạn thắc mắc là giải dễ như vậy tại sao lại cần cách các xấp xỉ làm gì? Mình cũng sẽ giải thích luôn là đây chỉ là ví dụ với 3 đỉnh, trong các bài toán thực tế thì một đồ thị thường lên tới hàng triệu đỉnh thì việc giải HPT để tìm ra thứ hạng chính xác là điều cực kì khó khăn và không cần thiết.
2. Tính xấp xỉ pagerank bằng thuật toán lặp
Để bắt đầu cách này trước hết chúng ta vẫn phải tìm ra hệ phương trinh $(1)$ trước nha.
Sau đó bắt đầu chúng ta khởi tạo giá trị thứ hạng cho từng đỉnh: $r_a(0) = r_b(0) = r_c(0) = 1/3$, chúng ta có thể khởi tạo bất kì giá trị nào cũng được nha, nếu khởi tạo hơi lỗi thì chúng ta sẽ phải mất nhiều lần lặp hơn mới tìm ra được điểm hội tụ, còn nếu khởi tạo tốt thì có thể chỉ mất 1,2 vòng lặp. Kí hiệu $(0)$ đằng sau mỗi $r_a, r_b, r_c$ để thể hiện cho số vòng lặp, trong trường hợp khởi tạo thì số vòng đã lặp là 0.
+ Vòng 1:
$r_a(1) = r_c(0) / 1 = 1 / 3$
$r_b(1) = r_a(0) / 2 = 1 / 6$
$r_c(1) = r_a(0) / 2 + r_b(0) / 1 = 1 / 2$
+ Vòng 2:
$r_a(2) = r_c(1) / 1 = 1 /2$
$r_b(2) = r_a(1) / 2 = 1/ 6$
$r_c(2) = r_a(1) / 2 + r_b(1) / 1 = 1 /3$
+ Vòng 3:
$r_a(3) = r_c(2) / 1 = 1 / 3$
$r_b(3) = r_a(2) / 1 = 1/ 4$
$r_c(3) = r_a(2) / 2 + r_b(2) / 1 = 5 / 12$
+ Vòng 4:
$r_a(4) = r_c(3) / 1 = 5 / 12$
$r_b(4) = r_a(3) / 2 = 1 / 6$
$r_c(4) = r_a(3) / 2 + r_b(3) / 1 = 5 / 12$
+ Vòng ...
Lặp tới bao nhiêu vòng là tùy vào yêu cầu bài toán mà thầy/ cô giáo đưa ra, còn trên thực tế chúng ta sẽ lặp tới khi nào hội tụ, tức là khi mà vòng lặp sau kết quả không đổi so với kết quả trước hoặc là thay đổi nhỏ hơn một số denta rất nhỏ do chúng ta định nghĩa ra trước.
3. Tính xấp xỉ pagerank bằng thuật toán lặp với ma trận
Lặp bằng tay như cách 2 có thể khiến các bạn rơi vào trầm cảm, cách 3 này như là một cách tóm gọn lại của cách 2 bằng ma trận vậy.
Đầu tiên vẫn là khởi tạo giá trị ban đầu $r_a = r_b = r_c = 1 / 3$
Ta có ma trận:
$\begin{bmatrix}0 & 1/2 & 1/2\\0 & 0 & 1\\1 & 0 & 0\end{bmatrix}$
Ma trận này có được bằng cách lấy 1 chia đều cho số cạnh ra, ví dụ đỉnh A có 2 cạnh ra là AB và AC thì tương ứng vị trí của ma trận là $\begin{bmatrix}0 & 1/2 & 1/2\end{bmatrix}$, tương tự với các đỉnh còn lại.
+ Lặp vòng 1:
$\begin{bmatrix}1/3 \\ 1/3 \\ 1/3\end{bmatrix} * \begin{bmatrix}0 & 1/2 & 1/2\\0 & 0 & 1\\1 & 0 & 0\end{bmatrix} = \begin{bmatrix}1/3 \\ 1/6 \\ 1/2\end{bmatrix}$
+ Lặp vòng 2:
$\begin{bmatrix}1/3 \\ 1/6 \\ 1/2\end{bmatrix} * \begin{bmatrix}0 & 1/2 & 1/2\\0 & 0 & 1\\1 & 0 & 0\end{bmatrix} = \begin{bmatrix}1/2 \\ 1/6 \\ 1/3\end{bmatrix}$
+ Lặp vòng 3:
$\begin{bmatrix}1/2 \\ 1/6 \\ 1/3\end{bmatrix} * \begin{bmatrix}0 & 1/2 & 1/2\\0 & 0 & 1\\1 & 0 & 0\end{bmatrix} = \begin{bmatrix}1/3 \\ 1/4 \\ 5/12\end{bmatrix}$
+ Lặp vòng 4:
$\begin{bmatrix}1/3 \\ 1/4 \\ 5/12\end{bmatrix} * \begin{bmatrix}0 & 1/2 & 1/2\\0 & 0 & 1\\1 & 0 & 0\end{bmatrix} = \begin{bmatrix}5/12 \\ 1/6 \\ 5/12\end{bmatrix}$
Chúng ta có thể thấy sau 4 lần lặp, kết quả ở cách 3 tương ứng với kết quả ở cách 2.
Để nắm vững kiến thức, các bạn nên đọc thêm slide, làm thêm các bài tập về pagerank, chúc mọi người học tập tốt!
.jpg)
