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

張家健，趙冰

（河海大學 商學院，江蘇 南京　211100）

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

張家健，趙冰

（河海大學 商學院，江蘇 南京211100）

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

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

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

1　基本模型

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

1）布爾搜索引擎

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

2）向量空間模型引擎

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

3）概率模型搜索引擎

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

4）元搜索引擎

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

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

2　SALSA

2.1SALSA示例

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

1）SALSA示例

首先為某個特定查詢產生一個對應的領域圖N，如圖1所示：

圖1　頁面1和6的領域圖NFig．1　Page 1 and 6 field figure N

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

如圖2所示，二分無向圖G中有一個樞紐側和一個權威側。Vh中的結點列在樞紐側，Va中的結點列在權威側。E中的每條有向邊由G中的一條無向邊所表示。

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

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

由此得出的SALSA樞紐矩陣和權威矩陣為：

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

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

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

對權威結點進行加權，可由單獨的權威向量構成出全局權威向量：

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

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

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

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

3　TrafficRank

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

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

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

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

4　結　論

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

［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稿件編號：201503473

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

張家健（1987—），男，江蘇南京人，碩士。研究方向：企業(yè)管理、技術經濟。