張家健，趙冰

（河海大學(xué) 商學(xué)院，江蘇 南京　211100）

基于網(wǎng)頁(yè)排名的其他鏈接方法的研究

張家健，趙冰

（河海大學(xué) 商學(xué)院，江蘇 南京211100）

目前針對(duì)主要的排名算法PageRank和HITS的研究與應(yīng)用較廣泛，同時(shí)，其它排名算法也逐漸得到了研究者的重視。文中將對(duì)其它排名算法中的SALSA和TrafficRank進(jìn)行研究。文中首先對(duì)布爾搜索引擎、向量空間模型引擎、概率模型搜索引擎、元搜索引擎等基本搜索引擎模型進(jìn)行綜述，總結(jié)各基本搜索引擎模型的特征和優(yōu)缺點(diǎn)。其次對(duì)SALSA和TrafficRank的算法進(jìn)行分析，總結(jié)出兩種排名算法的特征和優(yōu)缺點(diǎn)。

布爾搜索引擎；向量空間模型引擎；概率模型搜索引擎；元搜索引擎；SALSA；TrafficRank

蒂姆·伯納斯-李和他的萬(wàn)維網(wǎng)于1989年進(jìn)入了信息檢索的世界，記錄網(wǎng)絡(luò)信息檢索的鏈接分析方法是包括谷歌使用的PageRank和Teoma使用的HITS在內(nèi)的現(xiàn)今最為流行且成功的多個(gè)搜索引擎的底層機(jī)制。截至2004年1月，萬(wàn)維網(wǎng)包含了超過(guò)100億個(gè)頁(yè)面。如何準(zhǔn)確并快速地在巨量的信息世界中尋找到對(duì)自己有價(jià)值的內(nèi)容？當(dāng)然這離不開(kāi)搜索引擎，影響搜索引擎有效性的因素有許多，但從根本上說(shuō)，關(guān)鍵在于搜索引擎自身的鏈接算法設(shè)計(jì)。

1　基本模型

網(wǎng)絡(luò)信息檢索是在世界上最大且相互鏈接的文檔集中進(jìn)行的搜索，大多數(shù)搜索引擎依賴(lài)于以下基本模型中的一種或者多種：

1）布爾搜索引擎

信息檢索的布爾模型是最早最簡(jiǎn)單的檢索方法之一，它使用嚴(yán)格匹配來(lái)將文檔與用戶(hù)的查詢(xún)進(jìn)行比對(duì)。該模型經(jīng)過(guò)改良的派生方法為大多數(shù)圖書(shū)館所使用。信息檢索的布爾模型工作原理是考察在文檔中有哪些關(guān)鍵詞出現(xiàn)了或未曾出現(xiàn)，并據(jù)此判定文檔與檢索相關(guān)或無(wú)關(guān)［1］。但是標(biāo)準(zhǔn)的布爾引擎無(wú)法返回那些語(yǔ)義相關(guān)但關(guān)鍵詞未被包括在原始查詢(xún)中的文檔。許多布爾搜索引擎要求用戶(hù)熟悉布爾運(yùn)算符以及引擎的特殊語(yǔ)法。布爾模型的各種變體構(gòu)成了許多搜索引擎的基礎(chǔ)，其優(yōu)點(diǎn)包括：建立并編寫(xiě)布爾引擎是直接的；查詢(xún)處理迅速，可以采用并行方式對(duì)文檔的關(guān)鍵詞文件進(jìn)行快速掃描；布爾模型可以很好地?cái)U(kuò)展到大的文檔集［2］。

2）向量空間模型引擎

該模型中，向量空間模型被用于避開(kāi)前述的若干信息檢索難題［3］。向量空間模型將文本數(shù)據(jù)變換為數(shù)值向量和矩陣，使用矩陣分析方法來(lái)發(fā)現(xiàn)文檔集之中的關(guān)鍵特征和聯(lián)系。一些高級(jí)向量空間模型能夠訪(fǎng)問(wèn)文檔集中隱含的語(yǔ)義結(jié)構(gòu)［4］。該模型的優(yōu)點(diǎn)包括：①相關(guān)性評(píng)分：通過(guò)給每個(gè)文檔賦予一個(gè)0到1之間的數(shù)，向量空間模型允許進(jìn)行文檔的部分匹配查詢(xún)。該數(shù)值可以被解釋為文檔與查詢(xún)之間的相關(guān)似然度。進(jìn)而檢索到的文檔集可以根據(jù)相關(guān)程度進(jìn)行排序。按照這一方式，向量空間模型以有序的列表返回結(jié)果文檔，按照相關(guān)性的分?jǐn)?shù)排序，返回的第一個(gè)文檔被認(rèn)為是與用戶(hù)查詢(xún)最為相關(guān)者，一些向量空間搜索引擎以相似度比例的形式給出相關(guān)性的評(píng)分。該模型的缺點(diǎn)為：必須計(jì)算每個(gè)文檔和查詢(xún)之間的距離度量，隨著文檔集的增大，矩陣分解的開(kāi)銷(xiāo)將使模型不再具有可行性［5］；向量空間模型無(wú)法很好地?cái)U(kuò)展，它僅局限于小文檔集。

3）概率模型搜索引擎

概率模型試圖對(duì)用戶(hù)找到某個(gè)特定相關(guān)文檔的概率進(jìn)行估計(jì)，檢索得到的文檔根據(jù)它們的相關(guān)幾率進(jìn)行排名。概率模型以遞歸的方式運(yùn)行，并要求算法能夠猜測(cè)得到初始參數(shù)，進(jìn)而逐次嘗試改善這一初始猜測(cè)，以得到最終的相關(guān)幾率的排位［6］。概率模型的缺點(diǎn)為：構(gòu)建和編程難度較大，因此限制了其擴(kuò)展性。同時(shí)該模型要求做出若干不現(xiàn)實(shí)的假設(shè)。該模型的優(yōu)點(diǎn)在于概率框架可以自然地納入先驗(yàn)偏好，可以做到針對(duì)單個(gè)用戶(hù)的偏好調(diào)整搜索結(jié)果。

4）元搜索引擎

該模型將以上3種模型相結(jié)合，其工作原理是用一個(gè)搜索引擎來(lái)搜索可以完成任務(wù)時(shí)，用兩個(gè)或以上搜索引擎搜索的效果更顯著。一個(gè)搜索引擎可能在某個(gè)任務(wù)上十分出色，而第二個(gè)搜索引擎則可能在另一項(xiàng)任務(wù)上表現(xiàn)好于第一個(gè)搜索引擎。元搜索引擎可以充分利用許多單獨(dú)的搜索引擎各自具有的最佳特性，可以同時(shí)將一個(gè)查詢(xún)發(fā)送至數(shù)個(gè)搜索引擎，并將所有這些搜索引擎的結(jié)果以一個(gè)統(tǒng)一的列表返回。元搜索引擎可以應(yīng)用于某個(gè)特定學(xué)科內(nèi)的搜索［7］。

加快農(nóng)業(yè)產(chǎn)業(yè)化發(fā)展。支持具有比較優(yōu)勢(shì)的龍頭企業(yè)建設(shè)現(xiàn)代農(nóng)業(yè)精深加工項(xiàng)目，建立示范性生產(chǎn)基地，大力培育省級(jí)農(nóng)業(yè)產(chǎn)業(yè)化集群。鼓勵(lì)農(nóng)民專(zhuān)業(yè)合作社發(fā)展農(nóng)產(chǎn)品加工、銷(xiāo)售，拓展合作領(lǐng)域和服務(wù)內(nèi)容，積極發(fā)展訂單性農(nóng)產(chǎn)品生產(chǎn)、加工、配送。

2　SALSA

2.1SALSA示例

1998年開(kāi)始，人們利用PageRank或HITS對(duì)網(wǎng)頁(yè)的受歡迎程度進(jìn)行排名。2000年，SALSA方法也被應(yīng)用于這一領(lǐng)域［8］。SALSA（Stochastic Approach to Link Structure Anatysis）是由羅尼·倫佩爾和什洛莫·莫蘭發(fā)明的一種網(wǎng)頁(yè)排名方法，該算法采用了HITS的評(píng)分方法，為網(wǎng)頁(yè)生成了樞紐和權(quán)威評(píng)分；同時(shí)結(jié)合了PageRank的導(dǎo)出方式，評(píng)分由馬爾可夫鏈導(dǎo)出。

1）SALSA示例

首先為某個(gè)特定查詢(xún)產(chǎn)生一個(gè)對(duì)應(yīng)的領(lǐng)域圖N，如圖1所示：

圖1　頁(yè)面1和6的領(lǐng)域圖NFig．1　Page 1 and 6 field figure N

SALSA和HITS的區(qū)別在于，SALSA并不構(gòu)造領(lǐng)域圖N的領(lǐng)接矩陣L，而是構(gòu)建了一個(gè)二分無(wú)向圖G。其中G由三個(gè)集合給出：樞紐結(jié)點(diǎn)集合Vh（N中所有出度＞0的結(jié)點(diǎn)）、權(quán)威結(jié)點(diǎn)集合Va（N中所有入度＞0的結(jié)點(diǎn)）和N中有向邊的集合E，N中的某個(gè)結(jié)點(diǎn)可能同時(shí)出現(xiàn)在Vh和Va中。因此，對(duì)于上述領(lǐng)域圖可得：

如圖2所示，二分無(wú)向圖G中有一個(gè)樞紐側(cè)和一個(gè)權(quán)威側(cè)。Vh中的結(jié)點(diǎn)列在樞紐側(cè)，Va中的結(jié)點(diǎn)列在權(quán)威側(cè)。E中的每條有向邊由G中的一條無(wú)向邊所表示。

圖2　G：SALSA的二分圖Fig．2　G:binary chart of SALSA

由此，G可以得出兩條馬爾可夫鏈：一條樞紐馬爾可夫鏈，轉(zhuǎn)移概率矩陣為H；一條權(quán)威馬爾可夫鏈，轉(zhuǎn)移概率矩陣為A。HITS使用了N的鄰接矩陣L以計(jì)算未加權(quán)矩陣L的權(quán)威和樞紐評(píng)分，PageRank使用行歸一化的加權(quán)矩陣G以計(jì)算類(lèi)似于權(quán)威評(píng)分的度量。SALSA則同時(shí)使用了行加權(quán)和列加權(quán)的非零列除以其列和后所得的矩陣。進(jìn)而計(jì)算領(lǐng)域圖N可得：

由此得出的SALSA樞紐矩陣和權(quán)威矩陣為：

如果二分圖G是聯(lián)通的，那么H和A就均為不可約的馬爾可夫鏈，而H的穩(wěn)態(tài)向量可以給出查詢(xún)關(guān)于領(lǐng)域圖N的樞紐評(píng)分，則可以給出權(quán)威評(píng)分；如果G不連通，那么H和A各自包含若干個(gè)不可約的組分，此時(shí)需要通過(guò)將每個(gè)單獨(dú)的不可約部分的穩(wěn)態(tài)向量拼接以得到全局的樞紐和權(quán)威評(píng)分。對(duì)于更大的圖，不能通過(guò)簡(jiǎn)單地觀察來(lái)了解聯(lián)通性時(shí)，那么也已經(jīng)有圖的遍歷算法，可以判斷圖的連通性并識(shí)別其聯(lián)通組分［9］。由于G不連通，因此H和A中包含了多個(gè)聯(lián)通組分，H包含了兩個(gè)聯(lián)通組分，即C=｛2｝，和D=｛1，3，6，10｝；A的聯(lián)通組分為E=｛1｝和F=｛3，5，6｝。H和 A中所有不可約組分均包含了自循環(huán)，即以上的鏈均是非周期的。H的兩個(gè)不可約組分的穩(wěn)態(tài)向?yàn)椋?/p>

而A的兩個(gè)不可約組分的穩(wěn)態(tài)向量為：

既然樞紐組分C僅包含了所有5個(gè)樞紐結(jié)點(diǎn)中的1個(gè)，那么其穩(wěn)態(tài)樞紐向量的權(quán)值為1/5，而D包含了5個(gè)樞紐結(jié)點(diǎn)中的4個(gè)，其穩(wěn)態(tài)向量的權(quán)值為4/5。因此，全局的樞紐向量為：

對(duì)權(quán)威結(jié)點(diǎn)進(jìn)行加權(quán)，可由單獨(dú)的權(quán)威向量構(gòu)成出全局權(quán)威向量：

有上述示例可以可出如下結(jié)論：1）SALSA是將獨(dú)立部分的評(píng)分加以拼接以構(gòu)成全局評(píng)分的一種方法；2）多個(gè)聯(lián)通組分對(duì)于計(jì)算是個(gè)優(yōu)點(diǎn)，因?yàn)楝F(xiàn)在有待求解的馬爾代夫鏈較小。這與PageRank對(duì)不連通網(wǎng)絡(luò)圖進(jìn)行的人工調(diào)整形成對(duì)比，PageRank中的調(diào)整需要通過(guò)在所有的網(wǎng)頁(yè)間增加有向鏈接以使聯(lián)通性成立。

2.2SALSA優(yōu)缺點(diǎn)分析

SALSA將HITS和PageRank的特點(diǎn)進(jìn)行了結(jié)合，因此，SALSA具有的優(yōu)點(diǎn)包括：不存在主題漂移問(wèn)題，即跑題的重要頁(yè)面會(huì)混進(jìn)領(lǐng)域集并由此獲得了位居前列的評(píng)分；因?yàn)闃屑~和權(quán)威評(píng)分之間的耦合相對(duì)較弱，SALSA受垃圾信息影響的程度較低；SALSA的二分圖G中存在的、實(shí)際中常常會(huì)出現(xiàn)的多個(gè)聯(lián)通組分，對(duì)于計(jì)算而言非常有利。

但是SALSA也存在阻礙其廣泛使用的因素，即其查詢(xún)相關(guān)性。在查詢(xún)期間，必須構(gòu)建查詢(xún)的領(lǐng)域圖N并計(jì)算兩條馬爾可夫鏈的穩(wěn)態(tài)向量；SALSA的另一個(gè)缺陷是收斂性。SALSA的收斂性和HITS相似，原始形式的HITS和SALSA都不能強(qiáng)行使得圖具有不可約性，因此當(dāng)領(lǐng)域圖可約時(shí)，算法給出的向量可能不唯一［10］。

3　TrafficRank

排名算法在為網(wǎng)絡(luò)信息檢索提供幫助時(shí)具有較高的有效性，很多新的算法都是基于PageRank、HITS、SALSA3種方法的改進(jìn)或組合［11］。而TrafficRank則是一種原創(chuàng)性的新的排名算法。

令Pij為由頁(yè)面i到頁(yè)面j的鏈接上的流量占總網(wǎng)絡(luò)流量的比例。如果沒(méi)有從i到j(luò)的超鏈接，則Pij=0。Pij的這一定義意味著，對(duì)萬(wàn)維網(wǎng)中的每條超鏈接對(duì)對(duì)應(yīng)著一個(gè)變量。對(duì)這些Pij的值進(jìn)行估計(jì)，然后將進(jìn)入頁(yè)面j的流量比例作為頁(yè)面j的TrafficRank值。變量Pij必須滿(mǎn)足某些約束：；對(duì)任何頁(yè)面j，有；Pij可以任意取值。因此，TrafficRank模型中的Pij值：，滿(mǎn)足對(duì)所有j，

這個(gè)熵函數(shù)對(duì)選擇Pij的自由度進(jìn)行了最大化，在以上約束條件下，對(duì)這些概率的最佳無(wú)偏估計(jì)。進(jìn)而求解這個(gè)最優(yōu)化問(wèn)題來(lái)獲得Pij，并給出每個(gè)頁(yè)面的TrafficRank值。利用拉格朗日乘子對(duì)最優(yōu)化問(wèn)題中的多個(gè)變量進(jìn)行快速迭代計(jì)算，高的 TrafficRank值傾向于對(duì)應(yīng)具有許多出鏈的情況。TrafficRank衡量了流經(jīng)一個(gè)頁(yè)面的流量，而大量的流量需要大量的入鏈和出鏈。

TrafficRank的優(yōu)點(diǎn)為：當(dāng)?shù)榷嗟牧髁啃畔⒆兊每捎脮r(shí)，可以用約束的形式將這些信息加入到模型中；對(duì)于該最優(yōu)化問(wèn)題的對(duì)偶解，將原始解的拉格朗日乘子取倒數(shù)，會(huì)得到每個(gè)網(wǎng)頁(yè)的HotRank。

4　結(jié)　論

網(wǎng)頁(yè)排名的鏈接算法在為網(wǎng)絡(luò)信息檢索提供幫助的這一方面已經(jīng)展現(xiàn)了有效性，但是無(wú)論是SALSA、TrafficRank、HITS或是PageRank，目前的研究都還不盡完善。由于不同算法給出的排名前K位的網(wǎng)頁(yè)列表彼此之間存在明顯差別，因此未來(lái)的研究工作可以將多個(gè)相互獨(dú)立的評(píng)分算法的結(jié)果加以融合。

［1］Ricardo Baeza-Yates and Berthier Ribeiro-Neto．Modern Information Retrieval［C］//．ACM Press，New York，1999： 1217-1264．

［2］William B．Frakes and ricardo Baeza-Yates．Information Retrieval:Data structures and algorithms［C］//Prentice Hall，Englewood Cliffs，NJ，1992:381-419．

［3］Gerard Salton and Chris Buckley．Introduction to Modern Information Retrieval［M］．McGraw-Hill，New York，1983．

［4］Susan T．Dumais．Improving the retrieval of information from external sources［C］//．Behavior Research Methods，Instruments and Computers，1991．

［5］Carl D．Meyer．Matrix Analysis and Applied Linear Algebra ［C］//．SIAM，Philadelphia，2000．

［6］Michael W．Berry and Murray Browne．Understanding search engines:mathematical modeling and text retrieval［J］．SIAM，Philadelphia，2an edition，2005:78-93．

［7］Paolo Boldi and Sebastiano Vigna．The WebGraph framework II．Codes for the World Wide Web［C］//．Technical Report 286-03，Universita di Milano，Dipartimento diScienze dell’Informazione Engineering，2003．

［8］Ronny Lempel and Shlomo Moran．The stochastic approach for link-structure analysis and the TKC effect．In The Ninth International World Wide Web Conference［C］//．New York，2000．ACM Press，2000：161-226．

［9］Thomas H．Cormen，Charles E．Leiserson，Ronald L．Rivest，and Clifford Stein．Introduction to Algorithms［C］//．MIT Press，2001（11）：278-296．

［10］Ayman Farahat，Thomas Lofaro etc．Authority rankings from HITS，PageRank，and SALSA:Existence，uniqueness，and effect of initialization［J］．SIAM Journal on Scientific Computing，2006 （27）:1181-213．

［11］Matthew Richardson and Petro Domingos．The intelligent surfer:Probabilisticcombinationoflinkandcontent information in PageRank［J］．Advances in Neural Information Processing Systems，2002（14）:1398-1399．

The research of other links method based on page rank

ZHANG Jia-jian，ZHAO Bing
（Business School of HOHAI University，Nanjing 211100，China）

There are a lot of PageRank and HITS against the main ranking algorithm study．At the same time，other ranking algorithms also gradually got the attention of the researchers．This paper will study of SALSA and TrafficRank．This paper summarizes the basic characteristics and advantages and disadvantages of search engine model，including the Boolean search engine，vector space model engines，search engines，metasearch engines．Finally，this paper analyzes the algorithm of the SALSA and TrafficRank，summed up the characteristics and advantages and disadvantages of these two kinds of ranking algorithm．

Boolean search engine；vector space model engines；search engines；metasearch engines；SALSA；TrafficRank

TN99

A

1674－6236（2016）02-0128-04

2015-03-31稿件編號(hào)：201503473

江蘇省社科聯(lián)研究基金（201035）

張家?。?987—），男，江蘇南京人，碩士。研究方向：企業(yè)管理、技術(shù)經(jīng)濟(jì)。