Khóa luận Link spam với đồ thị web và hạng trang web

à ổn định, và giá trị đó được coi là hạng trang theo phương pháp PageRank[9]. 1.4 Tổng kết chương 1 Xác định và loại bỏ ảnh hưởng của web spam đối với bài toán tính hạng trang là một vấn đề quan trọng trong máy tìm kiếm. Chương này đã giới thiệu về các công nghệ tạo spam chính hiện nay, trong đó link spam là kỹ thuật đáng quan tâm vì có ảnh hưởng lớn, trực tiếp đến kết quả tính hạng trang của máy tìm kiếm. Các chương tiếp theo sẽ trình bày các thuật toán tính hạng trang cơ bản và các phương pháp cải tiến nhằm nâng cao chất lượng tính hạng trang với việc nhận diện và xử lý link spam. Chương 2 Một số phương pháp tính hạng trang cơ bản Để đánh giá độ quan trọng của các trang web, máy tìm kiếm có thể sử dụng các thuật toán tính hạng độc lập yêu cầu người dùng tức là chỉ dựa vào số lượng các liên kết giữa các trang web. Nhiều thuật toán tính hạng trang đang được sử dụng đều tính toán dựa trên liên kết giữa các trang web với nhau, trong đó các thuật toán điển hình là PageRank, HITS [6, 9]. Kết quả nghiên cứu của chúng tôi nhằm tăng tốc tính hạng trang và cài đặt vào máy tìm kiếm cũng được trình bày [2, 12]. 2.1 Phương pháp PageRank 2.1.1 Phương pháp Đây là một trong các phương pháp tính hạng đầu tiên dựa vào mối liên kết giữa các trang. Page và các đồng tác giả [9] đã đưa ra ý tưởng: độ quang trọng của một trang chịu ảnh hưởng của độ quan trọng từ các trang liên kết đến nó. Và công thức tính PageRank cho một trang u, gọi là piu được tính như sau: piu = ∑ i∈BI(i) pii Ni (2.1) Với BI(i) là tập hợp các trang có liên kết đến trang i. 2.1. PHƯƠNG PHÁP PAGERANK 14 Biểu diễn đồ thị Web bởi ma trận chuyển P , khi đó phương trình (2.1) được viết lại dưới dạng ma trận: pi = piP (2.2) Trong đó: pi = (pi1, pi2, . . . pin) là véctơ hạng các trang web, với thành phần pii là hạng của trang i. Từ (2.2) cho thấy véctơ hạng trang pi chính là véctơ riêng của ma trận chuyển P tương ứng với giá trị riêng λ = 1. Do tính chất của chuỗi Markov, để tính véctơ riêng của P thuật toán giả thiết rằng đồ thị trang Web là liên thông, tức với cặp hai trang Web i, j bất kì luôn có đường đi từ i tới j và ngược lại. Tuy nhiên thực tế trên World Wide Web (WWW) vẫn tồn tại không ít các trang web không có liên kết đến hoặc liên kết ra nên việc giả thiết đồ thị Web liên thông là không hợp lý. Và trong ma trận P vẫn tồn tại hàng chỉ toàn số 0, nên không tồn tại một phân phối xác suất dừng ổn định của P hay chính là véctơ hạng trang. Vậy cần phải biến đổi ma trận P thành P ′ cho phù hợp. Định nghĩa véctơ v, được chuẩn hóa ‖ v ‖= 1, xác định xác suất phân phối với vi là xác suất trang web i được gọi đến ở lần duyệt web đầu tiên. Véctơ v có vai trò trong việc hướng kết quả PageRank theo chủ đề, lĩnh vực mong muốn. Khi không xét đến ngữ cảnh đó có thể chọn vi = 1 n với ∀i = 1, 2..n . Gọi d là véctơ n× 1 xác định các dangling nút: di = { 1 nếuN(i) = 0 0 ngược lại Ma trận P ′ được xác định: P ′ = P + dv (2.3) Khi thay đổi ma trận P như vậy tức thêm các liên kết ảo từ các dangling nút tới tất cả các nút khác trong đồ thị Web theo phân phối xác suất v. Điều đó giúp tránh việc khi duyệt các trang không có liên kết ra sẽ không duyệt tiếp được. Để đảm bảo phân phối dừng ổn định (duy nhất), chuỗi Markov tương ứng với quá trình duyệt Web của người dùng cần có tính chất ergodic, tức từ một trang 2.1. PHƯƠNG PHÁP PAGERANK 15 web người dùng có thể chuyển tới một trang bất kì khác. Do vậy ma trận Markov P˜ được xác định như sau: P˜ = αP ′ + (1− α) J (2.4) Với: J = [1]n×1 v α: là hệ số hãm Qua thực nghiệm, α thường được chọn giá trị 0.85. Với ý nghĩa, tại mỗi bước duyệt Web người dùng có thể chuyển tới một trang trong các liên kết ra từ trang hiện tại với xác suất α và chuyển tới các trang khác trong đồ thị Web với xác suất (1− α) theo phân phối v. Khi đó, thay vì tính vector riêng của ma trận P ta tính vector riêng pi của ma trận P˜ : pi = piP˜ (2.5) Theo tính chất của chuỗi Markov, tổng các thành phần của véctơ pi bằng 1: n∑ i=1 pii = 1 Véctơ hạng trang được tính toán dựa theo liên kết, hạng của một trang web phụ thuộc giá trị hạng của các trang liên kết đến, nên việc tính hạng có thể dẫn tới vòng lặp vô hạn. Tuy nhiên với công thức 2.5, véctơ hạng trang có thể được tính một cách đơn giản đó là tính véctơ riêng của ma trận P˜ . Có nhiều phương pháp tính véctơ riêng của ma trận nhưng với ma trận rất lớn của đồ thị các trang web thì không phải phương pháp nào cũng phù hợp. Phần sau sẽ giới thiệu phương pháp lặp tính véctơ riêng của ma trận, tính hạng 2.1.2 Tính hạng trang dựa vào tính chất hội tụ Page và Brin [9] đã sử dụng phương pháp lặp để tính hạng trang và qua thực nghiệm họ đưa ra đồ thị hình 2.1 biểu diễn mối quan hệ giữa bước lặp và độ sai lệch giữa hai vòng lặp liên tiếp. Từ đồ thị, các tác giả thấy độ sai khác giá trị hạng trang giữa hai vòng lặp liên tiếp giảm tuyến tính theo hàm log n, và tốc độ hội tụ khá nhanh sau khoảng 50 vòng lặp. Phương pháp tính hạng bằng cách thực hiện các vòng lặp, và từ tính hội 2.1. PHƯƠNG PHÁP PAGERANK 16 Hình 2.1: Tốc độ hội tụ Thuật toán 1 Tính PageRank theo phương pháp lặp 1: i← 0 2: pi[0] ← v 3: repeat 4: i← i + 1 5: pi[i] ← αP Tpi[i−1] + (1− α)v 6: until ‖ pi[i] − pi[i−1] ‖<  7: pi = pi[i] 2.1. PHƯƠNG PHÁP PAGERANK 17 tụ xác định ngưỡng , là sai số chấp nhật được của giá trị hạng trang, làm điều kiện dừng (xem thuật toán 1). Phương pháp PageRank khá tốt, được áp dụng trong rất nhiều máy tìm kiếm trên Internet. Nhưng do dựa trên vòng lặp, trong khi đồ thị Web có kích thước rất lớn (khoảng 11,5 tỉ trang web)1 nên thời gian tính toán có thể lên tới nhiều ngày. Điều này ảnh hưởng đến chất lượng của máy tìm kiếm. Do vậy, Sepandar Kamvar và các đồng tác giả [?] đã đưa ra ý tưởng cải tiến để tăng tốc độ tính toán, gọi là phương pháp Modified Adaptive PageRank hay MAP. Và chúng tôi [1] đã tiến hành thử nghiệm, đưa ra những đánh giá khá tốt về phương pháp này. Qua thực nghiệm tính hạng, các tác giả nhận thấy tốc độ hội tụ của các trang là không giống nhau. Do đó có thể giảm bớt tính toán, tận dụng những trang hội tụ trước bằng cách không tính lại hạng cho các trang đó ở các vòng lặp tiếp sau. Giả sử tại vòng lặp thứ k, có các tập hợp C các trang có hạng hội tụ theo  và N là tập các trang có hạng chưa hội tụ. Sắp xếp lại ma trận P và véc tơ pi ta có: pi[k] = (pi [k] N pi [k] C )và P = ( PNN PNC PCN PCC ) Trong đó: PNN : là ma trận kề của các trang chưa hội tụ có liên kết đến các trang chưa hội tụ. PNC : là ma trận kề của các trang chưa hội tụ có liên kết đến các trang đã hội tụ. PCN : là ma trận kề của các trang đã hội tụ có liên kết đến các trang chưa hội tụ. PCC : là ma trận kề của các trang đã hội tụ có liên kết đến các trang đã hội tụ. Vì piC đã hội tụ nên ở vòng lặp thứ k không cần tính lại, ta chỉ tính thành phần chưa hội tụ: pi (k+1) N = PNNpi (k) N + PCNpi (k) C Với việc biến đổi ma trận với độ hội tụ của các trang như vậy, quá trình tính toán đã thực sự cải thiện đáng kể. 1Đánh giá của Google 2.2. PHƯƠNG PHÁP HITS 18 2.1.3 Đánh giá PageRank là một phương pháp tính hạng khá tốt và quá trình tính toán độc lập với người dùng. Do vậy quá trình tính toán được thực hiện ngoại tuyến (offline) nên không ảnh hưởng đến tốc độ tìm kiếm. Tuy nhiên, vì thuật toán PageRank không quan tâm đến nội dung của trang web mà chỉ dựa vào các liên kết giữa các trang web, cụ thể là số lượng lên kết đến mỗi trang. Do đó, với sự ra đời của các công nghệ spam thì giá trị hạng trang sử dụng phương pháp PageRank không còn chính xác. 2.2 Phương pháp HITS Phương pháp HITS, do Kleinberg đưa ra [6], tính hạng của một trang web không chỉ dựa trên một giá trị độ quan trọng như PageRank mà nỗi trang web được xác định hai trọng số khác nhau: authority và hub. Thuật toán đưa ra dựa trên ý tưởng một trang có giá trị hub tốt là trang mà có nhiều liên kết ra, và một trang có authority tốt là trang được nhiều trang liên kết tới (hình 2.2). Trong đó các trọng số hub và authority có quan hệ qua lại với nhau: một trang có giá trị hub tốt hơn nếu trỏ tới nhiều trang có authority tốt, và những trang được càng nhiều trang hub tốt trỏ tới thì càng có giá trị authority tốt hơn. Hình 2.2: Mô tả tính chất authority và hub 2.2.1 Thuật toán Thuật toán chỉ làm việc trên một tập nhỏ các trang web, gọi là đồ thị con, chứ không phải toàn bộ đồ thị Web. Và tùy thuộc vào câu truy vấn của người dùng tức phương pháp tính này không hoàn toàn độc lập người dùng, với mỗi truy vấn 2.2. PHƯƠNG PHÁP HITS 19 Hình 2.3: Mở rộng tập cơ sở T từ tập nhân S khác nhau công việc tính toán phải được thực hiện lại. Tuy nhiên câu truy vấn chỉ có vai trò trong việc tạo đồ thị con chứ không ảnh hưởng tới phương pháp tính toán. Vì vậy trước tiên phải xây dựng đồ thị con các trang tùy theo truy vấn và sau đó dự vào liên kết giữa các trang trong đồ thị để xác định các giá trị authority và hub của các trang đến khi hai giá trị đó hội tụ (bằng nhau). • Tạo đồ thị con hay còn gọi là tập cơ sở S: từ tập nhân gồm các trang chứa, liên quan nhiều đến truy vấn, dựa vào các liên kết đến và liên kết ra của các trang trong tập nhân đó để mở rộng đồ thị. Việc mở rộng dừng lại khi đồ thị con đã đủ lớn hoặc đã loang hết tất cả các trang có liên kết đến, hoặc được liên kết ra từ tập nhân. Việc tìm tập nhân liên quan đến truy vấn có thể xác định dựa vào kết quả tìm kiếm của các máy tìm kiếm khác như Google: tập nhân được lấy từ các trang đầu tiên có thể là 10 địa chỉ trang web đầu tiên được trả về tương ứng với truy vấn. Hoặc là các trang có địa chỉ chứa nội dung truy vấn, ví dụ với truy vấn “java” thì trang chủ là Các trang web trong đồ thị con S cũng được đánh chỉ số từ 1 đến n và đồ thị được biểu diễn bởi ma trận kề A. • Tính giá trị authority và hub của các trang trong tập S. Các trọng số au- thority ai và hub hi của mỗi trang web được khởi tạo bằng 1 và sau đó sẽ được tính dựa theo công thức: ai = ∑ j∈B(i) hj và hi = ∑ j∈N(i) aj (2.6) 2.2. PHƯƠNG PHÁP HITS 20 Biểu diễn theo ma trận ta có: ~a = AT~h và ~h = A~a (2.7) Trong đó: ~a = (a1, a2, . . . an), ~h = (h1, h2, . . . hn) lần lượt là véc tơ trọng số authority, hub của các trang trong tập S. Từ 2.7 biến đổi ta được: ~a = AAT~a và ~h = ATA~h Vậy cũng tương tự như phương pháp PageRank, véc tơ a, h lần lượt là véc tơ riêng của các ma trận AAT và ATA. Do vậy tương tự phương pháp tính PageRank, có thể áp dụng tính chất hội tụ để tính véc tơ a, h. Véc tơ a, h thường được chuẩn Thuật toán 2 Tính HITS theo phương pháp lặp 1: a← (1, 1 . . . 1) 2: h← (1, 1 . . . 1) 3: k ← 0 4: repeat 5: k ← k + 1 6: for i = 1 to n do 7: a [k] i = ∑ j∈B(i) h [k−1] j 8: h [k] i = ∑ j∈N(i) a [k−1] j 9: end for 10: until ‖ a[k] − a[k−1] ‖<  11: a = a[k] 12: h = h[k] hóa: ∑ i a = ∑ i h = 1. Kleinberg [6] đã chỉ ra sự hội tụ của các trọng số authority và hub tức thuật toán thỏa mãn tính dừng nhưng chưa đưa ra được giới hạn số vòng lặp cần tính. Tuy nghiên thực nghiệm đã cho thấy thuật toán nhanh chóng hội tụ. 2.2.2 Đánh giá Thuật toán HITS có phần hướng người dùng do sử dụng thông tin truy vấn để xây dựng tập con S các trang web. Thuật toán đã thể hiện mối quan hệ chặt chẽ giữa các trang chủ (authority) và trang trung tâm (hub). 2.3. PHƯƠNG PHÁP CCP 21 Tuy nhiên thuật toán HITS lại cần tính toán trực tuyến (online), tức nhận được câu truy vấn rồi đồ thị con mới được xây dựng và sau đó các trọng số authority, hub được tính. Điều này làm chậm thời gian trả kết quả về cho người dùng. Nhưng có thể ứng dụng thuật toán HITS trong các phương pháp có xác định link spam sau này nhằm đánh tính độ ảnh hưởng của các trang xấu tới các trang khác khi đã xác định được tập nhân các trang xấu. 2.3 Phương pháp CCP Tuy phương pháp tính hạng trang PageRank không tính hạng trực tuyến nên không trực tiếp ảnh hưởng đến thời gian tìm kiếm của người dùng, nhưng độ trễ do thời gian tính hạng ảnh hưởng đến việc cập nhật thông tin. Như với Google quá trình crawl thực hiện hàng tháng do vậy thông tin về các trang web đặc biệt các liên kết giữa các trang thay đổi và cần tính lại hạng trang. Do đó thời gian tính hạng sẽ ảnh hưởng tới thời gian cập nhật thông tin mới của máy tìm kiếm. Trong thực tế đồ thị Web không liên thông và tồn tại rất nhiều trang web không có liên kết đến hoặc liên kết ra. Do vậy ma trận kề biểu diễn đồ thị Web thường là ma trận thưa. Do vậy với các phương pháp tính hạng trên, dù dựa vào tốc độ hội tụ của các trang nhưng quá trình tính toán trên toàn đồ thị Web vẫn chưa tối ưu. Chúng tôi đã nghiên cứu và đề xuất một phương pháp tính hạng với việc phân tích các thành phần liên thông nhằm giảm bớt công việc tính toán, giảm thời gian tính hạng trang [2, 12]. 2.3.1 Thuật toán Qua khảo sát mô hình Markov, các trạng thái có thể phân thành các lớp khác nhau và trong cùng một lớp các trạng thái có thể chuyển qua nhau. Khái niệm lớp các trạng thái trong mô hình Markov rất gần với khái niệm thành phần liên thông trong lý thuyết đồ thị. Do vậy việc phân lớp hay thành phần liên thông trong đồ thị Web để tính hạng trang là hoàn toàn khả thi. 2.3. PHƯƠNG PHÁP CCP 22 Giả sử đồ thị G có k thành phần liên thông, đồ thị được sắp xếp lại như sau: P =  P1 0 · · · 0 0 P2 · · · 0 ... ... . . . ... 0 0 · · · Pk  (2.8) Với: - Pi là ma trận kề kích thước ni × ni của thành phần liên thông thứ i - ∑k i=1 ni = n Chúng tôi định nghĩa: P˜i = αPi + (1− α) ni Ji i = 1, k (2.9) Với: Ji là ma trận J của thành phần liên thông i kích thước ni × ni Khi đó, véc tơ riêng ứng với từng khối ma trận Pi, i = 1, k: pii = piiP˜i (2.10) Và véc tơ hạng trang ˜ được tính: ˜ = (n1 n pi1, n2 n pi2, . . . , nk n pik ) (2.11) Trong [12] chúng tôi đã chứng minh ˜ chính là véc tơ riêng của ma trận P˜ . Do vậy˜ là véc tơ hạng của các trang web. Mỗi thành phần liên thông gọi là một khối. Nhằm nâng cao hiệu quả tính toán, chúng tôi đề xuất đặt giới hạn về độ lớn Max, Min cho các khối. Do vậy sau khi phân tách thành phần liên thông, các khối có độ lớn nhỏ hơn giới hạn dưới Min sẽ được gộp lại và các khối có độ lớn vượt quá Max sẽ được chia thành các khối nhỏ hơn có độ lớn phù hợp. Quá trình tính hạng gồm ba bước chính: • Chia đồ thị Web thành các thành phần liên thông (khối) với các ma trận kề tương ứng. • Tính véc tơ riêng PageRank của các trang trong mỗi thành phần liên thông, theo thuật toán PageRank. • Tổ hợp hạng trang cuối cùng theo công thức 2.11. 2.3. PHƯƠNG PHÁP CCP 23 2.3.2 Đánh giá Khi chúng ta sử dụng toàn bộ ma trận P để tính toán véc tơ riêng như trong phương pháp PageRank, thì với phép nhân ma trận thời gian tính toán là O(n2) trong đó n là số trang web. Mà thực tế đồ thị Web có tới hàng tỉ trang. Nhưng khi chúng ta đưa ma trận kề biểu diễn đồ thị về dạng các khối biểu diễn cho từng thành phần liên thông thì thời gian tính toán sẽ giảm đi rất nhiều. Giả sử chúng ta sẽ có k thành phần liên thông, khi đó với mỗi khối thời gian tính toán nhỏ hơn O(n2i max) và tổng thời gian tính toán sẽ nhỏ hơn k×O(n2imax) nhỏ hơn nhiều so với khi sử dụng cả ma trận lớn để tính toán. Đồng thời, việc tìm thành phần liên thông của đồ thị có thể tiến hành dễ dàng với thời gian đa thức O(n+m) với n là số đỉnh và m là số cạnh của đồ thị nên thời gian chi phí với việc tìm kiếm thành phần liên thông là không đáng kể. Như vậy, phương pháp do chúng tôi đề xuất có thời gian tính toán lý thuyết hiệu quả hơn đối với phương pháp PageRank. Hơn nữa, nếu kết hợp phương pháp này với những phương pháp hỗ trợ tính toán như MAP thì thời gian tính toán được giảm đi đáng kể. Sử dụng thành phần liên thông chúng ta có thể làm giảm đi số vòng lặp tính toán do kích thước ma trận giảm nên tốc độ giảm của véc tơ hạng càng nhanh. Ngoài ra với chúng ta còn có thể tiến hành song song hoá quá trình tính hạng. Với phương pháp chia ma trận thành các thành phần theo tiêu chí cùng host cũng làm giảm số vòng lặp nhưng lại được chia làm hai bước tính hạng, mất thời gian tính toán hạng cho khối. Do vậy độ phức tạp tính toán vẫn lớn. Như vậy, phương pháp đề xuất có một số ưu điểm cơ bản sau: - Giảm thời gian tính toán do việc tính lặp trên ma trận cỡ nhỏ. - Tích hợp dễ dàng với các phương pháp hỗ trợ tính toán trên ma trận. - Có thể dễ dàng áp dụng song song hoá cho quá trình tính hạng. Kết quả thực nghiệm khi thi hành đối với máy tìm kiếm Nutch [16] đã được chúng tôi gửi công bố trong [12]. Chương 3 Các phương pháp xác định LinkSpam 3.1 Giới thiệu Các phương pháp tính hạng trang được trình bày trong chương trước là khá tốt nhưng hoàn toàn không đề cập đến vấn đề spam, và coi liên kết giữa các trang thực sự hàm chứa mối quan hệ độ quan trọng. Ngày nay, với sự ra đời của các công nghệ spam link nhằm nâng cao hạng trạng thì các phương pháp đó không còn phù hợp mà cần cải tiến, thực hiện xác định, loại bỏ các link spam để có được đánh giá hạng chính xác hơn. Trong hai năm gần đây có nhiều bài báo tập trung vào việc đưa ra phương pháp xác định link spam. Qua nghiên cứu [3, 4, 5, 8, 14, 13, 15] cho thấy các phương pháp có thể chia thành các hướng tiếp cận: 1. Nhận dạng LinkSpam dựa vào cấu trúc liên kết: Với nhận định các trang web có số liên kết đến và liên kết ra tuân theo luật số lớn và do đó các trang web có trọng số PageRank tuân theo luật số lớn, nhóm của Benezur [3] đã cho rằng mỗi trang web được phân phối trọng số PageRank từ các trang liên kết tới tuân theo luật số lớn. Do đó các phân phối trọng số PageRank không tuân theo luật đó được nhận định là link spam. Ngoài ra, D. Fetterly, M. Manasse, và M. Najork cũng phân tích các mô hình phân phối liên kết trên web để xác định các trang spam. Phương pháp này chỉ thích hợp với những dạng link spam đơn giản với cấu trúc liên kết lớn 3.2. PHƯƠNG PHÁP TRUSTRANK 25 được sinh tự động. Và với sự phát triển của công nghệ spam hiện nay thì các phương pháp đó không hiệu quả. Tạo nhóm các trang có liên kết mạnh với nhau, còn gọi là các trang có cấu kết với nhau, là một phương pháp nâng cao hạng trang rất hiệu quả và thường được sử dụng bởi những người tạo spam. Baoning Wu và Brian D.Davion [4] đã đưa ra một thuật toán hiệu quả để nhận diện nhóm các trang đó và Z. Gyongyi, H. Garcia-Molina [15] cũng đưa ra các cải tiến trong công thức tính hạng trang tùy theo cấu trúc liên kết trong các nhóm đó. Các phương pháp này tập trung vào phân tích các cấu trúc liên kết tức các trang liên kết với nhau như thế nào để quyết định một trang là spam hay không và thay đổi giá trị hạng trang của chúng. 2. Xác định spam bằng cách đánh giá độ tốt của các trang thay vì tìm các trang xấu, và hạng các trang web được phân phối từ hạng của các trang trong tập nhân các trang web tốt cho trước. Nhóm tác giả Z.Gyongyi, H. Garcia-Molina, J. Pedersen [13] đã đưa ra phương pháp này dựa trên quan niệm: các trang tốt thường chỉ liên kết đến các trang tốt, và các trang xấu (spam) thường chỉ được các trang xấu liên kết đến. 3. Ngoài ra, với sự ra đời của các trang web cho phép viết bài phương pháp xác định các link spam hay cụ thể là blog spam do Gilad Mishne, David Carmel và Ronny Lempel [5] đưa ra nhằm xác định các bài viết xấu (comment spam) chứa liên kết tới các trang web có chủ đề không phù hợp với chủ đề của bài viết. Chương này tập trung phân tích hai thuật toán xác định Link Spam quan trọng là phương pháp xác định Link Farm của Baoning Wu và Brian D. Davison [4] và phương pháp xác định các trang tốt của nhóm Z.Gyongyi [13], từ đó đưa ra giải pháp kết hợp hai phương pháp xác định link spam ứng dụng vào máy tìm kiếm. 3.2 Phương pháp TrustRank Thay vì xác định các trang spam tức trang xấu, phương pháp đánh giá độ tốt của các trang web. Do mục đích của phương pháp là chọn ra những trang tốt nhất nên cũng tương đương với việc loại bỏ các trang xấu. Các trang tốt thường chỉ liên kết 3.2. PHƯƠNG PHÁP TRUSTRANK 26 đến các trang tốt và hiếm khi liên kết đến các trang xấu (spam). Đó là ý tưởng để nhóm của Z. Gyongyi đưa ra thuật toán TrustRank [13]. 3.2.1 Nội dung phương pháp Phương pháp không tự động xác định các trang tốt và xấu mà cần có tập nhân các trang tốt được xác định trước, và các trang đó phân phối độ tốt tới các trang khác dựa vào mối liên kết giữa chúng. Do vậy việc đầu tiên là chọn một tập nhân các trang tốt, và gán trọng số về độ tốt trust lớn. Sau đó dựa vào thuật toán tính hạng PageRank để phân phối giá trị trust, tìm các trang tốt khác. Những trang có giá trị trust cao được tin tưởng đó là các trang tốt. Trong thuật toán, việc chọn tập nhân rất quan trọng và có ảnh hưởng quyết định tới độ tin cậy của phương pháp, nên trước tiên cần dựa vào kiến thức chuyên gia (kiến thức của con người) xác định một tập nhỏ các trang tốt, xấu trong đồ thị Web, rồi kết hợp với phương pháp xác định trọng số trust của các trang để lựa chọn những trang tốt có trọng số trust cao nhất đưa vào tập nhân. Thuật toán 3 TrustRank 1: s← SelectSeed(. . .) . Tính giá trị trust của N trang trong toàn đồ thị web 2: σ ← Sort({1, . . . , N}, s) . Sắp xếp các trang theo thứ tự trust giảm dần 3: v = 0N . v là véc tơ các trang tốt ban đầu 4: for i = 1 to L do . Chọn L trang tốt có trust cao nhất vào tập nhân 5: if O(σ(i)) = 1 then . O(p) = 1 xác định trang p là tốt 6: v(σ(i))← 1 7: end if 8: end for 9: v ← v/ | v | . Chuẩn hóa véc tơ v 10: pi ← v 11: for i = 1 to MB do . Tính hạng theo PageRank với MB vòng lặp 12: pi = αB.P.pi + (1− α)v 13: end for Các tác giả đã xác định các trang tốt (có trust cao) là các trang có nhiều liên kết ra. Do vậy để tính trust của các trang, các tác giả sử dụng thuật toán tính PageRank với hệ số hãm α và số vòng lặp M nhưng thay vì sử dụng ma trận 3.2. PHƯƠNG PHÁP TRUSTRANK 27 chuyển P của đồ thị G = (V,E), thuật toán sử dụng ma trận chuyển U của đồ thị G′ = (V,E ′). Trong đó: mỗi (p, q) ∈ E có (q, p) ∈ E ′ và ngược lại, hay U chính là ma trận chuyển ngược của P . Thuật toán 4 Tính trust hay PageRank ngược 1: function SelectSeed(. . . ) 2: s← 1N . N là số trang trong đồ thị Web 3: for i = 1 to M do . Tính hạng theo PageRank với M vòng lặp 4: s = α.U.s + (1− α). 1 N .1N 5: end for 6: return s 7: end function Thuật toán TrustRank sử dụng phương pháp tính hạng PageRank nguyên thủy để phân phối hạng từ các trang tốt trong tập nhân tới các trang khác. Tuy nhiên các tác giả cũng đưa ý tưởng về cách phân phối giá trị trust giảm dần theo khoảng cách (bước liên kết) từ các trang nhân với trang được liên kết tới, thay vì phương pháp phân phối đều như PageRank. Hình 3.1: Phương pháp phân phối giảm dần Hình 3.1 mô phỏng việc phân phối giá trị trust từ trang 1 tới trang 2 với giá trị β < 1, và từ đó giá trị trust do trang 2 phân phối cho trang 3 là β.β. Nếu có liên kết từ trang 1 tới trang 3 thì giá trị trust mà 3 nhận được sẽ được lấy trung bình: (β + β.β)/2. Hình 3.2 mô phỏng phương pháp phân phối đều giá trị trust, tương tự phương pháp tính PageRank nguyên thủy. Hơn nữa, có thể kết hợp cả hai cách trên để phân phối giá trị trust, ví dụ trang 3 trong hình 3.2 có thể nhận giá trị trust là β.(1/2+1/3). Mô phỏng thuật toán với một ví dụ cụ thể (theo ví dụ trong [13]): 3.2. PHƯƠNG PHÁP TRUSTRANK 28 Xét đồ thị web gồm 7 trang web hình 3.3, với các nút để trắng tương ứng với các trang tốt và các nút đen tương ứng với các trang xấu. Ta có véc tơ xác định các trang tốt xấu: O = [1, 1, 1, 1, 0, 0, 0]. Véc tơ trust: s = [0.08, 0.13, 0.08, 0.10, 0.09, 0.06, 0.02]. Sắp xếp trang theo giá trị trust giảm dần: σ = [2, 4, 5, 1, 3, 6, 7] Chọn L = 3 khi đó tập nhân gồm các trang {2, 4, 5 } nhưng trong đó trang 5 không phải trang tốt do thông tin ban đầu O [5] = 0. Nên có véc tơ v sau khi chuẩn hóa: v = [ 0, 1 2 , 0, 1 2 , 0, 0, 0, 0 ] Chọn hệ số hãm αB = 0.85 và số vòng lặp MB = 20, thuật toán TrustRank trả về giá trị hạng các trang: pi = [0, 0.18, 0.12, 0.15, 0.13, 0.05, 0.05] Ở đây, trang 1 là trang tốt nhưng có giá trị hạng bằng 0 là do trang 1 chỉ có liên kết ra nên không được phân phối giá trị trust từ các trang nhân. Trong khi đó Hình 3.2: Phương pháp chia đều giá trị trust Hình 3.3: Đồ thị gồm 7 trang web đã được đánh dấu trang tốt, xấu 3.2. PHƯƠNG PHÁP TRUSTRANK 29 Hình 3.4: Biểu đồ kết quả thử nghiệm TrustRank [13] trang 5 là trang xấu lại có hạng cao do có một liên kết trực tiếp từ trang tốt 4 trong tập nhân tới nó. Đây cũng chính là mặt hạn chế của phương pháp TrustRank. 3.2.2 Đánh giá phương pháp Phương pháp TrustRank đã nâng cao hạng của nhiều trang tốt và đồng thời do đó đã giảm hạng của các trang xấu như biểu đồ hình 3.4. Tuy nhiên khi xác định trang tốt thuật toán vẫn còn nhiều hạn chế, như ví dụ ở phần trước đã dẫn chứng hai lỗi điển hình của phương pháp. Vấn đề cốt lõi của phương pháp nằm ở quá trình lựa chọn tập nhân các trang tốt. Trong khi việc chọn tập nhân tốt với số lượng không quá lớn nhưng phải bao phủ được không gian web là vấn đề không đơn giản. Đồng thời phương pháp cần thông tin kiến