歐賢

摘 要 隨著Internet 技術(shù)的快速普及和迅猛發(fā)展，Web 上信息總量日益膨脹。用戶如何從網(wǎng)頁信息中快速獲取所需信息變得日益重要。本文對(duì)Web結(jié)構(gòu)挖掘算法PageRank 算法進(jìn)行研究學(xué)習(xí)，分析了其兩種算法的基本思想和技術(shù)特點(diǎn)。

關(guān)鍵詞 排序 PageRank算法 隨機(jī)游走

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A

1 PageRank算法概述

PageRank（網(wǎng)頁級(jí)別），2001年9月被授予美國專利，專利人是Google創(chuàng)始人之一拉里·佩奇[1]。它是Google排名運(yùn)算法則（排名公式）的一部分，是Google用于用來標(biāo)識(shí)網(wǎng)頁的等級(jí)/重要性的一種方法，是Google用來衡量一個(gè)網(wǎng)站的好壞的唯一標(biāo)準(zhǔn)。在揉合了諸如Title標(biāo)識(shí)和Keywords標(biāo)識(shí)等所有其它因素之后，Google通過PageRank來調(diào)整結(jié)果，使那些更具“等級(jí)/重要性”的網(wǎng)頁在搜索結(jié)果中另網(wǎng)站排名獲得提升，從而提高搜索結(jié)果的相關(guān)性和質(zhì)量。級(jí)別從0到10級(jí)，10級(jí)為滿分。

2 PageRank算法過程分析

PageRank算法所建立的用戶瀏覽模型被稱為“隨機(jī)游走”（random walk）模型。用戶使用一個(gè)特殊的瀏覽器來瀏覽網(wǎng)頁，這個(gè)瀏覽器沒有地址欄、后退按鈕，即只能順著網(wǎng)頁鏈接瀏覽。同時(shí)提供一個(gè)“隨便逛逛”的功能，可以通過點(diǎn)此按鈕隨機(jī)打開萬維網(wǎng)上的一個(gè)網(wǎng)頁開始瀏覽。那么，網(wǎng)頁A被訪問的概率可以用如下公式計(jì)算得到：

上式右半部分是使用“隨便逛逛”功能訪問到頁面A的概率，而后半部分則是使用超鏈接訪問到頁面A的概率，兩者相加即為訪問到頁面A的總概率大小?？芍?，如果給定參數(shù) ，頁面A的PageRank值事實(shí)上是由鏈接到它的各個(gè)頁面的PageRank值決定的。

3 PageRank算法

PageRank算法要求G中不存在沒有超鏈接的“死胡同”網(wǎng)頁，為解決這一問題，可以采用如下算法：

（4）當(dāng)結(jié)果向量收斂時(shí)，返回（3）繼續(xù)循環(huán)；當(dāng)收斂時(shí)，算法結(jié)束，輸出所計(jì)算出的G中每一個(gè)節(jié)點(diǎn)n的PR（n）的結(jié)果。

4.總結(jié)

可以看出，與第一種算法相比，第二種算法考慮到?jīng)]有超鏈接網(wǎng)頁的情況，對(duì)這部分網(wǎng)頁，“隨機(jī)游走”的瀏覽方式則只能點(diǎn)擊“隨便逛逛”功能進(jìn)行跳轉(zhuǎn)，而任何G中的網(wǎng)頁都可能成為跳轉(zhuǎn)目標(biāo)。事實(shí)上，這相當(dāng)于先在“死胡同”網(wǎng)頁和G中的所有網(wǎng)頁兩兩之間添加了一條虛擬的超鏈接，之后，再在這個(gè)經(jīng)過修改的鏈接關(guān)系圖上進(jìn)行簡(jiǎn)化算法。

參考文獻(xiàn)

[1] 黃德才，戚華春，錢能.基于主題相似度模型的TS2PageRank算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2007（03）.

[2] 盧開澄.計(jì)算機(jī)密碼學(xué)——計(jì)算機(jī)網(wǎng)絡(luò)中的數(shù)據(jù)保密與安全（第3版）[M].清化大學(xué)出版社，2002.

[3] 李凱，赫楓齡，左萬利.PageRank2Pro一種改進(jìn)的網(wǎng)頁排序算法[J].吉林大學(xué)學(xué)報(bào)，2003（4）.