搜索引擎的數(shù)學(xué)模型及其應(yīng)用

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

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

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

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

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

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

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

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

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

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