PangRank算法綜述研究

題目《PangRank算法綜述》摘要隨著互聯(lián)網(wǎng)的普及與移動端的崛起，人們對信息的需求越來越大。了解實(shí)時新聞，尋求問題的解決方法，獲得學(xué)習(xí)資料等等都需要通過互聯(lián)網(wǎng)，通過搜索引擎來實(shí)現(xiàn)。一個高質(zhì)量的搜索引擎，例如Google，需要快速地將滿足用戶需求的信息反饋給用戶，這就需要一個可以在龐大數(shù)據(jù)庫中快讀篩選并按重要性對滿足要求的信息進(jìn)行排序的搜索算法的支持。PageRank算法正是Google搜索引擎所使用的一個優(yōu)質(zhì)的網(wǎng)頁重要性排序算法。本文介紹了PageRank算法的研究背景及研究意義，給出了算法原理和算法公式，以及該算法存在的問題及已有的改進(jìn)措施，討論了該算法在實(shí)際社會中的應(yīng)用情況，說明該算法在搜索引擎領(lǐng)域的成功性。關(guān)鍵詞：搜索引擎，PageRank，算法，改進(jìn)，技術(shù)與應(yīng)用1緒論在Google出現(xiàn)以前，搜索引擎很原始，搜索速度也遠(yuǎn)遠(yuǎn)不及現(xiàn)在，如今想要查詢什么內(nèi)容直接搜索關(guān)鍵詞就能出來很多條結(jié)果供人參考。蒙特利爾大學(xué)生發(fā)明的Archie可以算是搜索引擎的祖先。他的數(shù)據(jù)庫是由數(shù)百個系統(tǒng)的文件目錄組成，搜索時根據(jù)文件名在數(shù)據(jù)庫中進(jìn)行查找，然后告訴你哪些系統(tǒng)上的目錄包含所需的文件，使用的是FTP協(xié)議。PageRank算法是由Google的創(chuàng)始人LarryPage在斯坦福讀大學(xué)時（1998年）提出，又稱Pr，佩奇排名。該算法主要針對網(wǎng)頁進(jìn)行排名，計算網(wǎng)站的重要性，優(yōu)化搜索引擎的搜索結(jié)果。PR值是表示其重要性的因子。其核心思想就是：如果一個網(wǎng)頁鏈接的數(shù)量很多且質(zhì)量很高，那么該網(wǎng)頁比較重要，對應(yīng)的PageRank值也會比較高。數(shù)量多是指有很多其他網(wǎng)頁鏈接該網(wǎng)頁，質(zhì)量高是指鏈接該網(wǎng)頁的網(wǎng)頁中有PageRank值很高的。但是該算法也存在一定的缺陷，研究者們也針對具體問題對該算法進(jìn)行了改進(jìn)。改進(jìn)后的PageRank算法對用戶能在巨大的數(shù)據(jù)庫中快速地檢索出符合自己需求的有價值的信息方面起著重要的作用。2PageRank算法2.1PageRank的簡單計算代表的是其它節(jié)點(diǎn)（指向a節(jié)點(diǎn)的）PR值代表的是其它節(jié)點(diǎn)（指向a節(jié)點(diǎn)的）出鏈數(shù)代表的是循環(huán)次數(shù)2.2修正的PageRank計算由于存在一些網(wǎng)頁，它的出鏈?zhǔn)撬旧?，因此PR值會逐代累加至1，因此需要進(jìn)行修正。如果一個用戶選擇直接在地址欄輸入URL進(jìn)入下一個網(wǎng)頁，而不是選擇點(diǎn)擊現(xiàn)頁面上其他的網(wǎng)頁鏈接，設(shè)點(diǎn)擊現(xiàn)頁面鏈接的概率為d，那么直接在地址欄輸入URL跳到新網(wǎng)頁的概率是（1-d），d為阻尼系數(shù)，一般為0.85。2.3另一個版本的PageRank計算由于存在一些懸掛網(wǎng)頁，即出鏈為0的網(wǎng)頁，這使得循環(huán)迭代求值時不能收斂。所以，當(dāng)用戶訪問到這些懸掛網(wǎng)頁時，會隨機(jī)跳到任何一個其他頁面，即其他網(wǎng)頁的入鏈包含懸掛網(wǎng)頁，因此在修正公式中加入1/N，N表示互聯(lián)網(wǎng)中所有網(wǎng)頁的數(shù)量。2.4PageRank算法實(shí)例假設(shè)有四個頁面A，B，C，D，它們的鏈接關(guān)系如圖1所示：圖1頁面鏈接關(guān)系初始A入鏈為C，出鏈為D.B入鏈為C，出鏈為D.C入鏈為D，出鏈為A，B，D.D入鏈為A，C，B，出鏈為C.如此反復(fù)多次地進(jìn)行計算，直到PageRank值收斂于某一定值?？梢园l(fā)現(xiàn)D的PageRank值最高，因?yàn)殒溄铀木W(wǎng)頁最多。3存在的問題及改進(jìn)措施存在時間越久的網(wǎng)頁的PageRank值越大。存活時間越久的網(wǎng)站被引用的可能性越高，PR值越大，但是新網(wǎng)頁往往包含更加及時性有效性價值高的信息。當(dāng)一個新的網(wǎng)頁剛被放上網(wǎng)，短時間內(nèi)不會被很多網(wǎng)頁引用，這樣它的PR值較小，根據(jù)算法，當(dāng)用戶通過搜索引擎搜索與該頁面信息相關(guān)的關(guān)鍵詞時，該頁面會排在較靠后的位置，很有可能不會被用戶注意到，這樣就違背了用戶需求，因?yàn)橛脩敉ǔＯ肟吹阶钚孪?。為了讓新網(wǎng)頁能夠快速地被其他網(wǎng)頁鏈接，張玲博士提出了基于時間序列分析的加速估計算法。該算法的基本思想是對基于時間序列URL進(jìn)行線性擬合分析，直線斜率為正說明該URL未來趨勢走向很好，重要性高，將此值作為決定該頁面排名的重要參數(shù)。主題偏移現(xiàn)象。PageRank算法無法判斷網(wǎng)頁中的鏈接和該網(wǎng)頁的主題內(nèi)容是否相關(guān)，這樣用戶可能會搜索到自己不想看到的內(nèi)容。此外，該算法偏重.com結(jié)尾的綜合性的網(wǎng)站，因?yàn)檫@種網(wǎng)站會被更多的網(wǎng)頁鏈接。但是這類網(wǎng)站所涉及的內(nèi)容太廣太雜，多而不專，與搜索的主題匹配性不高。針對這一問題，斯坦福大學(xué)的TaherH.Haceliwala提出了對搜索主題敏感的PageRank算法。該算法的基本思想是根據(jù)ODP對網(wǎng)頁進(jìn)行分類，并根據(jù)每個分類給出一個主題敏感值，計算該分類下的PR值。再根據(jù)用戶搜索的主題和上下文計算網(wǎng)頁的綜合得分，從而計算出網(wǎng)頁的重要性排名，提高了網(wǎng)頁排序結(jié)果的準(zhǔn)確性，返回與用戶搜索主題相關(guān)的網(wǎng)頁，提高了用戶滿意度。平均網(wǎng)頁權(quán)值現(xiàn)象。一個網(wǎng)頁被引用的次數(shù)越高，說明其重要性越高。但是被權(quán)威網(wǎng)頁引用的頁面的重要性肯定比被很多垃圾網(wǎng)站引用的網(wǎng)頁的重要性高。但是PageRank算法將權(quán)值平均分配給各個引用它的鏈接，這種分配方式在一定程度上影響了網(wǎng)頁的重要性排名。4社會應(yīng)用場景4.1微博影響力排名微博是當(dāng)代重要的社交媒體之一。微博具有即時性和便捷性特征。用戶通過微博發(fā)布自己的生活照片，發(fā)布發(fā)生在身邊的典型事件，通過微博和有著相似愛好的人進(jìn)行交流溝通，也通過微博了解一些自己在日常生活中接觸不到的人的生活軌跡。正是由于微博傳遞和接受信息方便快捷，越來越多的人為了吸引眼球博關(guān)注而從事話題操作，經(jīng)常發(fā)布虛假信息，散布謠言，傳播低俗內(nèi)容，從而影響社會和諧安定發(fā)展。因此，對微博上的信息進(jìn)行數(shù)據(jù)分析，找到具有影響力的節(jié)點(diǎn)是非常重要的。PageRank算法就應(yīng)用在獲得微博用戶影響力排名這一領(lǐng)域。微博用戶影響力的計算值為自身影響力和間接影響力之和：.用戶自身影響力指標(biāo)主要有用戶在某一時段內(nèi)發(fā)表的微博總數(shù)，以及每條微博被其他用戶點(diǎn)贊的數(shù)量，被其他用戶轉(zhuǎn)發(fā)的數(shù)量，被其他用戶評論的數(shù)量，用戶是否經(jīng)過官方認(rèn)證也是一個指標(biāo)。就為評論數(shù)、點(diǎn)贊數(shù)與轉(zhuǎn)發(fā)數(shù)之和除以該段時間用戶所發(fā)微博總數(shù)除以該用戶的有效粉絲數(shù)。如果該用戶為認(rèn)證用戶，結(jié)果再加0.5。間接影響力指標(biāo)主要是通過粉絲對其影響力的貢獻(xiàn)值所決定的，即4.2學(xué)術(shù)文獻(xiàn)排名隨著科技的發(fā)展，學(xué)術(shù)領(lǐng)域?qū)φ撐牡囊笤絹碓礁?，各大學(xué)術(shù)網(wǎng)絡(luò)平臺例如谷歌學(xué)術(shù)，IEEE，知網(wǎng)等文獻(xiàn)的數(shù)量海量增長，這些文獻(xiàn)為更多人進(jìn)行科研工作提供了方便。但是，如何在復(fù)雜龐大的快速高效地找到用戶需要的且閱讀價值高的文章和水平高的作者是一項(xiàng)復(fù)雜而困難的工作。PageRank算法就可以應(yīng)用在該領(lǐng)域中。文獻(xiàn)排名的計算公式如下：，N是文獻(xiàn)總數(shù)。這種傳統(tǒng)的PageRank算法忽略了時間因素，發(fā)表越久遠(yuǎn)的論文可能有更多次的引用，對應(yīng)的PR值也就越大。但是在科研領(lǐng)域，更值得我們參考的應(yīng)該的是最新發(fā)表的論文。因此，在文獻(xiàn)排名算法中，使用PageRank迭代計算文獻(xiàn)的PageRank值，根據(jù)作者和所發(fā)表論文之間的關(guān)系矩陣迭代求解文獻(xiàn)和作者的權(quán)威值,同時考慮時間因素的影響。4.3體育賽事團(tuán)體實(shí)力預(yù)測我國在眾多體育賽事中都有著出色成績，但是在一部分賽事中成績也不是很理想。如果在比賽之前可以提前預(yù)測對手的實(shí)力，就會有更加充分的準(zhǔn)備，也不會因?yàn)閷κ帜吧a(chǎn)生心理焦慮。PageRank算法就能應(yīng)用在體育賽事團(tuán)體實(shí)力排名領(lǐng)域。首先要獲得每個團(tuán)體在該比賽中歷史成績，每個團(tuán)體兩兩之間最終比分結(jié)果，每個運(yùn)動員最近n場比賽的平均得分；接著根據(jù)主力隊(duì)員的變動，調(diào)整比分結(jié)果；最后根據(jù)比分結(jié)果構(gòu)造投票貢獻(xiàn)矩陣，計算出團(tuán)體綜合實(shí)力。5總結(jié)與展望Google搜索引擎PageRank技術(shù)無論是在工作，生活還是學(xué)習(xí)方面都有著極為重要的應(yīng)用。雖然該算法本身存在一定的缺陷，但在不斷地改進(jìn)之后，使得搜索結(jié)果更加精確，更能滿足用戶的需求。在今后的研究中，需要更加完善該算法，在計算PR值時充分考慮網(wǎng)頁間的主題相關(guān)性，考慮時間因素對搜索結(jié)果帶來的影響，深入研究網(wǎng)絡(luò)鏈接結(jié)構(gòu)，盡可能快速地將符合用戶需求的準(zhǔn)確性高及時性高的信息反饋給用戶。參考文獻(xiàn)邱苓蕓,王銘,趙衛(wèi)東.PageRank算法改進(jìn)研究[J].軟件導(dǎo)刊,2017(2):74-76.馮振明.Google核心——PageRank算法探討[J].計算機(jī)技術(shù)與發(fā)展,2006,16(7):82-84.BrinS;PageLTheanatomyofalarge-scalehypertextualWebsearchengine1998(1-7)李稚楹,楊武,謝治軍.PageRank算法研究綜述[J].計算機(jī)科學(xué),2011(s1):185-188.白瑩瑩.PageRank算法在學(xué)術(shù)網(wǎng)絡(luò)平臺中