Đến nội dung

Hình ảnh

Toán học trong tìm kiếm web

- - - - -

  • Please log in to reply
Chủ đề này có 3 trả lời

#1
E. Galois

E. Galois

    Chú lùn thứ 8

  • Quản lý Toán Phổ thông
  • 3861 Bài viết

Câu lạc bộ toán học Explorer (Hoa Kì) đã có một modun về Toán học trong tìm kiếm Web. Công trình này được tài trợ bởi Quỹ Khoa học Quốc gia Hoa Kì. BBT xin giới thiệu từng phần modun này.

Lời nói đầu

Trong hai thập kỷ qua, công nghệ đã không ngừng phát triển. Từ 3 trang web đầu tiên (Microsoft, Netscape, và Amazon) đến hơn 800 triệu trang web trong năm 1999 và trên 50 tỷ trang ngày nay, Internet đã tăng trưởng theo cấp số nhân. Ngay cả một lần lướt web bình thường trên Internet cũng đủ để thuyết phục bạn rằng có một số lượng lớn thông tin và liên kết trực tuyến có sẵn. Tuy nhiên, tất cả các thông tin này đều là vô ích nếu như chúng ta không có một cách tìm kiếm và phân loại nó. Từ công cụ tìm kiếm đầu tiên là Archie vào năm 1990 cho đến các công cụ tìm kiếm hiện đại mà chúng ta sử dụng ngày nay, sự liên kết của các thông tin trực tuyến có sẵn là một vấn đề rất quan trọng.

 

h1.jpg

Một ảnh chụp của đồ thị Internet. Hình ảnh được cung cấp bởi Wikipedia

 

Trong mô-đun này, chúng ta cố gắng phân tích các vấn đề toán học đằng sau một trong những công cụ tìm kiếm phổ biến nhất: Google. Hai bài giảng đầu tiên là khép kín và nó có thể được đọc một cách độc lập. Tuy nhiên hai bài giảng tiếp theo sử dụng kiến thức được nói đến trước đó.



1. Bài giảng 1: Sơ lược về Đại số tuyến tính.
2. Bài giảng 2: Đồ thị định hướng - Ma trận chuyển tiếp
3. Bài giảng 3: Thuật toán PageRank - Toán học của Google Search
4. Bài giảng 4: Thuật toán HITS - Hub và quyền truy cập trên Internet
5. Bài giảng 5: Toán Internet
6. Tài liệu tham khảo


1) Xem cách đăng bài tại đây
2) Học gõ công thức toán tại: http://diendantoanho...oạn-thảo-latex/
3) Xin đừng đặt tiêu đề gây nhiễu: "Một bài hay", "... đây", "giúp tớ với", "cần gấp", ...
4) Ghé thăm tôi tại 
http://Chúlùnthứ8.vn

5) Xin đừng hỏi bài hay nhờ tôi giải toán. Tôi cực gà.


#2
E. Galois

E. Galois

    Chú lùn thứ 8

  • Quản lý Toán Phổ thông
  • 3861 Bài viết

PHẦN 1 - SƠ LƯỢC VỀ ĐẠI SỐ TUYẾN TÍNH 
Chúng ta bắt đầu bằng cách nhắc lại một số kiến thức liên quan đến đại số tuyến tính. Lý thuyết ở đây, tất nhiên không được nêu lên một cách tổng quát, nhưng đơn giản và thích hợp với cuộc thảo luận của chúng ta.

 

Ký hiệu tập hợp của tất cả các số thực là $\mathbb{R}$. Một $\textit{vector}$ có chiều dài $n$ là một danh sách có $n$ phần tử, còn được gọi là $\textit{vector cột}$. Ký hiệu vector $v$ có các phần tử $x_1 , x_2 , ..., x_n$ như sau:
$$v=\begin{bmatrix}x_1\\x_2 \\ \vdots \\ x_n\end{bmatrix}$$
Ví dụ 1: Các phần tử của một vectơ nguyên tắc có thể được bất cứ điều gì: từ ngữ, màu sắc, số, ... Sau đây là những ví dụ của vectơ:
$$\begin{bmatrix}I \\ am \\ a \\ vector\end{bmatrix};\begin{bmatrix}{\color{Red}{Red}}\\{\color{Blue}{Blue}}\\{\color{Green}{Green}}\end{bmatrix};\begin{bmatrix}1.1\\0 \\ 13.5\end{bmatrix};\begin{bmatrix}1\\ 0\end{bmatrix};\begin{bmatrix}X\\ O\\ X\\ O\\ X\end{bmatrix}$$
Tuy nhiên, chúng ta sẽ chỉ nhìn vào vector có phần tử là các số thực (có nghĩa là $x_1 , x_2 , ..., x_n$ là các số thực). Như trong trường hợp các số thực, vectơ thực sự có thể được thêm vào hoặc nhân bởi một số thực (được gọi là vô hướng ) một cách đơn giản:
Phép cộng:
$$\begin{bmatrix}x_1\\ x_2\\ \vdots \\ x_n\end{bmatrix}+\begin{bmatrix}y_1\\ y_2\\ \vdots \\ y_n\end{bmatrix}=\begin{bmatrix}x_1+y_1\\ x_2+y_2\\ \vdots \\ x_n+y_n\end{bmatrix}$$
Phép nhân:
$$a.\begin{bmatrix}x_1\\ x_2\\ \vdots \\ x_n\end{bmatrix}=\begin{bmatrix}a.x_1\\ a.x_2\\ \vdots \\ a.x_n\end{bmatrix}$$
Ví dụ 2: Theo ký hiệu hai ở trên, chúng ta có thể dễ dàng kiểm tra xem:
$$\begin{bmatrix}1.14\\ 5\\ \pi\end{bmatrix}+\begin{bmatrix}2\\ -1.86\\ 0\end{bmatrix}=\begin{bmatrix}3.14\\ 3.14\\ \pi\end{bmatrix}; \pi .\begin{bmatrix}1\\ 5\\ \dfrac{1}{2}\end{bmatrix}=\begin{bmatrix}\pi\\ 5\pi\\ \dfrac{\pi}{2}\end{bmatrix}$$
Bài toán 1:
1. Liệu có thể nhân hai vectơ? Làm thế nào để cộng vectơ độ dài khác nhau?
2. Có bao nhiêu vectơ có độ dài 5 với phần tử số nguyên đó? Điều gì sẽ xảy ra nếu chúng ta yêu cầu rằng tất cả các phần tử khác nhau?

Theo cách tương tự, chúng ta định nghĩa khái niệm một ma trận . Một ma trận $m \times n$ là một mảng hình chữ nhật có chiều cao $m$ và chiều rộng $n$ . Điều này cũng có thể được xem như là xếp $m$ vectơ $n$ chiều liên tiếp (các vectơ có thể khác nhau hoặc không). Một lần nữa, các phần tử là các số thực. Chúng ta biểu thị $A$ là ma trận $m \times n$ với các phần tử $a_{ij}$ như sau:
matrix.gif

Điều này có nghĩa rằng trên hàng $i$ và cột $j$, chúng ta tìm thấy số thực $a_{ij}$ . Ví dụ, trên hàng đầu tiên, cột thứ hai nằm ở phần tử $a_{12}$. Chú ý rằng một vector $m$ chiều chỉ là một ma trận $m \times 1$ và một số thực sự là một ma trận $1\times 1$ . Nếu $m = n$ thì ma trận được gọi là một ma trận vuông , kích thước $n$ . Đây là những gì chúng ta sẽ xem xét từ bây giờ. Nó giúp cho việc bây giờ để nói về đường chéo của một ma trận, trong đó bao gồm những phần tử mà số hàng bằng số cột (các phần tử, $a_{11} , a_{22} , …, a_{nn}$ ).

Ví dụ 3: Sau đây là những ví dụ của các ma trận, nhưng chỉ có ba ma trận vuông:
$$\begin{bmatrix}1 &0 \\2 &-3 \\ 4& 7\end{bmatrix};\begin{bmatrix}1 &0 \\ 0 & 1\\ 0 &0 \\ 0 & 0\end{bmatrix};\begin{bmatrix}0& 0&1 \\ 1& 0& 0\\ 0& 1& 0\end{bmatrix};\begin{bmatrix}a &b \\b &a \end{bmatrix};\begin{bmatrix} 5& -1& 11\\ -1& 0& 3\\ 11& 3& 9\end{bmatrix}$$
Chú ý rằng hai ma trận cuối là "đặc biệt": chúng là các ma trận đối xứng. Điều này có nghĩa là phần tử trên hàng $i$ và cột $j$ bằng phần tử trên hàng $j$ cột $i$ (hoặc nếu không nói $a_{ij} = a_{ji}$ ). Như một bài tập dễ dàng, chứng minh rằng bất kỳ ma trận đường chéo (có số không ở khắp mọi nơi, ngoại trừ trên đường chéo) là đối xứng. Các ma trận có những đường chéo và số không ở khắp mọi nơi khác được gọi là ma trận đồng nhất và được ký hiệu là $I$ . Phép nhân ma trận được thực hiện theo cách chung sau đây:
multiplication0.gif
Ở đó mà các phần tử $c_{ij}$ được cho bởi công thức:
$$c_{ij}=\sum_{k=1}^{n}a_{ik}.b_{kj}=a_{i1}.b_{1j}+a_{i2}.b_{2j}+...+a_{in}.b_{nj}$$
Nhân một ma trận với một véc tơ được thực hiện như sau:
multiplication3.gif
mọi phần tử $y_i$ kết quả từ các vector được cho bởi công thức
$$y_{i}=\sum_{k=1}^{n}a_{ik}.x_{k}=a_{i1}.x_{1}+a_{i2}.x_{2}+...+a_{in}.x_{n}$$
Hai hoạt động ma trận khác, cộng và phép nhân vô hướng, được thực hiện như trong trường hợp của vectơ. Cộng ma trận $A$ và $B$ đưa ra một ma trận $C$ trong đó có các phần tử trên hàng $i$ và cột $j$ bằng tổng của các phần tử tương ứng của $A$ và $B$ . Nhân ma trận $A$ với một số thực $A$ là giống như nhân mọi phần tử của $A$ với $A$ .

Ví dụ 4: Tất cả các hoạt động trên ma trận sẽ trở nên rõ ràng hơn thông qua các ví dụ sau đây:
$$\begin{bmatrix}0&0 &1 &1 \\ 1& 0 & 0 & 0\\ 1 & 1 & 0 &1 \\ 1 & 1 &0 &0 \end{bmatrix} . \begin{bmatrix}12\\4 \\9 \\6\end{bmatrix} = \begin{bmatrix}15\\12 \\22 \\16\end{bmatrix};\begin{bmatrix}1 &2 \\3 &4 \end{bmatrix} . \begin{bmatrix}0 &1 \\ 2 & 3\end{bmatrix} = \begin{bmatrix}4 & 7\\ 8 & 15\end{bmatrix}$$

Bài toán 2: Xem xét các ma trận sau đây:
$$A=\begin{bmatrix}1& 1 & 1\\ 1&1 &2 \\ 0 &0 &0 \end{bmatrix}; B = \begin{bmatrix}\sqrt3 &1 &0 \\0 &\sqrt2 &1 \\1 &0 &1 \end{bmatrix};C=\begin{bmatrix}1&1 &0 \\ 1 & 1 &0 \\ 1 &2 &0 \end{bmatrix}$$
1. Tìm $A + B$ , $B - C$ và $A- B$ ?
2. Chứng minh $(A+ B) + C = A+(B+ C)$ và $(A .B ).C = A . (B .C)$.
3. Tìm tích của $A$ với cột đầu tiên của $C$ .



Định lý 1: Đối với bất kỳ ma trận $A$ , $B$ , $C$ có cùng kích thước, ta có:
$$(A+B).C=A.C+B.C;C. (A+B ) = C.A+C.B$$ .


Ta có thể quan sát rằng có một sự tương tự giữa các ma trận $A$ và $C$ trong Vấn đề 2. ở trên. Sự tương tự xuất phát từ thực tế rằng phần tử trên hàng $i$ và cột $j$ trong ma trận $A$ bằng các phần tử trên hàng $j$ và cột $i$ trong ma trận $C$ . Tất nhiên, các phần tử trên đường chéo là như nhau. Do đó chúng ta nói rằng $A$ là transpose của $C$ , hoặc $C$ là chuyển vị của $A$ . Nói chung, đối với một ma trận $A$ , chúng ta kí hiệu chuyển vị của nó $A^t$ . Trực quan hơn, có thể đưa ra một ma trận chuyển vị của $A$ bằng cách trao đổi các phần tử ở hàng $i$ , cột $j$ với phần tử tại hàng $j$ , cột $i$ . Nếu chúng ta làm điều này hai lần chúng ta nhận thấy rằng chuyển vị của ma trận chuyển vị là ma trận ban đầu, hoặc ( $A^t )^t = A$ .


Định lý 2: Đối với bất kỳ ma trận $A$ , $B$ , ta có:
$$(A.B)^t = B^t .A^;(A+B)^t = A^t + B^t$$ .


Bây giờ chúng ta giới thiệu hai khái niệm quan trọng trong lý thuyết về ma trận: vectơ riênggiá trị riêng. Chúng ta nói rằng số thực $z$ là một giá trị riêng cho $A$ nếu có tồn tại một vector $v$ thực $n$ chiều mà $A.v$ = $z.v$ . Khi đó vector $v$ được gọi là vectơ riêng tương ứng với giá trị riêng $z$ . Đây không phải là định nghĩa chung nhất, nhưng nó sẽ đủ cho các mục đích của chúng ta. Nhìn chung giá trị riêng và các vectơ riêng là phức tạp, và không có thật. Nếu chúng ta giả sử rằng $A$ là một ma trận thực đối xứng có kích thước $n$ , khi đó chúng ta biết rằng nó có $n$ giá trị riêng thực và tất cả các vectơ riêng cũng thực. Trong thực tế, một ma trận kích thước $n$ có thể có nhiều nhất là $n$ giá trị riêng thực.
Để làm cho những định nghĩa rõ ràng hơn, xem xét ví dụ sau đây:

Ví dụ 5: ma trận $A=\begin{bmatrix}1 & 0\\2 &3 \end{bmatrix}$ có vectơ riêng $v=\begin{bmatrix}
0\\1 \end{bmatrix}$ , giá trị riêng $z$ = 3 tương ứng với vectơ riêng này. Thật vậy:
$$\begin{bmatrix}1 & 0\\2 &3 \end{bmatrix}.\begin{bmatrix}0\\1 \end{bmatrix}=\begin{bmatrix}0\\3 \end{bmatrix}=3.\begin{bmatrix}0\\1 \end{bmatrix}$$


Định lý 3: Bất kỳ ma trận $A$ đều có giá trị riêng tương tự như chuyển vị của nó $At$ .


Tất nhiên, nói chung một ma trận $A$ và chuyển vị $A^t$ không có cùng các vectơ riêng tương ứng với các giá trị riêng phổ biến. Đối với các ma trận trong ví dụ trên, $A^t=\begin{bmatrix}1 &2 \\ 0 & 3\end{bmatrix}$ có giá trị riêng $z = 3$ nhưng vectơ riêng tương ứng $u=\begin{bmatrix}1\\1 \end{bmatrix}$. Điều này theo tính toán dưới đây
$$\begin{bmatrix}1 & 2\\0&3 \end{bmatrix}.\begin{bmatrix}1\\1 \end{bmatrix}=\begin{bmatrix}3\\3 \end{bmatrix}=3.\begin{bmatrix}1\\1 \end{bmatrix}$$
Một quan sát quan trọng là một ma trận $A$ trong nhiều trường hợp có nhiều hơn một vectơ riêng tương ứng với giá trị riêng. Các vectơ riêng có tương ứng với cùng một giá trị riêng có thể không có quan hệ với nhau. Tuy nhiên chúng có thể có liên quan, ví dụ như nếu một vectơ là tích của một số với một vectơ khác. Chính xác hơn, trong ví dụ cuối cùng, vector có các phần tử là 0 và 1 là một vectơ riêng, mà vector có phần tử là 0 và 2 cũng là một vectơ riêng. Nó là một bài tập tốt để kiểm tra điều này bằng cách tính toán trực tiếp như trong Ví dụ 5.
Ma trận $A$ được gọi là ma trận cột-ngẫu nhiên nếu tất cả các phần tử của nó lớn hơn hoặc bằng số không (không âm) và tổng của các phần tử trong mỗi cột là bằng 1. Nếu tất cả các phần tử của một ma trận không âm, khi đó chúng ta nói rằng chính nó là ma trận không âm . Hơn nữa, một ma trận dương là tất cả các phần tử của nó là số thực dương (lớn hơn không) .
 

Ví dụ 6: Hãy xem xét một ma trận $A$ với chuyển vị $A^t$ :
examples5a.gif
Thật dễ dàng để thấy rằng $A$ là ma trận cột-ngẫu nhiên, trong khi $A^t$ thì không. Tuy nhiên, tổng của các phần tử trên mỗi hàng của $A^t$ là bằng 1. Chúng ta thấy $z = 1$ là một giá trị riêng cho $A^t$ , tương ứng vectơ riêng $u=\begin{bmatrix}1\\1\\1\\1 \end{bmatrix}$.



Điều này là hiển nhiên vì $A^t .v = 1 . v$ . Do đó, từ định lý 3, $1$ là một giá trị riêng của ma trận $A$ và tiếp theo chúng ta muốn tìm thấy một vectơ riêng tương ứng với giá trị riêng này cho $A$ . Gọi $u$ là một vectơ riêng. Để tìm $u$ một cách rõ ràng chúng ta viết các phương trình
$$\begin{bmatrix}0 & 0 &1 &\frac{1}{2} \\ \frac{1}{3} &0 &0 &0 \\ \frac{1}{3} & \frac{1}{2}&0 &\frac{1}{2} \\ \frac{1}{3} &\frac{1}{2} & 0 &0 \end{bmatrix} . \begin{bmatrix}x_1\\x_2 \\ x_3\\ x_4\end{bmatrix} = 1. \begin{bmatrix}
x_1\\x_2 \\ x_3\\ x_4 \end{bmatrix}$$
Trong đó: $u= \begin{bmatrix}x_1\\x_2 \\ x_3\\ x_4\end{bmatrix} ;x_1;x_2; x_3; x_4$ là tất cả các số thực tế mà chúng ta chưa biết. Thực hiện phép nhân, chúng ta thấy rằng
eq4.gif
Thay thế $x_4=\frac{1}{2}x_1$ trong phương trình thứ ba chúng ta có được $x_3=\frac{3}{4}x_1$ và do đó, các vector $u$ có dạng
$$u=\begin{bmatrix}x_1\\x_2 \\x_3 \\x_4 \end{bmatrix}=\begin{bmatrix}x_1\\ \frac{1}{3}.x_1 \\ \frac{3}{4}.x_1 \\ \frac{1}{2}.x_1 \end{bmatrix}=x_1.\begin{bmatrix}1\\ \frac{1}{3}\\ \frac{3}{4}\\ \frac{1}{2} \end{bmatrix}=\frac{x_1}{12}.\begin{bmatrix}12\\4\\ 9\\ 6 \end{bmatrix}$$
Khi $x_1$ chỉ là một số thực (do đó là một vô hướng) chúng ta có thể $x_1 = 12$ và chúng ta đã chứng minh rằng các vector có phần tử là $12, 4, 9, 6$ (từ trên xuống dưới) là một vectơ riêng cho $A$ .

Trong phần đầu tiên của ví dụ trước chúng ta đã chỉ cho thấy $1$ là một giá trị riêng cho trường hợp cụ thể. Tuy nhiên, điều này là đúng cho bất kỳ ma trận cột ngẫu nhiên, như đã nêu dưới đây.


Định lý 4: Bất kỳ ma trận cột-ngẫu nhiên đều có $z= 1$ là giá trị riêng.


Chú ý rằng cũng vectơ riêng mà chúng ta tìm thấy trong phần thứ hai của ví dụ trên là khá "đặc biệt". Chúng ta đã chọn $x_1 = 12$ và chúng ta có được một vectơ riêng với phần tử dương. Tuy nhiên, nếu chúng ta chọn $x_1 = -12$ sau đó chúng ta có được một vectơ riêng với các số âm (nhỏ hơn 0).


Định lý 5: Với mọi ma trận cột-ngẫu nhiên dương, khi đó bất kỳ vectơ riêng tương ứng với các giá trị riêng $z = 1$ có hoặc chỉ phần tử dương hoặc chỉ phần tử âm.


Bài toán 3: Dễ thấy ma trận $\begin{bmatrix}\frac{1}{2} &0 \\\frac{1}{2} &1 \end{bmatrix}$ là một ma trận-cột ngẫu nhiên và có $z= 1$ là giá trị riêng. Tìm một vectơ riêng để tương ứng với giá trị riêng như vậy mà tất cả các phần tử của nó là dương.

Khi chúng ta đang làm việc với các ma trận cột-ngẫu nhiên dương, nó có thể tìm thấy một vectơ riêng $v$ liên quan đến giá trị riêng $z= 1$ mà tất cả các phần tử của nó là dương. Do đó $A.v = v$ và $v$ có mọi phần tử đều dương.



Định lý 6: Nếu $A$ là một cột ngẫu nhiên ma trận dương, khi đó có duy nhất một vectơ riêng tương ứng với các giá trị riêng $z = 1$ sao cho vectơ đó chỉ có 1 phần tử dương và tổng các phần tử của nó bằng 1.


1) Xem cách đăng bài tại đây
2) Học gõ công thức toán tại: http://diendantoanho...oạn-thảo-latex/
3) Xin đừng đặt tiêu đề gây nhiễu: "Một bài hay", "... đây", "giúp tớ với", "cần gấp", ...
4) Ghé thăm tôi tại 
http://Chúlùnthứ8.vn

5) Xin đừng hỏi bài hay nhờ tôi giải toán. Tôi cực gà.


#3
E. Galois

E. Galois

    Chú lùn thứ 8

  • Quản lý Toán Phổ thông
  • 3861 Bài viết
Một đồ thị là một đối tượng bao gồm một tập hợp không rỗng các đỉnh và tập hợp các cạnh. Khi làm việc với các ví dụ thực tế của đồ thị, đôi khi chúng ta xem chúng như các mạng. Các đỉnh thường được gọi là các nút hoặc các điểm, trong khi cạnh được gọi là các liên kết (links) hoặc dòng (lines). Tập hợp các cạnh có thể rỗng, trong trường hợp này đồ thị là một tập hợp các điểm.

Ví dụ 1: Một ví dụ đơn giản của một đồ thị với các đỉnh $1, 2, 3, 4$ và các cạnh từ đỉnh $1$ đến $2$ đỉnh, đỉnh $3$ đến đỉnh $2;4$, và đỉnh $4$ đến đỉnh $1$.

Hình đã gửi

Hình đã gửi

Trong bài giảng này, chúng ta sẽ chỉ làm việc với đồ thị có hướng và các ví dụ thực tế của chúng (đồ thị Internet), nhưng đối với các kiểu đồ thị khác, bạn hãy tham khảo trang web của Câu lạc bộ Toán Explorer. Ví dụ trung tâm trong mô-đun này là đồ thị web, trong đó các trang web được đại diện là các đỉnh và các liên kết giữa họ được đại diện là các cạnh. Một ví dụ của đồ thị như là một đồ thị con của đồ thị BGP web (Gateway Protocol), bao gồm các bộ định tuyến Internet lớn. Nó có khoảng 6.400 đỉnh và 13.000 cạnh và nó được nêu ra bởi Ross Richardson và nhắc lại bởi Graham Fan Chung.

Hình đã gửi

Mặc dù đồ thị Internet là rất lớn, có số đỉnh theo thứ tự khoảng 30 (hoặc nhiều hơn), tất cả các đồ thị trong mô-đun này được coi là hữu hạn (hữu hạn số lượng đỉnh và các cạnh).

Chúng ta nói rằng hai đỉnh $i$ và $j$ của một đồ thị có hướng là nối liền hoặc lân cận nếu có một cạnh từ $i$ tới $j$ hoặc từ $j$ và $i$. Nếu một cạnh như vậy tồn tại thì $i$ và $j$ là các thiết bị đầu cuối của nó. Nếu có một cạnh từ $i$ đến $j$ thì $i$ thường được gọi là đuôi, trong khi $j$ được gọi là đầu. Trong Ví dụ 1, đỉnh 1 và 2 là nối liền bởi vì có một cạnh 1-2, trong khi đỉnh 1 và 3 không được nối liền . Tuy nhiên, không có cạnh từ đỉnh 2 tới đỉnh 1. Chú ý rằng có thể có không nhiều hơn hai cạnh giữa hai đỉnh bất kỳ. Có một mối quan hệ mạnh mẽ giữa đồ thị và ma trận, trước đây được giới thiệu trong Bài giảng 1. Giả sử chúng ta đang đưa ra một đồ thị có hướng $n$ đỉnh. Sau đó, chúng ta xây dựng một ma trận $A$ cấp $n \times n$ gọi là ma trận liên kết liên quan đến nó như sau: nếu có một cạnh từ đỉnh $i$ đến đỉnh $j$, thì ta đặt số 1 vào vị trí vào hàng $i$, cột $j$ của ma trận.

Ví dụ 2: ma trận liên kết của đồ thị trong Ví dụ 1:
$$A=\begin{bmatrix} 0&1&0&0\\ 0&0&0&0\\ 0&1&0&1\\ 1&0&0&0\end{bmatrix}$$

Nếu có thể đi từ đỉnh $i$ đến đỉnh $j$ dọc theo các cạnh của đồ thị thì chúng ta nói rằng có một đường dẫn từ $i$ tới $j$. Nếu chúng ta đi trên $k$ cạnh, thì đường dẫn có chiều dài $k$. Đối với mỗi ma trận, chúng ta biểu thị $A^k$ là ma trận thu được bằng cách nhân $A$ với chính nó $k$ lần. Các phần tử trên hàng $i$, cột $j$ của $A^2=A.A$ tương ứng với số lượng các đường dẫn có độ dài 2 từ đỉnh $i$ đến đỉnh $j$ trong đồ thị. Ví dụ 2, ta có bình phương ma trận liên kết.

$$A^2=\begin{bmatrix}0 &1 &0 &0 \\0 &0 &0 &0 \\0 &1 & 0 &1 \\1 &0 &0 &0\end{bmatrix}.\begin{bmatrix}0 &1 &0 &0 \\0 &0 &0 &0 \\0 &1 & 0 &1 \\1 &0 &0 &0\end{bmatrix}=\begin{bmatrix}0&0 &0 &0 \\0 &0 &0 &0 \\1 &0 &0 &0 \\0& 1 &0 &0 \end{bmatrix}$$

Điều này có nghĩa rằng có một con đường từ đỉnh 4 đến đỉnh 2, bởi vì các phần tử ở vào hàng thứ hai và cột thứ hai là 1. Tương tự như vậy, có một con đường 3-1, là một trong những có thể dễ dàng nhìn thấy từ Ví dụ 1.

Định lý 1: Cho một đồ thị có hướng và $k$ là số nguyên dương. Khi đó, số hướng đi từ đỉnh $i$ đến đỉnh $j$ có chiều dài k là phần tử trên hàng $i$ và cột $j$ của ma trận $A^k$, $A$ là ma trận liên kết.

Nói chung, một ma trận được gọi là nguyên thủy nếu có một số nguyên dương $k$ sao cho $A^k$ là một ma trận dương. Một đồ thị được gọi là kết nối nếu với hai đỉnh bất kì $i$ và $j$có một đường dẫn hoặc từ $i$ tới $j$ hoặc từ $j$ tới $i$. Mặt khác, một đồ thị được gọi là kết nối mạnh, nếu bắt đầu từ đỉnh $i$ bất kỳ, ta có thể đến được đỉnh $j$ bất kỳ khác $i$ bằng cách đi trên các cạnh của nó. Trong thuật ngữ các ma trận, điều này có nghĩa rằng nếu tồn tại một số nguyên dương $k$ sao cho ma trận $B=I+A+A^2+A^3+...+A^k$ dương, khi đó đồ thị là đồ thị kết nối mạnh. Chúng ta thêm ma trận đơn vị $I$ để chỉ các cạnh từ một đỉnh đến chính nó. Nói cách khác, nếu tồn tại ít nhất một đường dẫn từ đỉnh $i$ đến đỉnh $j$ có độ dài k, thì ta có thể đi từ đỉnh $i$ đến đỉnh $j$. Do đó, nếu ma trận B có một phần tử dương trên hàng $i$ và cột $j$, thì có thể đi đến đỉnh $j$ bắt đầu từ đỉnh $i$. Nếu điều này xảy ra cho tất cả các đỉnh của đồ thị thì đồ thị là đồ thị kết nối mạnh.

Dễ thấy rằng đồ thị trong Ví dụ 1 được kết nối, nhưng không kết nối mạnh vì không có cạnh từ đỉnh 1 đến đỉnh 3. Đối với các ma trận trong Ví dụ 2, chúng ta nhận thấy rằng $A^4$ là một ma trận chỉ có số không, và vì thế với mọi $k \geq 4$, $A^k$ sẽ là một ma trận đầy với số không. Do đó cho bất kỳ $k \geq 4$, ma trận $B=I+A+A^2+A^3+...+A^k$ là:

$$\small B=\begin{bmatrix}1 & 0 & 0 &0 \\0 & 1 & 0 & 0\\0 & 0 & 1 & 0\\0& 0 & 0 & 1\end{bmatrix}+\begin{bmatrix}0 &1 &0 &0 \\0 &0 &0 &0 \\0 &1 & 0 &1 \\1 &0 &0 &0\end{bmatrix}+\begin{bmatrix}0&0 &0 &0 \\0 &0 &0 &0 \\1 &0 &0 &0 \\0& 1 &0 &0\end{bmatrix}+\begin{bmatrix}0&0 &0 &0 \\0 &0 &0 &0 \\0&0 &0 &0 \\1& 0 &0 &0\end{bmatrix}=\begin{bmatrix}1 &1 &0 & 0\\0 &1 & 0 & 0\\1& 1 &1 &1 \\2 &1 &0 &1 \end{bmatrix}$$

Do ma trận $B$ không dương nên đồ thị ở ví dụ 1 không liên kết mạnh như ta đã thấy.

Bài tập 1: Xây dựng ma trận liên kết của đồ thị dưới đây. Đồ thị này có kết nối hay kết nối mạnh không? Có bao nhiêu đường dẫn chiều dài 3 từ đỉnh 3 đến đỉnh 2?
Hình đã gửi
Trong ví dụ trên, chúng ta nhận thấy rằng đối với mỗi đỉnh $i$ có một số cạnh nối tới đỉnh (tức là $i$ là một đầu) và một số của các cạnh mà xuất phát từ đỉnh ($i$ là một đuôi). Vì vậy, ta định nghĩa mật độ nhập (indegree) đỉnh $i$ là số cạnh mà $i$ là một đầu. Tương tự như vậy, mật độ xuất (outdegree) đỉnh $i$ là số cạnh mà $i$ là một đuôi. Ví dụ, đồ thị trong Bài tập 1, mật độ nhập của đỉnh 2 là 2 và các mật độ xuất đỉnh 1 là 1. Ma trận chuyển đổi $A$ liên quan đến một đồ thị có hướng được định nghĩa như sau. Nếu có một cạnh từ $i$ đến $j$ và mật độ xuất của đỉnh $i$ là $d_i$ thì trên cột $i$ và hàng $j$ chúng ta đặt $\frac{1}{d_i}$. Nếu không, chúng ta đặt ở cột $i$, hàng $j$ với số không. Chú ý rằng đầu tiên là với cột, sau đó với hàng. Chúng ta thường viết $\frac{1}{d_i}$. trên các cạnh đi từ đỉnh $i$ đến đỉnh $j$ liền kề, do đó có được một đồ thị trọng lượng. Điều này sẽ trở nên rõ ràng thông qua ví dụ sau đây.

Ví dụ 3: Xem xét đồ thị từ Ví dụ 1 với trọng lượng trên các cạnh của nó như mô tả ở trên.
Hình đã gửi
Khi đó, ma trận chuyển đổi gắn liền với nó là:

$$A=\begin{bmatrix} 0 &0 & 0 & 1\\ 1& 0 & \frac{1}{2} & 0\\ 0& 0 & 0& 0\\ 0& 0 & \frac{1}{2}& 0 \end{bmatrix}$$

Chú ý rằng tổng của các phần tử trên cột đầu tiên là 1. Tương tự cho cột thứ ba và thứ tư. Tổng quát, ta có một định lý.

Định lý 2: Đối với một đồ thị kết nối mạnh, các ma trận chuyển đổi là ma trận cột ngẫu nhiên.

Chúng ta sử dụng các ma trận chuyển đổi mô tả hành vi của một người lướt web ngẫu nhiên trên một đồ thị web. Lướt chọn một trang ngẫu nhiên, sau đó sau liên kết đến các trang web khác miễn là anh ta (cô ta) muốn. Ở mỗi bước, xác suất di chuyển lướt từ đỉnh $i$ đến đỉnh $j$ là số không nếu không có liên kết từ $i$ tới $j$ và là $\frac{1}{d_i}$ nếu có. Nhớ lại rằng $d_i$ là mật độ xuất đỉnh $i$. Ban đầu, xác suất của mỗi trang được lựa chọn như là một điểm khởi đầu là
$$v=\frac{1}{n} . \begin{bmatrix} 1\\1\\ \vdots \\1 \end{bmatrix}$$


Tại bước 1, xác suất của mỗi đỉnh được truy cập sau một cú nhấp chuột là$A.v$. Tại bước 2, xác suất của mỗi đỉnh được truy cập sau khi hai lần nhấp chuột là $A^2.v$ Xác suất của một trang được truy cập tại bước $k$ là $A^k.v$. Nếu ma trận là ma trận nguyên thủy, cột ngẫu nhiên, thì quá trình này hội tụ về một phân phối dừng duy nhất vector $p$ ,
$$p=\begin{bmatrix}p_1\\p_2\\ \vdots \\ p_n \end{bmatrix}$$


Ý nghĩa của phần tử thứ $i$ của $p$ là người lướt thăm trang $i$ tại bất kỳ thời gian nào với xác suất $p_i$.

Bài tập 2: $A$ là một ma trận chuyển đổi kết hợp với một đồ thị và $B$ là một ma trận kích thước $n$ chứa toàn $\frac{1}{n}$. Hãy xem xét $x$ là một số thực dương nhỏ hơn 1. Khi đó, ma trận $C=x.A +(1-x).B$ là cột-ngẫu nhiên. Chứng minh rằng điều này là đúng trong trường hợp đặc biệt là bài tập 1.

1) Xem cách đăng bài tại đây
2) Học gõ công thức toán tại: http://diendantoanho...oạn-thảo-latex/
3) Xin đừng đặt tiêu đề gây nhiễu: "Một bài hay", "... đây", "giúp tớ với", "cần gấp", ...
4) Ghé thăm tôi tại 
http://Chúlùnthứ8.vn

5) Xin đừng hỏi bài hay nhờ tôi giải toán. Tôi cực gà.


#4
E. Galois

E. Galois

    Chú lùn thứ 8

  • Quản lý Toán Phổ thông
  • 3861 Bài viết
Xem Phần I - Phần II

Chúng ta sống trong một kỷ nguyên máy tính. Internet trở thành một phần trong cuộc sống hàng ngày của chúng ta và việc tìm kiếm thông tin chỉ thông qua một cú nhấn chuột. Chỉ cần mở công cụ tìm kiếm ưa thích của bạn, như Google, Altavista, Yahoo, gõ từ khóa, và các công cụ tìm kiếm sẽ hiển thị các trang có liên quan cho tìm kiếm của bạn. Nhưng thực sự một công cụ tìm kiếm làm việc như thế nào?
Hình đã gửi
Thoạt nhìn, có vẻ như hợp lý khi tưởng tượng rằng những gì một công cụ tìm kiếm làm là giữ một chỉ số của tất cả các trang web, và khi một người dùng trong một truy vấn tìm kiếm, công cụ duyệt thông qua chỉ số của nó và đếm số lần xuất hiện của các từ khóa mỗi tập tin web. Chiến thắng dành cho các trang có số lượng xuất hiện các từ khóa cao nhất . Những kết qủa nhận được hiển thị lại cho người sử dụng.

Điều này được sử dụng là hình ảnh chính xác trong đầu những năm 90, khi các công cụ tìm kiếm đầu tiên được sử dụng Hệ thống xếp hạng theo văn bản để quyết định những trang nào là phù hợp nhất với một truy vấn nhất định. Tuy nhiên có một số vấn đề với cách tiếp cận này. Chẳng hạn, một tìm kiếm về một thuật ngữ phổ biến như "Internet". Trang đầu tiên được hiển thị bởi một trong những công cụ tìm kiếm ban đầu được viết bằng tiếng Trung, với sự xuất hiện lặp đi lặp lại từ "Internet" và không chứa các thông tin khác về Internet. Hơn nữa, giả sử chúng ta muốn tìm thấy một số thông tin về Cornell. Chúng tôi gõ vào từ "Cornell" và hy vọng rằng "www.cornell.edu" sẽ là trang web có liên quan đến truy vấn của chúng tôi. Tuy nhiên có thể là hàng triệu trang web bằng cách sử dụng nhiều từ Cornell, và www.cornell.edu có thể không được sử dụng thường xuyên nhất. Giả sử chúng tôi quyết định viết một trang web có chứa từ "Cornell" một tỷ lần và không có gì khác. Thì liệu trang web của chúng tôi có là một trong những trang đầu tiên được hiển thị bằng một công cụ tìm kiếm? Câu trả lời rõ ràng là không. Tuy nhiên, nếu tất cả các công cụ tìm kiếm không có gì khác ngoài đếm các lần xuất hiện của các từ trong truy vấn, điều đó chính là những gì có thể xảy ra.

Hình đã gửi
Tính hữu ích của một công cụ tìm kiếm phụ thuộc vào sự thích hợp của tập hợp các kết quả mà nó mang lại. Tất nhiên có thể có là hàng triệu các trang web bao gồm một từ hoặc cụm từ cụ thể, tuy nhiên một số trong chúng sẽ có liên quan, phổ biến, hoặc có chuyên sâu (có thẩm quyền) hơn những trang khác. Một người sử dụng không có khả năng kiên nhẫn để quét qua tất cả các trang có chứa các từ truy vấn. Một hy vọng các trang có liên quan được hiển thị trong vòng 20-30 trang hàng đầu được trả lại bởi các công cụ tìm kiếm.

Các công cụ tìm kiếm hiện đại sử dụng các phương pháp xếp hạng các kết quả để cung cấp các kết quả "tốt nhất" đầu tiên. Nó phức tạp hơn so với phương pháp xếp hạng theo văn bản đơn giản. Một trong những thuật toán nổi tiếng và có ảnh hưởng nhất cho việc tính toán sự phù hợp của trang web là Thuật toán xếp hạng trang (PageRank algorithm) được sử dụng bởi các công cụ tìm kiếm của Google. Nó được phát minh bởi Larry PageSergey Brin trong khi họ là sinh viên sau đại học tại Stanford, và nó đã trở thành một thương hiệu của Google trong năm 1998. Ý tưởng PageRank đưa ra là, tầm quan trọng của bất kỳ trang web có thể được đánh giá bằng cách nhìn vào các trang liên kết đến nó. Nếu chúng ta tạo ra một trang web $i$ và bao gồm một siêu liên kết đến các trang web $j$, điều này có nghĩa là chúng ta xem xét $j$ quan trọng và có liên quan cho chủ đề của chúng ta. Nếu có rất nhiều các trang liên kết đến $j$, điều này có nghĩa là có niềm tin phổ biến rằng trang $j$ là quan trọng. Nếu mặt khác, $j$ có chỉ có một liên kết đến, nhưng mà đến từ một trang web $k$ có thẩm quyền (như www.google.com, www.cnn.com, www.cornell.edu) chúng ta nói rằng $k$ chuyển giao quyền lực của mình cho $j$ , nói cách khác, $k$ khẳng định rằng $j$ là quan trọng. Cho dù chúng ta nói về trang phổ biến hay trang có thẩm quyền, chúng ta nhắc lại rằng có thể chỉ định một cấp bậc cho mỗi trang web, dựa trên cấp bậc của các trang trỏ đến nó.

Để thực hiện mục tiêu này, chúng ta bắt đầu bằng hình mạng Web như là một đồ thị có hướng, với các đỉnh đại diện bởi các trang web và các cạnh được đại diện bởi các liên kết giữa chúng.

Giả dụ, chúng ta đã có một Internet nhỏ bao gồm các chỉ 4 trang web www.page1.com, www.page2.com, www.page3.com, www.page4.com, sự liên kết giữa chúng được thể hệ như dưới đây:

Hình đã gửi


Chúng ta "chuyển" hình ảnh vào một đồ thị định hướng với 4 đỉnh, mỗi đỉnh cho một trang web. Khi trang web $i$ liên kết đến trang $j$, chúng ta thêm 1 cạnh định hướng giữa đỉnh $i$ và đỉnh $j$ trong đồ thị. Với mục đích là tính toán thứ hạng trang của chúng, chúng ta bỏ qua bất kỳ liên kết điều hướng như Back, Next, chỉ quan tâm đến các kết nối giữa các trang web khác nhau. Ví dụ, Page1 liên kết đến tất cả các trang khác, do vậy, đỉnh 1 trong đồ thị sẽ có cạnh đi cho tất cả các đỉnh khác. Page3 có chỉ có một liên kết đến Page1, do đó đỉnh 3 sẽ có một cạnh đi vào đỉnh 1. Sau khi phân tích mỗi trang web, chúng ta nhận được đồ thị dưới đây:
Hình đã gửi
Trong mô hình của chúng ta, mỗi trang cần chuyển đều tầm quan trọng của nó đến các trang mà nó liên kết đến. Đỉnh 1 có 3 cạnh đi, do đó, nó sẽ chuyển quan trọng của nó với 3 đỉnh khác. Đỉnh 3 đã chỉ có một đi cạnh, do đó, nó sẽ vượt chuyển tất cả tầm quan trọng với đỉnh 1. Nói chung, nếu một đỉnh có $k$ cạnh đi, nó sẽ chuyển tầm quan trọng của nó cho mỗi đỉnh mà nó liên kết đến. Hãy hình dung rõ hơn quá trình bằng cách chỉ định trọng lượng mỗi cạnh.


Hình đã gửi



Hãy để chúng tôi biểu thị bằng ma trận chuyển đổi của đồ thị,

$$A= \begin{bmatrix} 0& 0 & 0 & \frac{1}{2}\\ \frac{1}{3}& 0 & 0 & 0\\ \frac{1}{3}& \frac{1}{2} & 0 & \frac{1}{2}\\ \frac{1}{3}&\frac{1}{2} & 0 &0 \end{bmatrix}$$

Xem xét theo hệ thống động lực :
Giả sử rằng ban đầu mức quan trọng được phân bố đồng đều giữa 4 đỉnh, mỗi đỉnh nhận được $\frac{1}{4}$ nhận được. Ký hiệu $v$ là vector xếp hạng ban đầu, có tất cả các phần tử bằng $\frac{1}{4}$. Mỗi liên kết đến làm tăng tầm quan trọng của một trang web, do đó, tại bước 1, chúng ta cập nhật thứ hạng của mỗi trang bằng cách thêm vào các giá trị hiện tại của tầm quan trọng các liên kết đến. Điều này giống như nhân ma trận $A$ với $v$. Tại bước 1, các vector tầm quan trọng mới là $v_1 = A.v$. Chúng ta có thể lặp lại quá trình, do đó tại bước 2, vector tầm quan trọng cập nhật $v_2 = A.(Av) = A^2.v$. Ta có:
$$v=\begin{bmatrix}0.25\\0.25 \\0.25 \\0.25 \end{bmatrix};A.v=\begin{bmatrix}0.37\\0.08 \\0.33 \\0.20 \end{bmatrix};A^2v=\begin{bmatrix}0.43\\0.12 \\0.27 \\0.16 \end{bmatrix};A^3v=\begin{bmatrix}0.35\\0.14 \\0.29 \\0.20 \end{bmatrix}$$

$$A^4v=\begin{bmatrix}0.39\\0.11 \\0.29 \\0.19 \end{bmatrix};A^5v=\begin{bmatrix}0.39\\0.13 \\0.28 \\0.19 \end{bmatrix};A^6v=\begin{bmatrix}0.38\\0.13 \\0.29 \\0.19 \end{bmatrix};A^7= \begin{bmatrix}0.38\\0.12 \\0.29 \\0.19 \end{bmatrix}=A^8v$$

Chúng ta nhận thấy rằng dãy $v, Av, ..., A^kv$ có xu hướng đến giá trị cân bằng $v^* =\begin{bmatrix}0.38\\0.12 \\0.29 \\0.19 \end{bmatrix}$. Chúng ta gọi đây là vector PageRank của đồ thị web ở trên.

Xem xét theo đại số tuyến tính:

Hãy để chúng tôi biểu thị $x_1, x_2, x_3, x_4$ tương ứng là tầm quan trọng của bốn trang. Phân tích tình hình tại mỗi đỉnh, chúng ta có được hệ:
$$\left\{\begin{matrix} x_1 &= & & & 1.x_3&+\frac{1}{2}x_4 \\ x_2 &= &\frac{1}{3}x_1 \\ x_3 &= &\frac{1}{3}x_1 &+\frac{1}{2}x_2&&+\frac{1}{2}x_4 \\ x_4 &= &\frac{1}{3}x_1 & +\frac{1}{2}x_2 \end{matrix}\right.$$
Điều này là tương đương với yêu cầu giải hệ phương trình.
$$A.\begin{bmatrix}x_1\\x_2 \\ x_3\\ x_4\end{bmatrix}=\begin{bmatrix}x_1\\x_2 \\ x_3\\ x_4 \end{bmatrix}$$
Từ Ví dụ 6 trong Bài giảng 1, chúng ta biết rằng các vector riêng tương ứng các giá trị riêng 1 có dạng.
$$c. \begin{bmatrix}12\\4 \\ 9\\ 6 \end{bmatrix}$$
Khi PageRank chỉ phản ánh tầm quan trọng tương đối của các đỉnh, và khi các vector riêng là bội vô hướng của nhau, chúng ta có thể chọn bất kỳ trong số chúng là vector PageRank. Chọn $v^*$ là vector riêng duy nhất với tổng của tất cả các mục bằng 1. (Đôi khi chúng tôi sẽ xem nó như là vector riêng xác suất tương ứng với các giá trị riêng 1). Vector riêng
$$\frac{1}{31}.\begin{bmatrix}12\\4\\ 9\\ 6\end{bmatrix}\sim \begin{bmatrix}0.38\\0.12 \\ 0.29\\ 0.19\end{bmatrix}$$
là véc tơ PageRank của chúng ta.

Xem xét theo quan điểm Xác suất
Vì tầm quan trọng của một trang web được đo bằng tính phổ biến của nó (nó có bao nhiêu liên kết đến), chúng ta có thể xem trang tầm quan trọng của trang $i$ là xác suất mà một người lướt ngẫu nhiên trên Internet mở ra một trình duyệt bất kỳ trang nào và bắt đầu sau các siêu liên kết, thăm $i$. Chúng ta có thể giải thích trọng lượng chúng ta gán cho các cạnh của đồ thị một cách xác suất: Một người lướt ngẫu nhiên mà hiện tại đang xem trang web 2, có $\frac{1}{2}$ xác suất để đi đến trang 3, và $\frac{1}{2}$ xác suất để đi đến trang 4. Chúng ta có thể mô hình hóa các quá trình như là một bước đi ngẫu nhiên trên đồ thị. Mỗi trang có xác suất bằng $\frac{1}{4}$ được lựa chọn như là một điểm khởi đầu. Vì vậy, phân bố xác suất ban đầu được đưa ra bởi các vector cột
$$\begin{bmatrix}\frac{1}{4}\\ \frac{1}{4} \\ \frac{1}{4} \\ \frac{1}{4}\\\end{bmatrix}$$

Xác suất trang $i$ sẽ được truy cập sau một bước bằng $Ax$, và cứ như vậy. Xác suất trang $i$ sẽ được truy cập sau khi bước $k$ bằng $A^kx$. Dãy $Ax, A^2x, A^3x, ..., A^kx, ...$ hội tụ về một vector xác suấtduy nhất xác suất $v^*$. Khi đó $v^*$ được gọi là phân phối tĩnh (stationarydistribution) và nó sẽ là vector RankPage của $i$. Hơn nữa, mục thứ $i$ trong $v^*$ chỉ đơn giản là xác suất tại từng thời điểm mỗi một người lướt ngẫu nhiên thăm trang $i$. Các tính toán là giống hệt nhau với gì ta đã làm trong việc giải thích các hệ thống động lực, chỉ có ý nghĩa chúng ta gán cho mỗi bước là hơi khác nhau.

Chúng ta đã tính toán Vector PageRank $v^*$ bởi phương pháp khác nhau, chỉ ra rằng trang 1 là trang có nhiều mối liên hệ nhất. Điều này có vẻ đáng ngạc nhiên khi trang 1 có 2 backlinks, trong khi trang 3 có 3 backlinks. Nếu chúng ta nhìn vào đồ thị, chúng ta thấy rằng đỉnh 3 có chỉ có một cạnh đi tới đỉnh 1, do đó, nó chuyển tất cả tầm quan trọng của nó đến đỉnh 1. Điều này tương đương, mỗi một người lướt web sau siêu liên kết thăm trang 3, ông chỉ có thể đi đến trang 1. Kết quả cũng xếp hạng của mỗi trang không phụ thuộc vào tổng các trọng số của các cạnh vào đỉnh. Theo trực giác, tại bước 1, một đỉnh nhận được một phiếu quan trọng từ các đỉnh láng giềng trực tiếp của nó, ở bước 2 từ những hàng xóm của hàng xóm của nó, và cứ như vậy.

Thay đổi biểu đồ web có thể dẫn đến vấn đề nhất định.

Các đỉnh với không có cạnh đi (đỉnh treo)
Hình đã gửi
Chúng tôi lặp đi lặp lại tính toán thứ hạng của 3 trang:
$$v_0=\begin{bmatrix}\frac{1}{3}\\ \frac{1}{3}\\ \frac{1}{3}\end{bmatrix};$$
$$v_1=\begin{bmatrix}0 &0 &0 \\ 0 & 0 &0 \\1 & 1 &0\end{bmatrix}.\begin{bmatrix}\frac{1}{3}\\ \frac{1}{3}\\ \frac{1}{3}\end{bmatrix} = \begin{bmatrix}0\\ 0\\ \frac{2}{3}\end{bmatrix};$$
$$v_2=\begin{bmatrix}0 &0 &0 \\ 0 & 0 &0 \\1 & 1 &0\end{bmatrix}.\begin{bmatrix}0\\ 0\\ \frac{2}{3}\end{bmatrix} = \begin{bmatrix}0\\ 0\\ 0\end{bmatrix}$$
Vì vậy, trong trường hợp này, thứ hạng của mỗi trang là 0. Điều này vô lý, trang 3 có 2 liên kết, vì vậy nó phải có một số tầm quan trọng!

Các thành phần không kết nối
Hình đã gửi
Một người lướt ngẫu nhiên mà bắt đầu trong các thành phần kết nối đầu tiên không có cách nào nhận được trang web 5 từ các đỉnh 1 và 2 (vì không có liên kết tới đỉnh 5). Đại số tuyến tính không giúp gì tốt hơn. Ma trận chuyển đổi cho đồ thị này là
$$A=\begin{bmatrix}0 & 1& 0 &0 &0 \\1 &0 & 0 & 0 &0 \\0 &0 &0 & \frac{1}{2}& \frac{1}{2}\\ 0&0 &\frac{1}{2} & 0 & \frac{1}{2} \\ 0& 0 & \frac{1}{2}&\frac{1}{2} &0\end{bmatrix}$$
Chú ý rằng cả hai vector riêng
$$u=\begin{bmatrix}1\\ 1\\ 0\\ 0\\ 0\end{bmatrix};v=\begin{bmatrix}0\\ 0\\ 1\\ 1\\ 1\end{bmatrix}$$
tương ứng với các giá trị riêng 1, và chúng không phụ thuộc tuyến tính (không phải là kết quả của nhau qua một phép nhân với đại lượng vô hướng). Vì vậy, cả về lý thuyết và trong thực tế, các kết quả của xếp hạng các trang từ các thành phần kết nối đầu tiên liên quan đến những yếu tố từ các thành phần kết nối thứ hai là mơ hồ.

Các trang Web rất không đồng nhất bởi bản chất của nó, và hiển nhiên rất lớn về số lượng, vì vậy chúng ta không mong đợi đồ thị của nó được kết nối. Tương tự như vậy, sẽ có các trang đơn giản mô tả và không chứa các liên kết đi. Điều gì là phải được thực hiện trong trường hợp này? Chúng ta cần 1 cách xếp hạng của một trang web theo ý nghĩa không hoàn toàn, cho bất kỳ đồ thị Web định hướng với các $n$ đỉnh.

Các giải pháp của Page và Brin:

Để khắc phục những vấn đề trên, lấy một số dương $p$ nằm giữa 0 và 1, mà chúng ta gọi là các yếu tố giảm xóc (một giá trị tiêu biểu cho $p$ là 0,15). Xác định các ma trận PageRank (còn được gọi là ma trận Google) của đồ thị bởi $M=(1-p).A+p.B$ với
$$B=\frac{1}{n}\begin{bmatrix}1 & 1 & \cdots & 1\\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1& \cdots & 1\end{bmatrix}$$

Bài toán 1. Chứng minh M vẫn còn là một ma trận ngẫu nhiên cột. Chứng minh rằng M chỉ có một số phần tử dương.

Mô hình ma trận $M$ là mô hình lướt mạng ngẫu nhiên như sau: hầu hết thời gian, một người lướt theo các liên kết từ một trang: từ trang $i$ sẽ thực hiện theo các liên kết đi và di chuyển trên một trong những trang lân cận của $i$. Một tỷ lệ nhỏ hơn, nhưng chiếm tương đối thời gian, anh ta sẽ bỏ trang hiện tại và chọn tùy tiện một trang khác từ trang web và "dịch chuyển" đến đó. Yếu tố giảm xóc $p$ phản ánh khả năng mà người lướt bỏ trang hiện tại và gọi trang mới. Kể từ khi anh ấy có thể dịch chuyển đến bất kỳ trang web, mỗi trang có xác suất được chọn. Điều này giải thích cho cấu trúc của ma trận $B$.

Bài toán 2. Làm lại các tính toán cho PageRank với ma trận chuyển đổi $A$ thay thế bằng ma trận $M$, cho các đồ thị đại diện cho các đỉnh treo, các thành phần không kết nối tương ứng. Khi đó những vấn đề được đề cập trong đó vẫn còn xảy ra nữa không?

Theo trực giác, ma trận $M$ "kết nối" các đồ thị và được thoát khỏi các đỉnh treo. Một đỉnh không có cạnh đi có xác suất để di chuyển đến bất kỳ đỉnh khác. Một cách chặt chẽ, cho ma trận $M$, các định lý sau đây được áp dụng:

Định lý Perron-Frobenius : Nếu $M$ là một ma trận cột ngẫu nhiên dương, khi đó


a) 1 là một giá trị riêng của nhiều vector riêng nhất.


b) 1 là giá trị riêng lớn nhất: tất cả các giá trị riêng khác trong mô đun nhỏ hơn 1.
c) Vector riêng tương ứng với giá trị riêng 1 có tất cả các mục tích cực. Đặc biệt, cho 1 giá trị riêng có tồn tại một vector riêng duy nhất có tổng của các phần tử của nó bằng 1.

Định lý Phương pháp hội tụ lũy thừa: Cho $M$ là ma trận cột ngẫu nhiên dương cấp $n \times n$. Ký hiệu $v^*$ là vector riêng xác suất của nó tương ứng với các giá trị riêng 1, $z$ là các vector cột với tất cả các phần tử bằng $\frac{1}{n}$. Khi đó, dãy $z, Mz, ..., M^kz$ hội tụ tới $v^*$.

Theo quan điểm của tất cả mọi thứ đã thảo luận ở trên, chúng tôi kết luận rằng:

Định lý: Các vector PageRank cho một đồ thị web với ma trận chuyển đổi $A$, và yếu tố giảm xóc $p$, $v^*$ là vector riêng xác suất duy nhất của ma trận $M$, tương ứng với các giá trị riêng 1.

Từ quan điểm toán học, một khi chúng ta có $M$, tính toán các vector riêng tương ứng với giá trị riêng 1, ít nhất là trong lý thuyết, là một nhiệm vụ dễ dàng. Bài giảng 1, chỉ cần giải quyết hệ $Ax = x$. Tuy nhiên, khi $M$ ma trận có kích thước 30.000.000.000 (vì nó đại diện cho hệ thống Web thực sự), thậm chí cả phần mềm toán học như Matlab hoặc Mathematica rõ ràng cũng quá tải.

Một cách thay thế tính toán vector riêng xác suất tương ứng với giá trị riêng 1 được cho bởi phương pháp lũy thừa. Định lý này đảm bảo rằng phương pháp làm việc cho ma trận cột ngẫu nhiên dương. Chúng tôi lý luận rằng các quá trình lặp đi lặp lại tương ứng với tầm quan trọng phân phối qua mạng theo cấu trúc liên kết (Nhớ lại mô hình liên kết ngẫu nhiên). Theo tính toán, rõ ràng là nhiều hơn nữa dễ dàng hơn, bắt đầu từ vector với tất cả các phần tử 1, nhân $x, Mx, ..., M^nx$ cho đến khi hội tụ sau đó nó được tính toán các vector riêng của $M$. Thực tế, trong trường hợp này, một trong những nhu cầu chỉ tính toán các cặp đầu tiên lặp đi lặp lại để có được một xấp xỉ tốt của vector PageRank. Đối với một ma trận ngẫu nhiên, phương pháp lũy thừa nói chung được biết để làm chậm sự hội tụ. Điều đó làm cho nó làm việc nhanh chóng trong trường hợp này tuy nhiên là một thực tế rằng đồ thị web là thưa thớt. Điều này có nghĩa rằng một đỉnh có một số lượng nhỏ các liên kết đi (một vài trăm tốt nhất, mà là cực kỳ nhỏ tương ứng với 30 tỷ đỉnh nó về mặt lý thuyết có thể liên kết). Do đó ma trận chuyển đổi có rất nhiều mục bằng 0.

Chúng tôi kết thúc bài giảng bằng cách đề xuất những vấn đề sau đây:

Bài toán 3. Tính toán vector PageRank của đồ thị dưới đây, xem xét yếu tố giảm xóc $p$ lần lượt là $p = 0; p = 0,15; p = 0,5;p = 1$.
Hình đã gửi
Bài toán 4. Tính toán vector PageRank của mô tả dưới đây, xem xét yếu tố giảm xóc $p = 0,15$. Giải thích kết quả của bạn về mối quan hệ giữa số lượng các liên kết mà mỗi đỉnh có và thứ hạng của nó.
Hình đã gửi



Còn tiếp ...


Dịch từ http://www.math.corn...09/RalucaRemus/.


Mời bạn cùng thảo luận tại http://diendantoanho...showtopic=71568


1) Xem cách đăng bài tại đây
2) Học gõ công thức toán tại: http://diendantoanho...oạn-thảo-latex/
3) Xin đừng đặt tiêu đề gây nhiễu: "Một bài hay", "... đây", "giúp tớ với", "cần gấp", ...
4) Ghé thăm tôi tại 
http://Chúlùnthứ8.vn

5) Xin đừng hỏi bài hay nhờ tôi giải toán. Tôi cực gà.





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh