Thư Viện Tài Liệu Bách Khoa

Pagerank là thuật toán xếp hạng trang bị thị dựa trên kết cấu tổng quát, chúng ta có cách để tính được đúng mự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 nên thiết. Trong nội dung bài viết này bản thân sẽ gợi ý 3 cách để xếp hạng những đỉnh cho đồ thị (mình call nhanh là 3 thuật toán pagerank). Về định hướng thì các bạn cũng có thể xem slide bài bác giảng của những thầy/ côTẠI ĐÂY.

Bạn đang xem: Thư viện tài liệu bách khoa

Đề bài: cho 1 đồ thị tất cả 3 đỉnh cùng quan hệ giữa những đỉnh như hình dưới, cùng với d = 1 (damping factor) hãy giám sát và đo lường thứ hạng của từng đỉnh.

Trong bài viết này mình giải quyết với damping factor = 1, đấy là trường hợp dễ dàng nhất trong các trường hợp, với damping factor khác một mình sẽ có nội dung bài viết sau reviews lại, vì damping factor không giống 1 bọn họ cần lắm rõ định hướng và bí quyết một tí, mặc dù thì cơ bạn dạng vẫn đã tương tự.
1. Tính đúng chuẩn pagerank bằng hệ phương trình

Ta có hệ phương trình sau:

$egincasesr_a = r_c\r_b = r_a / 2 \r_c = r_a / 2 + r_b & (1)\r_a + r_b + r_c = 1endcases$

Mình phân tích và lý giải qua nguyên nhân lại bao gồm hệ phương trình này nha, đầu tiên là tổng thứ hạng của toàn bộ các đỉnh lúc nào thì cũng bằng 1 rồi, vậy ta luôn có được phương trình sản phẩm công nghệ 4 là $r_a + r_b + r_c = 1$.

Tiếp theo nhằm giải được một hệ phương trình bao gồm 3 ẩn số thì ít nhất bọn họ phải cần thêm 2 phương trình nữa, ngơi nghỉ đây bọn họ sẽ cứ tìm ra hết những phương trình tất cả thể.

Với phương trình đầu $r_a = r_c$, trường hợp viết tương đối đầy đủ thì đề nghị là $r_a = r_c / 1$, cùng với CA là một cạnh của trang bị thị và đỉnh C có 1 bậc ra. Cùng với phương trình thứ 2 $r_b = r_a / 2$, cùng với AB là một trong những cạnh của đồ thị cùng đỉnh A tất cả 2 bậc ra. Với phương trình máy 3 $r_c = r_a / 2 + r_b$, cùng với AC, BC là một trong những cạnh của đồ thị cùng A, B lần lượt gồm 2 cùng 1 bậc ra.

Tiếp theo vấn đề giải phương trình này thì dễ dàng rồi, bọn họ thay nạm xuống phương trình cuối đã 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ó rất nhiều bạn vướng mắc là giải dễ như vậy lý do lại đề xuất cách các xấp xỉ làm cho gì? Mình cũng trở thành giải thích luôn là đây chỉ là ví dụ với 3 đỉnh, trong những bài toán thực tế thì một trang bị thị thường lên tới hàng triệu đỉnh thì việc giải HPT nhằm tìm ra sản phẩm hạng và đúng là điều cực kỳ khó khăn và không nên thiết.

Xem thêm: Tin Tức Mới Nhất Về:Cảnh Sát Dubai, Dàn Siêu Xe Triệu Usd Của Cảnh Sát Uae

2. Tính dao động pagerank bằng thuật toán lặp

Để bước đầu cách này trước hết chúng ta vẫn cần tìm ra hệ phương trinh $(1)$ trước nha.

Sau đó ban đầu chúng ta khởi tạo ra giá trị lắp thêm hạng mang đến từng đỉnh: $r_a(0) = r_b(0) = r_c(0) = 1/3$, bạn cũng có thể khởi tạo bất kể giá trị nào cũng khá được nha, giả dụ khởi tạo hơi lỗi thì bọn họ sẽ phải mất quá nhiều lần lặp hơn bắt đầu tìm ra đạt điểm hội tụ, còn giả dụ khởi tạo xuất sắc thì có thể chỉ mất 1,2 vòng lặp. Kí hiệu $(0)$ phía sau mỗi $r_a, r_b, r_c$ để biểu thị cho số vòng lặp, trong trường hợp khởi chế tạo ra 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 từng nào vòng là tùy thuộc vào yêu cầu việc mà thầy/ cô giáo gửi ra, dính trên thực tế bọn họ sẽ lặp tới khi nào hội tụ, có nghĩa là khi nhưng mà vòng lặp sau hiệu quả không đổi so với hiệu quả trước hoặc là chũm đổi nhỏ hơn một trong những denta rất nhỏ do chúng ta định nghĩa ra trước.

3. Tính giao động pagerank bởi thuật toán lặp cùng với ma trận

Lặp thủ công bằng tay như biện pháp 2 hoàn toàn có thể khiến các bạn rơi vào trầm cảm, biện pháp 3 này như là 1 trong những cách tóm gọn gàng lại của bí quyết 2 bằng ma trận vậy.

Đầu tiên vẫn chính là khởi chế tạo ra giá trị ban sơ $r_a = r_b = r_c = 1 / 3$

Ta có ma trận:

$eginbmatrix0 & 50% & 1/2\0 & 0 và 1\1 & 0 và 0endbmatrix$

Ma trận này còn có được bằng phương pháp lấy 1 chia số đông cho số cạnh ra, lấy một ví dụ đỉnh A gồm 2 cạnh ra là AB và AC thì tương xứng vị trí của ma trận là $eginbmatrix0 & 1/2 & 1/2endbmatrix$, tựa như với những đỉnh còn lại.

+ Lặp vòng 1:

$eginbmatrix1/3 \ 1/3 \ 1/3endbmatrix * eginbmatrix0 & 50% & 1/2\0 & 0 và 1\1 và 0 và 0endbmatrix = eginbmatrix1/3 \ 1/6 \ 1/2endbmatrix$

+ Lặp vòng 2:

$eginbmatrix1/3 \ 1/6 \ 1/2endbmatrix * eginbmatrix0 & một nửa & 1/2\0 và 0 & 1\1 và 0 & 0endbmatrix = eginbmatrix1/2 \ 1/6 \ 1/3endbmatrix$

+ Lặp vòng 3:

$eginbmatrix1/2 \ 1/6 \ 1/3endbmatrix * eginbmatrix0 & 1/2 & 1/2\0 & 0 & 1\1 & 0 & 0endbmatrix = eginbmatrix1/3 \ 1/4 \ 5/12endbmatrix$

+ Lặp vòng 4:

$eginbmatrix1/3 \ 1/4 \ 5/12endbmatrix * eginbmatrix0 & một nửa & 1/2\0 & 0 & 1\1 và 0 & 0endbmatrix = eginbmatrix5/12 \ 1/6 \ 5/12endbmatrix$

Chúng ta hoàn toàn có thể thấy sau 4 lần lặp, tác dụng ở phương pháp 3 tương ứng với công dụng ở biện pháp 2.

Để nắm rõ kiến thức, chúng ta nên đọc thêm slide, có tác dụng thêm những bài tập về pagerank, chúc mọi tín đồ học tập tốt!