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

1、第36卷第3期JoumaIofSouthw西est南Un民iv族ers大ity學fo學rN報ati。on自al然itie苧sN學at版uralScienceEditionMay201oI1‘一。文章編號：10032843(2010)03048007Google搜索引擎的數(shù)學模型及其應用趙國，宋建成(西南民族大學計算機科學與技術學院，四川成都610041)摘要：該文在闡明Google搜索引擎中關鍵的頁面等級算法(PageRallk)原理的

2、基礎上，分析了PageRank算法的隨機沖浪模型，并著重討論相應的數(shù)學模型在足球隊排名問題(1993年全國大學生數(shù)學建模競賽B題)中的應用具體做法是綜合考慮各隊的比賽成績，為每支球隊計算相應的等級分(Rank)，然后根據(jù)各隊的等級分高低來確定名次考慮到競技比賽結果的不確定性，最后建立了等級分的隨機沖浪模型分析表明等級分排名結果具有良好的參數(shù)穩(wěn)定性，并且可以成功地處理數(shù)據(jù)缺損方面的困難關鍵詞：搜索引擎；GooglePageRank算法；隨

3、機沖浪模型；足球隊排名問題中圖分類號：01414文獻標識碼：A1引言據(jù)統(tǒng)計，在短短20多年的時間里，Intemet中產(chǎn)生的信息量相當于人類過去100年產(chǎn)生的信息總量，而且Internet上的信息量正以幾何級數(shù)遞增搜索引擎已經(jīng)成為人們進行Internet信息資源搜索必不可少的工具在眾多的搜索引擎中，Google搜索引擎以其雄厚的技術為支撐，憑借其強大的檢索功能和高質(zhì)量的檢索服務，逐漸脫穎而出Google搜索引擎是由斯坦福大學SergeyB

4、rin和LawrencePage共同設計的，它是目前功能最強的搜索引擎通過對80億網(wǎng)頁進行整理，Google可為世界各地的用戶提供所需的搜索結果，而且搜索速度極快，通常不到半秒，每天可提供約3億次查詢服務圖1Google搜索引擎的工作原理示意圖圖2Intemet網(wǎng)絡的拓撲結構Google的優(yōu)勢在于掌握的信息量以及檢索模型和檢索速度傳統(tǒng)的搜索引擎在很大程度上取決于文字在網(wǎng)頁上出現(xiàn)的頻率Google使用PageRank技術檢查整個網(wǎng)絡鏈接結

5、構，并確定哪些網(wǎng)頁重要性最高然后進行超文本匹配分析(HypeneXtMatchingAnalysis)，以確定哪些網(wǎng)頁與正在執(zhí)行的特定搜索相關在綜合考慮整體收稿日期：20100313作者簡介：趙國(1979)，男，碩士，西南民族大學計算機科學與技術學院講師，主要研究方向為金融數(shù)學、數(shù)學模型基金項目：西南民族大學青年項目萬方數(shù)據(jù)482西南民族大學學報自然科學版第36卷彳=o12O0l0將歸一化所得的矩陣彳轉置，所得到的轉移概率矩陣∥=(w

6、口)為現(xiàn)給每個頁面尸一個PageRank值x，，這些PageRank值應該由鏈接到該頁面的那些頁面的PageRank值確定，即指向P的那些頁面的頁面等級值之和應該與尸的頁面等級值x。成正比設共同的比例系數(shù)為A，則有下面的線性方程組土≥：W，，x，=2x，，f_12，3(1)。J=l令x=(而，x2，X3)7為頁面等級值組成的列向量，則由矩陣乘法，等式(1)可以寫成Wx=觸由此求出轉移概率矩陣的最大正特征值五=1，相應非負特征向量x=(1

7、，1／2，1)1，由此可以確定網(wǎng)頁的排序為C，A，B，其中頁面A，C的排序無顯著差別，之所以將c排在前面是因為指向C的超鏈接數(shù)更多一些23隨機沖浪模型(RandomSurferModel)PageRank算法原理中有—個重要的假設：所有的網(wǎng)頁形成一個閉合的鏈接圖，除了這些文檔以外沒有其他任何鏈接的出入，并且每個網(wǎng)頁能從其他網(wǎng)頁通過超鏈接達到但是在現(xiàn)實的網(wǎng)絡中，并不完全是這樣的情況當一個頁面沒有出鏈的時候，它的PageRank值就不能被分

8、配給其它的頁面同樣道理，只有出鏈接而沒有入鏈接的頁面也是存在的但PageRank并不考慮這樣的頁面，因為沒有流入的PageRank而只流出的PageRank，從對稱性角度來考慮是很奇怪的吲時，有時候也有鏈接只在一個集合內(nèi)部旋轉而不向外界鏈接的現(xiàn)象在現(xiàn)實中的頁面，無論怎樣順著鏈接前進，僅僅順著鏈接是絕對不能進入的頁面群總歸是存在的PageRank技術為了解決這樣的問題，提出用戶的隨機沖浪模型：用戶雖然在大多數(shù)場合都順著當前頁面中的鏈接前進

9、，但有時會突然重新打開瀏覽器隨機進入到完全無關的頁面Google認為：用戶在85％的情況下沿著鏈接前進，但在15％的情況下會跳躍到無關的頁面中用公式表示相應的轉移概率矩陣為一W：dWo!型PP7’。門其中，e為分量全為l的胛維列向量，從而eel為全1矩陣，d∈(0，1)為權重因子(dampingfactor)，在實際中Google取d=O85也就是說，在隨機沖浪模型中，求各個頁面等級值PageRank的問題變成了求正矩陣形的最大特征值所

10、屬的特征向量問題還是考慮前面給出的三個網(wǎng)頁A、B、c之間的超鏈接關系，在隨機沖浪模型下為方便計算令d=05，相應的轉移概率矩陣為，，o1667o1667o6667)一W：o5W4螋PP7104167o1667o1667I3Io4167o6667o1667j根據(jù)著名的Perron—Frobenius定理【3】，轉移概率矩陣∥的最大正特征值是1，相應的特征向量為(14／13，10／13，15／13)T由此可以確定網(wǎng)頁的排序為c，A，B可見隨