Google搜索引擎的數(shù)學模型及其應用.pdf

《Google搜索引擎的數(shù)學模型及其應用.pdf》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、西南民族大學學報·自然科學版第36卷第3期May.2010___________________________________________________________________JournalofSouthwestUniversityforNationalities?NaturalScienceEdition文章編號:1003-2843(2010)03-0480-07Google搜索引擎的數(shù)學模型及其應用趙國,宋建成(西南民族大學計算機科學與技術學院,四川成都610041)摘要:該文在闡明Google搜索引擎中關鍵的頁面等級算法(PageRank)原理的基礎上

2、,分析了PageRank算法的隨機沖浪模型,并著重討論相應的數(shù)學模型在足球隊排名問題(1993年全國大學生數(shù)學建模競賽B題)中的應用.具體做法是綜合考慮各隊的比賽成績,為每支球隊計算相應的等級分(Rank),然后根據(jù)各隊的等級分高低來確定名次.考慮到競技比賽結果的不確定性,最后建立了等級分的隨機沖浪模型.分析表明等級分排名結果具有良好的參數(shù)穩(wěn)定性,并且可以成功地處理數(shù)據(jù)缺損方面的困難.關鍵詞:搜索引擎;GooglePageRank算法;隨機沖浪模型;足球隊排名問題中圖分類號:O141.4文獻標識碼:A1引言據(jù)統(tǒng)計,在短短20多年的時間里,Internet中產(chǎn)生的信息量相當于

3、人類過去100年產(chǎn)生的信息總量,而且Internet上的信息量正以幾何級數(shù)遞增.搜索引擎已經(jīng)成為人們進行Internet信息資源搜索必不可少的工具.在眾多的搜索引擎中,Google搜索引擎以其雄厚的技術為支撐,憑借其強大的檢索功能和高質量的檢索服務,逐[1]漸脫穎而出.Google搜索引擎是由斯坦福大學SergeyBrin和LawrencePage共同設計的,它是目前功能最強的搜索引擎.通過對80億網(wǎng)頁進行整理,Google可為世界各地的用戶提供所需的搜索結果,而且搜索速度極快,通常不到半秒,每天可提供約3億次查詢服務.圖1Google搜索引擎的工作原理示意圖圖2Inter

4、net網(wǎng)絡的拓撲結構Google的優(yōu)勢在于掌握的信息量以及檢索模型和檢索速度.傳統(tǒng)的搜索引擎在很大程度上取決于文字在網(wǎng)頁上出現(xiàn)的頻率.Google使用PageRank技術檢查整個網(wǎng)絡鏈接結構,并確定哪些網(wǎng)頁重要性最高.然后進行超文本匹配分析(HypertextMatchingAnalysis),以確定哪些網(wǎng)頁與正在執(zhí)行的特定搜索相關.在綜合考慮整體___________________________收稿日期：2010-03-13作者簡介：趙國(1979-),男,碩士,西南民族大學計算機科學與技術學院講師,主要研究方向為金融數(shù)學、數(shù)學模型.基金項目：西南民族大學青年項目._

5、__________________________________________________________________第3期趙國等:Google搜索引擎的數(shù)學模型及其應用481重要性以及與特定查詢的相關性之后,Google可以將最相關最可靠的搜索結果放在最前面.2Google搜索引擎的數(shù)學模型Google擁有多項專利技術,其中PageRank算法是關鍵技術之一,它奠定了Google強大的檢索功能及提供各種特色功能的基礎.雖然Google每天有很多工程師負責全面改進Google系統(tǒng),但是仍把PageRank算法作為[2]所有網(wǎng)絡搜索工具的基礎結構.2.1Page

6、Rank原理PageRank算法是Google搜索引擎對檢索結果的一種排序算法.它的基本思想主要是來自傳統(tǒng)文獻計量學中的文獻引文分析,即一篇文獻的質量和重要性可以通過其它文獻對其引用的數(shù)量和引文質量來衡量,也就是說,一篇文獻被其它文獻引用越多,并且引用它的文獻的質量越高,則該文獻本身就越重要.Google在給出頁面排序時也有兩條標準：一是看有多少超級鏈接指向它；二是要看超級鏈接指向它的那個頁面重要不重要.這兩條直觀的想法就是PageRank算法的數(shù)學基礎,也是Google搜索引擎最基本的工作原理.PageRank算法利用了互聯(lián)網(wǎng)獨特的超鏈接結構.在龐大的超鏈接資源中,Goo

7、gle提取出上億個超級鏈接頁面進行分析,制作出一個巨大的網(wǎng)絡地圖.具體的講,就是把所有的網(wǎng)頁看作圖里面相應的頂點,如果網(wǎng)頁A有一個指向網(wǎng)頁B的鏈接,則認為一條從頂點A到頂點B的有向邊.這樣就可以利用圖論來研究網(wǎng)絡的拓撲結構.PageRank算法正是利用網(wǎng)絡的拓撲結構來判斷網(wǎng)頁的重要性.具體來說,假如網(wǎng)頁A有一個指向網(wǎng)頁B的超鏈接,Google就認為網(wǎng)頁A投了網(wǎng)頁B一票,說明網(wǎng)頁A認為網(wǎng)頁B有鏈接價值,因而B可能是一個重要的網(wǎng)頁.Google根據(jù)指向網(wǎng)頁B的超鏈接數(shù)及其重要性來判斷頁面B的重要性,并賦予相應的頁面等級