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

1、第卷第期一。西南民族大學(xué)學(xué)報(bào)。自然苧學(xué)版文章編號(hào)：（）搜索引擎的數(shù)學(xué)模型及其應(yīng)用趙國(guó)，宋建成（西南民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川成都）摘要：該文在闡明搜索引擎中關(guān)鍵的頁(yè)面等級(jí)算法（）原理的基礎(chǔ)上，分析了算法的隨機(jī)沖浪模型，并著重討論相應(yīng)的數(shù)學(xué)模型在足球隊(duì)排名問(wèn)題（年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽題）中的應(yīng)用具體做法是綜合考慮各隊(duì)的比賽成績(jī)，為每支球隊(duì)計(jì)算相應(yīng)的等級(jí)分（），然后根據(jù)各隊(duì)的等級(jí)分高低來(lái)確定名次考慮到競(jìng)技比賽結(jié)果的不確定性，最后建立了等級(jí)分的隨機(jī)沖浪模型分析表明等級(jí)分排名結(jié)果具有良好的參數(shù)穩(wěn)定性，并且可以成功地處理數(shù)據(jù)缺損方面的困難關(guān)鍵詞：搜索引擎；算法；隨機(jī)沖浪模型；足球隊(duì)排名問(wèn)題中圖

2、分類(lèi)號(hào)：文獻(xiàn)標(biāo)識(shí)碼：引言據(jù)統(tǒng)計(jì)，在短短多年的時(shí)間里，中產(chǎn)生的信息量相當(dāng)于人類(lèi)過(guò)去年產(chǎn)生的信息總量，而且上的信息量正以幾何級(jí)數(shù)遞增搜索引擎已經(jīng)成為人們進(jìn)行信息資源搜索必不可少的工具在眾多的搜索引擎中，搜索引擎以其雄厚的技術(shù)為支撐，憑借其強(qiáng)大的檢索功能和高質(zhì)量的檢索服務(wù)，逐漸脫穎而出搜索引擎是由斯坦福大學(xué)和共同設(shè)計(jì)的，它是目前功能最強(qiáng)的搜索引擎通過(guò)對(duì)億網(wǎng)頁(yè)進(jìn)行整理，可為世界各地的用戶(hù)提供所需的搜索結(jié)果，而且搜索速度極快，通常不到半秒，每天可提供約億次查詢(xún)服務(wù)圖搜索引擎的工作原理示意圖圖網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的優(yōu)勢(shì)在于掌握的信息量以及檢索模型和檢索速度傳統(tǒng)的搜索引擎在很大程度上取決于文字在網(wǎng)頁(yè)上出現(xiàn)的頻率使

3、用技術(shù)檢查整個(gè)網(wǎng)絡(luò)鏈接結(jié)構(gòu)，并確定哪些網(wǎng)頁(yè)重要性最高然后進(jìn)行超文本匹配分析（），以確定哪些網(wǎng)頁(yè)與正在執(zhí)行的特定搜索相關(guān)在綜合考慮整體收稿日期：作者簡(jiǎn)介：趙國(guó)（），男，碩士，西南民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院講師，主要研究方向?yàn)榻鹑跀?shù)學(xué)、數(shù)學(xué)模型 基金項(xiàng)目：西南民族大學(xué)青年項(xiàng)目第期趙國(guó)等：搜索引擎的數(shù)學(xué)模型及其應(yīng)用重要性以及與特定查詢(xún)的相關(guān)性之后，可以將最相關(guān)最可靠的搜索結(jié)果放在最前面搜索引擎的數(shù)學(xué)模型擁有多項(xiàng)專(zhuān)利技術(shù)，其中算法是關(guān)鍵技術(shù)之一，它奠定了強(qiáng)大的檢索功能及提供各種特色功能的基礎(chǔ)雖然每天有很多工程師負(fù)責(zé)全面改進(jìn)系統(tǒng)，但是仍把算法作為所有網(wǎng)絡(luò)搜索工具的基礎(chǔ)結(jié)構(gòu)【原理算法是搜索引擎對(duì)檢索結(jié)果

4、的一種排序算法它的基本思想主要是來(lái)自傳統(tǒng)文獻(xiàn)計(jì)量學(xué)中的文獻(xiàn)引文分析，即一篇文獻(xiàn)的質(zhì)量和重要性可以通過(guò)其它文獻(xiàn)對(duì)其引用的數(shù)量和引文質(zhì)量來(lái)衡量，也就是說(shuō)，一篇文獻(xiàn)被其它文獻(xiàn)引用越多，并且引用它的文獻(xiàn)的質(zhì)量越高，則該文獻(xiàn)本身就越重要在給出頁(yè)面排序時(shí)也有兩條標(biāo)準(zhǔn)：一是看有多少超級(jí)鏈接指向它；二是要看超級(jí)鏈接指向它的那個(gè)頁(yè)面重要不重要這兩條直觀的想法就是算法的數(shù)學(xué)基礎(chǔ)，也是搜索引擎最基本的工作原理算法利用了互聯(lián)網(wǎng)獨(dú)特的超鏈接結(jié)構(gòu)在龐大的超鏈接資源中，提取出上億個(gè)超級(jí)鏈接頁(yè)面進(jìn)行分析，制作出一個(gè)巨大的網(wǎng)絡(luò)地圖具體的講，就是把所有的網(wǎng)頁(yè)看作圖里面相應(yīng)的頂點(diǎn)，如果網(wǎng)頁(yè)有個(gè)指向網(wǎng)頁(yè)的鏈接，則認(rèn)為一條從頂點(diǎn)到頂點(diǎn)

5、的有向邊這樣就可以利用圖論來(lái)研究網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)算法正是利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)來(lái)判斷網(wǎng)頁(yè)的重要性具體來(lái)說(shuō)，假如網(wǎng)頁(yè)有個(gè)指向網(wǎng)頁(yè)的超鏈接，就認(rèn)為網(wǎng)頁(yè)投了網(wǎng)頁(yè)一票，說(shuō)明網(wǎng)頁(yè)認(rèn)為網(wǎng)頁(yè)有鏈接價(jià)值，因而可能是個(gè)重要的網(wǎng)頁(yè)根據(jù)指向網(wǎng)頁(yè)的超鏈接數(shù)及其重要性來(lái)判斷頁(yè)面的重要性，并賦予相應(yīng)的頁(yè)面等級(jí)值（）網(wǎng)頁(yè)的頁(yè)面等級(jí)值被平均分畫(huà)己給網(wǎng)頁(yè)所鏈接指向的網(wǎng)頁(yè)，從而當(dāng)網(wǎng)頁(yè)的頁(yè)面等級(jí)值比較高時(shí)，則網(wǎng)頁(yè)可從網(wǎng)頁(yè)到它的超鏈接分得一定的重要性根據(jù)這樣的分析，得到了高評(píng)價(jià)的重要頁(yè)面會(huì)被賦予較高的網(wǎng)頁(yè)等級(jí)，在檢索結(jié)果內(nèi)的排名也會(huì)較高頁(yè)面等級(jí)值（）是表示網(wǎng)頁(yè)重要性的綜合性指標(biāo)，而且不會(huì)受到不同搜索引擎的影響當(dāng)然，重要性高的頁(yè)面如果和檢索

6、關(guān)鍵詞無(wú)關(guān)同樣也沒(méi)有任何意義為此，使用了完善的超文本匹配分析技術(shù)，使得能夠檢索出重要而且正確的網(wǎng)頁(yè)算法算法的具體實(shí)現(xiàn)可以利用網(wǎng)頁(yè)所對(duì)應(yīng)的圖的鄰接矩陣來(lái)表達(dá)超鏈接關(guān)系為此，首先寫(xiě)出所對(duì)應(yīng)圖的鄰接矩陣為了能將網(wǎng)頁(yè)的頁(yè)面等級(jí)值平均分配給該網(wǎng)頁(yè)所鏈接指向的網(wǎng)頁(yè)，對(duì)各個(gè)行向量進(jìn)行歸一化一一一處理，得矩陣算法的矩陣是將歸一化矩陣轉(zhuǎn)置所得矩陣這樣形成的矩陣肜被稱(chēng)為轉(zhuǎn)移概率矩陣，它的各個(gè)列向量之和為全概率，各個(gè)行矢量表示狀態(tài)之間的轉(zhuǎn)移概率轉(zhuǎn)移概率矩陣與過(guò)程有著密切的聯(lián)系【】轉(zhuǎn)置的理由是，算法并非重視鏈接到多少頁(yè)面，而是重視被多少頁(yè)面鏈接各個(gè)網(wǎng)頁(yè)的頁(yè)面等級(jí)值的計(jì)算，就是求這個(gè)轉(zhuǎn)移概率矩陣的最大特征值所屬的特征向

7、量現(xiàn)在以前面給出的三個(gè)頁(yè)面之間的超鏈接關(guān)系為例，說(shuō)明算法如何計(jì)算給定網(wǎng)頁(yè)的頁(yè)面等級(jí)值，從而定量地知道哪些網(wǎng)頁(yè)是最重要的為利用網(wǎng)頁(yè)所對(duì)應(yīng)的圖的鄰接矩陣來(lái)表達(dá)鏈接關(guān)系，首先寫(xiě)出所對(duì)應(yīng)圖的鄰接矩陣為了能將網(wǎng)頁(yè)的頁(yè)面等級(jí)值平均分配給該網(wǎng)頁(yè)所鏈接指向的網(wǎng)頁(yè)，對(duì)各個(gè)行向量進(jìn)行歸一化處理，得西南民族大學(xué)學(xué)報(bào)自然科學(xué)版第卷彳將歸一化所得的矩陣彳轉(zhuǎn)置，所得到的轉(zhuǎn)移概率矩陣（口）為形一現(xiàn)給每個(gè)頁(yè)面尸一個(gè)值，這些值應(yīng)該由鏈接到該頁(yè)面的那些頁(yè)面的值確定，即指向的那些頁(yè)面的頁(yè)面等級(jí)值之和應(yīng)該與尸的頁(yè)面等級(jí)值。成正比設(shè)共同的比例系數(shù)為，則有下面的線(xiàn)性方程組土：，。（）令（而，）為頁(yè)面等級(jí)值組成的列向量，則由矩陣乘法，等式

8、（）可以寫(xiě)成觸由此求出轉(zhuǎn)移概率矩陣的最大正特征值五，相應(yīng)非負(fù)特征向量（，），由此可以確定網(wǎng)頁(yè)的排序?yàn)?，其中?yè)面，的排序無(wú)顯著差別，之所以將排在前面是因?yàn)橹赶虻某溄訑?shù)更多一些隨機(jī)沖浪模型（）算法原理中有個(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í)候，它的值就不能被分配給其它的頁(yè)面同樣道理，只有出鏈接而沒(méi)有入鏈接的頁(yè)面也是存在的但并不考慮這樣的頁(yè)面，因?yàn)闆](méi)有流入的而只流出的，從對(duì)稱(chēng)性角度來(lái)考慮是很奇怪的吲時(shí)，有時(shí)候也有鏈接只在一個(gè)集合內(nèi)部旋轉(zhuǎn)而不向外界鏈接

9、的現(xiàn)象在現(xiàn)實(shí)中的頁(yè)面，無(wú)論怎樣順著鏈接前進(jìn)，僅僅順著鏈接是絕對(duì)不能進(jìn)入的頁(yè)面群總歸是存在的技術(shù)為了解決這樣的問(wèn)題，提出用戶(hù)的隨機(jī)沖浪模型：用戶(hù)雖然在大多數(shù)場(chǎng)合都順著當(dāng)前頁(yè)面中的鏈接前進(jìn)，但有時(shí)會(huì)突然重新打開(kāi)瀏覽器隨機(jī)進(jìn)入到完全無(wú)關(guān)的頁(yè)面認(rèn)為：用戶(hù)在的情況下沿著鏈接前進(jìn)，但在的情況下會(huì)跳躍到無(wú)關(guān)的頁(yè)面中用公式表示相應(yīng)的轉(zhuǎn)移概率矩陣為一：！型門(mén)。其中，為分量全為的胛維列向量，從而為全矩陣，（，）為權(quán)重因子（），在實(shí)際中取也就是說(shuō)，在隨機(jī)沖浪模型中，求各個(gè)頁(yè)面等級(jí)值的問(wèn)題變成了求正矩陣形的最大特征值所屬的特征向量問(wèn)題還是考慮前面給出的三個(gè)網(wǎng)頁(yè)、之間的超鏈接關(guān)系，在隨機(jī)沖浪模型下為方便計(jì)算令，相應(yīng)的轉(zhuǎn)

10、移概率矩陣為一：螋，）根據(jù)著名的定理【】，轉(zhuǎn)移概率矩陣的最大正特征值是，相應(yīng)的特征向量為（，）由此可以確定網(wǎng)頁(yè)的排序?yàn)?，可?jiàn)隨機(jī)沖浪模型下的排序結(jié)果更合理一些第期趙國(guó)等：搜索引擎的數(shù)學(xué)模型及其應(yīng)用頁(yè)面等級(jí)算法的應(yīng)用首先我們從圖論的角度解釋算法的原理：一是看這個(gè)頁(yè)面對(duì)應(yīng)頂點(diǎn)的入度；二是要給指向該頂點(diǎn)的邊賦予權(quán)重，表明這個(gè)超級(jí)鏈接的重要性具體的講，就是把所有的頁(yè)面看作圖里面的點(diǎn)，然后給每個(gè)頁(yè)面一個(gè)數(shù)量，用這個(gè)數(shù)量來(lái)刻畫(huà)頁(yè)面的重要性，這樣網(wǎng)頁(yè)的重要性就脫離了它的具體內(nèi)容我們只需從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)出發(fā)研究網(wǎng)頁(yè)的重要性，這樣就可以用圖論來(lái)研究向互聯(lián)網(wǎng)這樣的隨機(jī)復(fù)雜網(wǎng)絡(luò)而且按照這個(gè)原理對(duì)網(wǎng)頁(yè)排序具有三個(gè)優(yōu)點(diǎn)：

11、第一，排序與特定搜索關(guān)鍵詞無(wú)關(guān)；第二，網(wǎng)頁(yè)排序與網(wǎng)頁(yè)的具體內(nèi)容無(wú)關(guān)；第三，只需要知道網(wǎng)頁(yè)所對(duì)應(yīng)的圖的結(jié)構(gòu)算法的這個(gè)特點(diǎn)使得它可以被應(yīng)用于社會(huì)領(lǐng)域的其他問(wèn)題例如體育比賽的排名問(wèn)題下面針對(duì)年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽題，利用算法討論足球隊(duì)排名次問(wèn)題，我們發(fā)現(xiàn)隨機(jī)沖浪模型可以有效克服數(shù)據(jù)缺損等方面的凼難足球隊(duì)排名次問(wèn)題要求我們建立一個(gè)客觀的評(píng)估方法，只依據(jù)過(guò)去一段時(shí)間（幾個(gè)賽季或幾年）內(nèi)每個(gè)球隊(duì)的戰(zhàn)績(jī)給出各個(gè)球隊(duì)的名次，具有很強(qiáng)的實(shí)際背景【通過(guò)分析題中支足球隊(duì)在聯(lián)賽中的成績(jī)，不難發(fā)現(xiàn)表中的數(shù)據(jù)殘缺不全，隊(duì)與隊(duì)之間的比賽場(chǎng)數(shù)相差很大，直接根據(jù)比賽成績(jī)來(lái)排名次比較困難下面我們利用算法的隨機(jī)沖浪模型來(lái)求解類(lèi)比

12、算法，我們可以綜合考慮各隊(duì)的比賽成績(jī)?yōu)槊恐蜿?duì)計(jì)算相應(yīng)的等級(jí)分（），然后根據(jù)各隊(duì)的等級(jí)分高低來(lái)確定名次直觀上看，給定球隊(duì)的等級(jí)分應(yīng)該由它所戰(zhàn)勝和戰(zhàn)平的球隊(duì)的數(shù)量以及被戰(zhàn)勝或戰(zhàn)平的球隊(duì)的實(shí)力共同決定具體來(lái)說(shuō)，確定球隊(duì)的等級(jí)分的依據(jù)應(yīng)為：一是看它戰(zhàn)勝和戰(zhàn)平了多少支球隊(duì)；二要看它所戰(zhàn)勝或戰(zhàn)平球隊(duì)的等級(jí)分的高低這兩條就是我們確定排名的基本原理在實(shí)際中，若出現(xiàn)等級(jí)分相同的情況，可以進(jìn)一步根據(jù)凈勝球的多少來(lái)確定排名由于表中包含的數(shù)據(jù)量龐大，我們先在不計(jì)平局，只考慮獲勝局的情形下計(jì)算出各隊(duì)的等級(jí)分，以說(shuō)明算法原理然后我們綜合考慮獲勝局和平局，加權(quán)后得到各隊(duì)的等級(jí)分，并據(jù)此進(jìn)行排名考慮到競(jìng)技比賽的結(jié)果的不確定

13、性，我們最后建立了等級(jí)分的隨機(jī)沖浪模型，分析表明等級(jí)分排名結(jié)果具有良好的參數(shù)穩(wěn)定性獲勝局的等級(jí)分首先利用有向賦權(quán)圖的權(quán)重矩陣來(lái)表達(dá)出各隊(duì)之間的勝負(fù)關(guān)系用圖的頂點(diǎn)表示相應(yīng)球隊(duì)，用連接兩個(gè)頂點(diǎn)與丁，的有向邊表示兩隊(duì)的比賽結(jié)果，同時(shí)給該邊賦予相應(yīng)的權(quán)重，表明戰(zhàn)勝丁，的次數(shù)由此，可以寫(xiě)出表中支球隊(duì)所對(duì)應(yīng)的有向賦權(quán)圖的權(quán)重矩陣?yán)?，表中五與瓦比賽了兩場(chǎng)，各勝一場(chǎng)，故瓦。，瓦，同理，互。表明正曾次戰(zhàn)勝正注意到被戰(zhàn)勝球隊(duì)的等級(jí)分應(yīng)該平均分配給各個(gè)獲勝球隊(duì)，將權(quán)重矩陣的各個(gè)列向量向量進(jìn)行歸一化，得轉(zhuǎn)移概率矩陣。）為西南民族大學(xué)學(xué)報(bào)自然科學(xué)版第卷銣；仉現(xiàn)設(shè)每個(gè)隊(duì)的等級(jí)分，這些等級(jí)分應(yīng)由被戰(zhàn)勝的那些隊(duì)的等級(jí)分確定

14、，即謗，“一，（）其中五為比例系數(shù)令（，一，），則由矩陣乘法，等式（）可以寫(xiě)成缸即各個(gè)隊(duì)的等級(jí)分的計(jì)算，轉(zhuǎn)化求這個(gè)轉(zhuǎn)移概率矩陣的最大正特征值旯所屬的正特征向量直接利用軟件計(jì)算得五，相應(yīng)等級(jí)分為（，）由此可以確定只算獲勝局的情況下各隊(duì)的排名為，。，加權(quán)等級(jí)分在實(shí)際中，平局也會(huì)隊(duì)雙方的排名產(chǎn)生影響，因此也有必要考慮平局對(duì)等級(jí)分的貢獻(xiàn)因?yàn)槠骄质窍嗷サ?，所以可以利用無(wú)向賦權(quán)圖的權(quán)重矩陣來(lái)表達(dá)出各隊(duì)之間的平局關(guān)系，即，注意平局的權(quán)重矩陣尸是對(duì)稱(chēng)的同時(shí)注意到被戰(zhàn)平球隊(duì)的等級(jí)分也應(yīng)該平均分配給各個(gè)與之戰(zhàn)平的球隊(duì)，故將權(quán)重矩陣的各個(gè)列向量向量進(jìn)行歸一化處理，得轉(zhuǎn)移概率矩陣第期 趙國(guó)等：搜索引擎的數(shù)學(xué)模型及其應(yīng)

15、用 根據(jù)常識(shí)，在一場(chǎng)比賽中平局出現(xiàn)的概率為三同時(shí)，考慮到通常平局與獲勝局的得分比為：，我們可以 對(duì)平局和獲勝局的轉(zhuǎn)移概率矩陣進(jìn)行加權(quán)處理，得到下面的加權(quán)權(quán)重矩陣 形二××二×× 同樣，被戰(zhàn)勝或戰(zhàn)平球隊(duì)的等級(jí)分也應(yīng)該平均分配給各個(gè)獲勝隊(duì)或與之戰(zhàn)平的球隊(duì)，故將加權(quán)權(quán)重矩陣的各個(gè) 列向量向量進(jìn)行歸一化，得轉(zhuǎn)移概率矩陣形（）為 現(xiàn)設(shè)每個(gè)隊(duì)的等級(jí)分為，這些等級(jí)分應(yīng)由所戰(zhàn)勝或戰(zhàn)平的那些隊(duì)的等級(jí)分確定，即 佗一 帚 ，。， （） 萬(wàn)方數(shù)據(jù) 西南民族大學(xué)學(xué)報(bào)自然科學(xué)版 第卷 其中五為比例系數(shù)令（，一，），則由矩陣乘法，等式（）可以寫(xiě)成 即各個(gè)隊(duì)的等級(jí)分的計(jì)算，轉(zhuǎn)化求平局

16、的轉(zhuǎn)移概率矩陣矩陣的最大正特征值名所屬的非負(fù)特征向量直 接利用軟件計(jì)算得力，相應(yīng)等級(jí)分為 （ ， ， ， ， ， ， ） 由此可以確定在綜合考慮獲勝局和平局的情況下各隊(duì)的排名為 ，：，。，：，。 等級(jí)分的隨機(jī)沖浪模型 在大多數(shù)時(shí)候，競(jìng)技比賽的結(jié)果都是兩隊(duì)之間實(shí)力的客觀反映但是，競(jìng)技比賽的結(jié)果有時(shí)具有一定的不 確定性，它很容易受到某些偶然或人為因素的影響為了消除這些不確定因素的影響，我們需要建立等級(jí)分的 隨機(jī)沖浪模型 設(shè)球隊(duì)的實(shí)力能確定比賽的結(jié)果的概率為，即強(qiáng)隊(duì)因?yàn)椴淮_定因素輸?shù)艚o任意一支球隊(duì)的概率為一 則可得下面的轉(zhuǎn)移概率矩陣 礦：木萬(wàn)坐幸 療 其中，為分量全為的療維列向量，從而丁為全矩陣；（，）為權(quán)重因子，在實(shí)際中可以根據(jù)歷史數(shù)據(jù) 確定同樣，各個(gè)隊(duì)的等級(jí)分的計(jì)算，轉(zhuǎn)化求轉(zhuǎn)移概率矩陣形最大正特征值所屬的正特征向量 下面著重分析權(quán)重因子（，）的變化對(duì)排名的影響為此，我們利用軟件計(jì)算出權(quán)重因子取不 同的值時(shí)的排智隋況如表 表權(quán)重因子取不同的值時(shí)的排名情況 取值范圍 球隊(duì)排名 ，：，。，：，。 ，：，。，：， ，：，。，：，。 ，：，。，：，。，