一種基于網(wǎng)頁質(zhì)量的PageRank算法改進分析

趙亞娟　閆娜

摘要：互聯(lián)網(wǎng)信息的海量性一方面帶給人們無窮的信息，另一方面也給人們的信息獲取工作帶來一定的困難。因而能夠快捷高效地提供高質(zhì)量的查詢結(jié)果的互聯(lián)網(wǎng)搜索引擎將受到大眾的青睞。在網(wǎng)頁搜索中，PageRank和hits是重要的基于鏈接的排序算法，在百度、谷歌等商業(yè)引擎中使用廣泛。但在PageRank算法中也極存在一些問題，導致其容易受垃圾網(wǎng)頁的攻擊，不利于人們高質(zhì)量地從互聯(lián)網(wǎng)上獲取信息，因此，有必要對PageRank算法進行改進，從而改善網(wǎng)頁質(zhì)量，提高信息獲取的高效準確性。該文基于這樣的背景對PageRank算法改進進行分析，以更好地實現(xiàn)信息的有效流通，讓高質(zhì)量的網(wǎng)頁得到更多關(guān)注。

關(guān)鍵詞：PageRank算法改進；網(wǎng)頁質(zhì)量

中圖分類號：TP37 文獻標識碼：A 文章編號：1009-3044（2014）27-6365-02

Abstract： The huge amount of Internet information on one hand brings people endless information， on the other hand also give people access to information work to bring certain difficulty. The Internet search engine so it can efficiently provide high quality results will be favored by the public. In Webpage search， PageRank and hits are important link based ranking algorithms， widely used in Baidu， Google commercial engine. But in the PageRank algorithm also has some problems， resulting in the waste Webpage vulnerable to attack， is not conducive to high quality people to obtain information from the Internet， therefore， it is necessary to improve PageRank algorithm， so as to improve the quality of Webpage， improve the efficiency and accuracy of information acquisition. This paper analyzes the improvement of PageRank algorithm based on this background， the effective circulation to achieve better information， make high quality Webpage get more attention.

Key words： improved PageRank algorithm Webpage quality

1 PageRank算法原理

PageRank算法是一種針對鏈接進行分析并計算網(wǎng)頁在互聯(lián)網(wǎng)中的等級和重要性的算法，網(wǎng)頁等級越高、重要性越大則其在搜索引擎中的排位就會越靠前，在信息搜索時被訪問的次數(shù)就越多。PageRank算法的使用基于兩個前提，一個前提指向一個網(wǎng)頁的超鏈接數(shù)量越多，網(wǎng)頁被引用或搜索的次數(shù)越多，表明這個網(wǎng)頁越重要，權(quán)威網(wǎng)頁往往被傳遞和引用的次數(shù)更多。另一個前提是同一鏈接中用戶選擇的隨機沖浪性原理，可以簡單地理解為用戶隨機點擊一個鏈接進入該鏈接所指向的一個網(wǎng)頁，然后從打開的這個網(wǎng)頁中再隨機點擊一個鏈接進入下一個頁面，直到用戶不再點擊進入為止。網(wǎng)頁的重要性是基于其在這種隨機可能性中被選擇的概率，如果它被訪問的次數(shù)越多，尤其是當該網(wǎng)頁被重要的網(wǎng)頁如百度、谷歌等引用，表明該網(wǎng)頁的重要程度越高。換言之，網(wǎng)頁的PageRank值越高，則認為其在互聯(lián)網(wǎng)中越重要，被訪問的次數(shù)就越多。

為了更形象地說明PageRank算法的原理，可以將互聯(lián)網(wǎng)看成一個巨大的有向圖，有向圖中的一個結(jié)點表示一個網(wǎng)頁，連接結(jié)點和結(jié)點之間的線表示網(wǎng)頁間的超鏈接，結(jié)點間的邊是有方向的，既可以表示該網(wǎng)頁中包括的超鏈接又可以表明指向該網(wǎng)頁的超鏈接。如圖1所示，表示互聯(lián)網(wǎng)中一個簡單的網(wǎng)絡結(jié)構(gòu)。A-E表示網(wǎng)頁，它們之間通過超鏈接互相聯(lián)系，箭頭表示超鏈接，有指入和指出的區(qū)別。

2 PageRank算法的現(xiàn)狀分析

PageRank算法對網(wǎng)頁重要性的計算雖具有一定的代表性，但其目前存在的缺點也不斷突顯出來。首先，PageRank算法對新網(wǎng)頁的存在偏見，由其計算公式（2） 可知，一個網(wǎng)頁的重要性是由該網(wǎng)頁的鏈入超鏈接數(shù)決定的，而新的網(wǎng)頁在鏈入數(shù)方面明顯吃虧，其被搜索的可能性降低相反，用戶對新網(wǎng)頁往往抱有好奇。其次，PageRank算法主題偏移。PageRank算法是沒有考慮大多數(shù)用戶訪問網(wǎng)頁所查詢內(nèi)容，忽略了網(wǎng)頁間內(nèi)容的關(guān)聯(lián)度，在現(xiàn)實網(wǎng)絡中又存在許多垃圾網(wǎng)頁，它們指向的內(nèi)容與用戶查詢的內(nèi)容無關(guān)，從而導致用戶在查詢時產(chǎn)生主題的偏移，網(wǎng)頁鏈接與用戶查詢的內(nèi)容及目的性直接相關(guān)，PageRank算法是直接依據(jù)網(wǎng)絡的鏈接結(jié)構(gòu)計算出的PR值來評價網(wǎng)頁的重要性，而實際網(wǎng)絡的重要性與用戶的查詢關(guān)鍵詞不具有依賴性。此外，PageRank算法忽略了不同鏈接的重要程度，PageRank算法對于某一個網(wǎng)頁的鏈出的超鏈接所占的權(quán)重是平均分配的，但是網(wǎng)絡中一部分鏈接具有注釋性，另一些鏈接只是起導航或廣告的作用，它們相當于噪音信息，而PageRank算法計算的只是具有注釋性的鏈接。

3 PageRank算法的改進

針對上述PageRank算法存在的問題，研究PageRank算法的專家學者提出了一些改進算法，如國內(nèi)學者提出的結(jié)合分類、相似度及時間反饋因子的PageRank算法，國外學者提出的主題敏感的PageRank算法等。該文主要從提高網(wǎng)頁質(zhì)量的角度出發(fā)，對PageRank算法進行質(zhì)量衡量值的算法改進。因為當前的網(wǎng)絡中存在大量的垃圾網(wǎng)頁和噪鏈，使網(wǎng)頁質(zhì)量出現(xiàn)明顯的分化，這樣傳統(tǒng)的PageRank算法中平均分配權(quán)重的算法變得不再合適。在后來改進中，雖然通過多次迭代后仍可以得到較為客觀的PR值來反映網(wǎng)頁的質(zhì)量，但是這個過程中需要進行多次的迭代，并且對噪鏈沒有起到有效的過濾作用。

為了解決這些問題，筆者對基于網(wǎng)頁質(zhì)量的PageRank算法進行改進分析。在算法改進中引入了相對質(zhì)量的概念，在迭代中利用每次迭代后所得的網(wǎng)頁質(zhì)量PR值與網(wǎng)頁鏈接結(jié)構(gòu)來計算中該網(wǎng)頁相對質(zhì)量Q（p），并將所得結(jié)果分配到PR值中。相對質(zhì)量作為衡量網(wǎng)頁質(zhì)量的參數(shù)，它用來幫助分配PR值，網(wǎng)頁的排序依然按照PR值來定。

由上述分析可以看出，改進之后的算法利用了每一輪迭代后得到的PR值，這樣網(wǎng)頁高的PR值可以得到更快的累積，最終減少了總的迭代次數(shù)。另外，相對質(zhì)量Q（p）及網(wǎng)頁q分配給p的PR值在迭代過程中都只要計算一次，且它們的計算過程簡單，因此，總體而言，改進后的PageRank算法—相對質(zhì)量算法雖然算法稍微復雜一些，但瑕不掩瑜，對網(wǎng)頁質(zhì)量的PR值計算更準確。

參考文獻：

[1] 喬少杰，彭京，李天瑞，等.基于中心性和PageRank的網(wǎng)頁綜合評分方法[J].西南交通大學學報，2011，46（3）.

[2] 秦拯，張玲，李娜，等.改進的PageRank在Web信息搜集中的應用[J].計算機研究與發(fā)展，2006，43（6）.

[3] ZHANG Yong，YIN Chuan-ye，WU Chong-zheng，等.基于MapReduce的PageRank算法優(yōu)化研究[J].計算機應用研究，2014，31（2）.