基于網(wǎng)頁排名算法的敏感性分析

馬莉娜，張家健，李立維

（1.河海大學(xué) 商學(xué)院，江蘇 南京　210000；2.江蘇省郵電規(guī)劃設(shè)計(jì)院有限公司 江蘇 南京210019）

基于網(wǎng)頁排名算法的敏感性分析

馬莉娜1，張家健2，李立維2

（1.河海大學(xué) 商學(xué)院，江蘇 南京210000；2.江蘇省郵電規(guī)劃設(shè)計(jì)院有限公司 江蘇 南京210019）

對(duì)網(wǎng)頁排名算法的敏感性分析，能夠進(jìn)一步了解關(guān)于算法模型所給出的歡迎度評(píng)分的原理和條件范圍?；趨?shù)的不同變化會(huì)導(dǎo)致不同程度的敏感性這一問題，本文通過對(duì)算法的數(shù)學(xué)內(nèi)容分析，研究PageRank和HITS的敏感性問題。在分析矩陣G對(duì)于比例參數(shù)α、超鏈接矩陣H和個(gè)性化向量vT的依賴性的基礎(chǔ)上，分析了3個(gè)特定參數(shù)對(duì)PageRank向量的影響，最后，對(duì)HITS的敏感性進(jìn)行分析。

PageRank；HITS；敏感性分析；比例參數(shù)α；超鏈接矩陣H；個(gè)性化向量νT

作為搜索引擎的核心部件，網(wǎng)頁排名算法決定了搜索到的相關(guān)結(jié)果以何種順序呈現(xiàn)給用戶，其性能的優(yōu)劣將會(huì)直接影響搜索引擎的服務(wù)質(zhì)量和用戶的搜索體驗(yàn)[1]。對(duì)網(wǎng)頁排名算法的敏感性分析，能夠進(jìn)一步了解關(guān)于算法模型所給出的歡迎度評(píng)分的原理和條件范圍，同樣可以通過它的敏感性進(jìn)一步了解網(wǎng)頁排名算法模型的“個(gè)性”。

1　PageRank的敏感性分析

1.1α的敏感性分析

通過導(dǎo)數(shù)以分析α的改變對(duì)于πT的影響，πT對(duì)α求導(dǎo)所得的導(dǎo)數(shù)記為dπT（α）/dα，可知當(dāng)α發(fā)生改變時(shí)，PageRank向量πT中的元素將會(huì)發(fā)生改變[2-3]。如果dπT（α）/dα中的元素j的幅值較大，當(dāng)α小幅增加時(shí)，πj對(duì)于α的微小變化也會(huì)非常敏感。同時(shí)，如果dπj（α）/dα＞0，則α的小幅增加意味著Pj的PageRank將會(huì)有所提升；dπj（α）/dα＜0，則α的小幅增加意味著Pj的PageRank將會(huì)有所下降。理論角度分析，參數(shù)α的參數(shù)值在0～1之間變化，G依賴于α，進(jìn)而可知G（α）=αS＋（1-α）eνT，求導(dǎo)dπT（α）/dα可以分析出πT（α）對(duì)α的敏感性并得出πT（α）相對(duì)于α的小幅變化的變化率。需要注意到，雖然分布πT（α）是G（α）的左特征向量，但是特征向量的元素并不一定是G（α）中元素的可微函數(shù)，因此，dπT（α）/dα的存在性需要進(jìn)一步明確。設(shè)PageRank向量由下式給出：

該式中，Di（α）為I-G（α）中的第i個(gè)n-1階主子式。由于每個(gè)主子式Di（α）＞0都是I-G（α）中元素值得乘積之和，因此πT（α）中的每個(gè)元素在（0，1）區(qū)間上都是α的一個(gè)可微函數(shù)。若πT（α）=（π1（α）π2（α），…，πn（α））為PageRank向量，則對(duì)每個(gè)j=1，2，…，n，有，分析該式可知，當(dāng)α值較小時(shí)，PageRank向量作為參數(shù)α的函數(shù)不會(huì)表現(xiàn)過于敏感，但是當(dāng)α→1時(shí)，，這一上界的價(jià)值也將逐漸降低；當(dāng)α值較大時(shí)，若πT（α）是矩陣G（α）=αS＋（1＋α）eνT所對(duì)應(yīng)的PageRank向量，則，該導(dǎo)數(shù)的極限值為：（I-S）#，其中（*）#表示矩陣的群逆，所有隨機(jī)矩陣的主特征值λ1=1均為半簡的。因此，當(dāng)S通過相似變換被簡化為若當(dāng)形時(shí)，所得結(jié)果為，1?σ（C）? （I-S）=X和（I-S#）=X。矩陣C由與特征值λk≠1相對(duì)應(yīng)的若當(dāng)塊J.組成，在（I-C）-1中對(duì)應(yīng)的塊為（I-J.）-1。由此分析可知，當(dāng)α→1時(shí)，πT（α）的敏感性由（I-S）#中元素的大小所決定。由于‖（I-S）#‖≤K（X）‖（I-C）-1‖，其中，K（X）為X的條件數(shù)，當(dāng)α→1時(shí)πT（α）的敏感性主要由‖（I-C）-1‖的大小所決定，而‖（I-C）-1‖由|1-λ2|-1所決定，可知，當(dāng)λ2越接近于λ1=1，則當(dāng)α→1時(shí)，πT（α）就越敏感。綜上分析，對(duì)于小的α值，PageRank對(duì)α的微小變動(dòng)不敏感；當(dāng)α值變大時(shí)，PageRank對(duì)α的微小擾動(dòng)變得越來越敏感；對(duì)于接近于1的α值，PageRank對(duì)α值的微小改變非常敏感。

1.2H的敏感性分析

針對(duì)超鏈接矩陣H的傳統(tǒng)算法是采用平均加權(quán)的方式以產(chǎn)生H矩陣的元素，即一個(gè)頁面的所有出鏈均以隨機(jī)上網(wǎng)者的鏈接概率的形式被賦予相等的權(quán)重，但是這種方法的缺點(diǎn)在于對(duì)隨機(jī)上網(wǎng)者的描述方式不夠準(zhǔn)確，因?yàn)橄啾扔陔S機(jī)選擇一個(gè)出鏈頁面并超鏈接到新的頁面，上網(wǎng)者可能會(huì)根據(jù)許多有價(jià)值的內(nèi)容或者有關(guān)的描述性錨文本來選擇出鏈并連接到新的頁面[4-5]。因此，相比于簡短的廣告頁面，智能上網(wǎng)者更可能轉(zhuǎn)跳到內(nèi)容充實(shí)的頁面，因此對(duì)這些內(nèi)容更加充實(shí)的頁面應(yīng)該賦予更高的概率權(quán)值?？梢酝ㄟ^將與頁面中的出鏈位置、與出鏈關(guān)聯(lián)的錨文本長度、由鏈接相連的兩個(gè)文檔之間的內(nèi)容相似性等有關(guān)的度量加以結(jié)合的方法來填入原始超鏈接矩陣H中的元素，其中，利用訪問日志以發(fā)現(xiàn)上網(wǎng)者的瀏覽習(xí)慣和喜好是填充H矩陣中元素的有效方法之一[6]，例如網(wǎng)絡(luò)管理員通過分析上網(wǎng)者的訪問日發(fā)現(xiàn)其正停留在頁面P1上并且連接到P2的可能性是連接到P3的可能性的兩倍。此時(shí)H矩陣中第1行的出鏈概率便可得到相應(yīng)調(diào)整。不同的方法調(diào)整后的矩陣如下：（1）使用傳統(tǒng)的超鏈接矩陣使用隨機(jī)上網(wǎng)者方法描述：

（2）當(dāng)對(duì)頁面P1應(yīng)用智能上網(wǎng)者時(shí)描述為：

但是，不管H是如何產(chǎn)生的，對(duì)馬爾可夫鏈而言，關(guān)鍵在于所得矩陣要接近于隨機(jī)矩陣，對(duì)應(yīng)于非懸掛結(jié)點(diǎn)的行的元素之和應(yīng)等于1，而對(duì)應(yīng)于懸掛結(jié)點(diǎn)的行的元素之和應(yīng)等于0[7]。如果這點(diǎn)不成立，那么需要對(duì)各行進(jìn)行歸一化處理。

針對(duì)πT對(duì)于H中的變化的敏感性，傳統(tǒng)擾動(dòng)分析指出，對(duì)于轉(zhuǎn)移矩陣為P而穩(wěn)態(tài)向量為πT的馬爾可夫鏈，πT對(duì)于P中的擾動(dòng)敏感|λ2（P）|≈1；對(duì)于PageRank的敏感性分析，當(dāng)|λ2（G）|≤α?xí)r，對(duì)于一個(gè)可約的 S，可知 λ2（G）|=α。當(dāng)α→1時(shí)，PageRank向量將對(duì)G中的變化越來越敏感，此時(shí)G與α、H和νT有關(guān)；對(duì)于單獨(dú)分析超鏈接矩陣H的結(jié)構(gòu)變化對(duì)PageRank向量的敏感性的影響，可以通過計(jì)算導(dǎo)數(shù)：

分析該式可知，當(dāng)α→1時(shí)，（I-αS）-1中的元素趨向于無窮大，PageRank向量對(duì)于網(wǎng)絡(luò)圖結(jié)構(gòu)中的微小變化也更為敏感。同時(shí)，與改變一個(gè)不重要的頁面相比，增加一條連接或增加某個(gè)重要頁面中鏈接的權(quán)重，對(duì)PageRank向量的敏感性也具有更大影響[8]。

1.3νT的敏感性分析

跳轉(zhuǎn)矩陣E是PageRank模型最早的修改之一，使用eνT作為跳轉(zhuǎn)矩陣，其中νT＞0是一個(gè)概率向量，使用νT代替1/neT意味著該跳轉(zhuǎn)概率不再是均勻分布。由于νT是所有元素均為正的概率向量，因此每個(gè)結(jié)點(diǎn)仍然直接與其他所有結(jié)點(diǎn)相連，即為G素矩陣，由此可知PageRank向量是該馬爾可夫鏈存在的唯一一個(gè)穩(wěn)態(tài)向量。每當(dāng)上網(wǎng)者發(fā)生跳轉(zhuǎn)時(shí)，其將根據(jù)中所給出的概率分布跳到下一個(gè)頁面，當(dāng)G=αS＋（1-α）eνT時(shí)，冪法變?yōu)椋?/p>

該式將每次迭代中所加的常數(shù)向量由eT/n變?yōu)棣蚑，但是冪法的優(yōu)點(diǎn)和結(jié)論繼續(xù)保持，即漸進(jìn)收斂率、稀疏向量-矩陣乘法、最小存儲(chǔ)與易于編程等性質(zhì)均得到保留。與此同時(shí)，不同個(gè)性化向量將給出不同的PageRank排名，即 πT（νT）是νT的函數(shù)[9]。但是，個(gè)性化向量νT使得與查詢無關(guān)、與用戶無關(guān)的PageRank變得依賴于用戶，并且計(jì)算負(fù)擔(dān)也增加了。

分析個(gè)性化向量νT的影響需要計(jì)算πT對(duì)νT的導(dǎo)數(shù)：

其中，D是懸掛結(jié)點(diǎn)集合，分析該式可知，πT對(duì)νT的敏感性包括：（1）該敏感性依賴于α，當(dāng)α→1時(shí)，（I-αS）-1中的元素趨向于無窮大，因此，可得當(dāng)α→1時(shí)，πT逐漸敏感；（2）如果懸掛結(jié)點(diǎn)包括PageRank中的較大部分，則PageRank向量對(duì)于個(gè)性化向量νT中的變化將更為敏感，由此可知，如果懸掛結(jié)點(diǎn)集較為重要，那么隨機(jī)上網(wǎng)者將更頻繁地對(duì)其進(jìn)行重復(fù)訪問，從而也更頻繁地依照νT中給出的跳轉(zhuǎn)概率以改變位置[10]。因此，隨機(jī)上網(wǎng)者的行動(dòng)以及由此得出的PageRank值的分布對(duì)于跳轉(zhuǎn)向量νT中的變化具有敏感性。

2　HITS的敏感性分析

HITS利用萬維網(wǎng)的超鏈接結(jié)構(gòu)來生成網(wǎng)頁的歡迎度評(píng)分，相比于PageRank，HITS給出了兩個(gè)評(píng)分，且與查詢相關(guān)。HITS從權(quán)威和樞紐的角度看待網(wǎng)頁，每個(gè)頁面都是某個(gè)權(quán)威的某種度量，也是某個(gè)樞紐的某種度量[11]。當(dāng)HITS領(lǐng)域圖的鄰接矩陣L發(fā)生了改變并產(chǎn)生了新的矩陣時(shí)，分析權(quán)威向量和樞紐向量的敏感性：令E為擾動(dòng)矩陣，可得=LTL+E，當(dāng)λ1是一個(gè)單根時(shí)，，相比于新舊權(quán)威向量x和之間的差別的長度，更為合適的方法是考察新舊權(quán)威向量x和之間的角度，因?yàn)樵贖ITS程序中，權(quán)威向量被歸一化，同時(shí)，元素排名十分重要。兩個(gè)主特征向量之間的間隔，決定了HITS的敏感性[12-13]。如果σ=λ1-λ2較大，則權(quán)威向量對(duì)于網(wǎng)絡(luò)圖中的小幅改變不敏感[14-15]；如果σ=λ1-λ2較小，則該向量可能非常敏感。

3　結(jié)束語

對(duì)網(wǎng)頁排名算法的敏感性分析的研究已經(jīng)展現(xiàn)其有效性，研究方法和思路更加追求創(chuàng)新和效率，但是無論比例參數(shù)α、超鏈接矩陣H和個(gè)性化向量νT對(duì)PageRank向量的敏感性分析或者HITS的敏感性分析，目前的研究都還不盡完善。由于不同算法給出的矩陣彼此之間存在明顯差別，因此未來的研究工作可以將多個(gè)相互獨(dú)立的算法的結(jié)果和參數(shù)的范圍條件影響結(jié)果加以融合。

文獻(xiàn)綜述：

[1]楊博 等.基于超鏈接多樣性分析的新型網(wǎng)頁排名算法[J].計(jì)算機(jī)學(xué)報(bào),2014（4）：883-847.

[2]Sergey Brin and Lawrence Page.The anatomy of a largescale hypertextual Web search engine.Computer Networks and ISDN Systems，1998（33）:105-118.

[3]Sergey Brin and Lawrence Page and Terry Winograd.The PageRank citation ranking:Bringing order to the Web[D]. Tech-nical Report 1999-0121，Computer Science Department，Stan-ford University，1999.

[4]Krishna Bharat and Farzin Maghoul.The term vector database:Fast access to indexing terms for webpages.Computer Networks，2010，244-257.

[5]Mattew Richardson and Petro Domingos.The intelligent surfer:Probabilisticcombinationoflinkandcontent information in PageRank.Advances in Neural Information Processing System.2012，144-148.

[6]Ricardo Baeza-Yates and Emilio Davis.Web page ranking using link attributes.In The Thirteen International World Wide Web Conference，pages 328-330，New York，2004. ACM Press.

[7]Michael W.Berry and Murray Browne.Understanding Search Engines:Mathematical Modeling and Text Retrieval.SIAM，Philadelphia，2nd edition，2005.

[8]John A.Tomlin.A new paradigm for ranking pages on the World Wide Web.In The Twelfth International World Wide Web Conference，New York 2003.ACM Press.

[9]Kristen Thorson.Modeling the Web and the computation of PageRank.Undergraduate thesis，Hollins University，2004.

[10]Sergey Brin and Bajeev Motwani.What can you do with a Web in your pocket Data Engineering Bulletin，1998：36-56.

[11]Ayman Farahat and Thomas Lofaro.Authority rankings from HITS，PageRank and SALSA:Existence，uniqueness，and effect of initialization.SIAM Journal on Scientific Computing，2006：1180-1200.

[12]Andrew Y.Ng，Alice X and Michael I.Jordan.Stable algorithms for link analysis.In Proceedings of the 24th Annual International ACM AIGIR Conference.ACM，2001.

[13]James H.Aggregation of variables in dynamic systems. Information Processing and Management，2013：111-139.

[14]Carl D.Meyer.Stochastic complementation，uncoupling Markov chains and the theory of nearly reducible systems. SIAM Review，1989：240-270.

[15]William J.Stewart.Introduction to the Numerical of Markov Chains.Princeton University Press，2004.

The sensitivity analysis based on Web page ranking algorithm

MA Li-na1，ZHANG Jia-jian2，LI Li-wei2
（1.Business School of Hohai University，Nanjing 210000，China；2.Jiangsu Posts&Telecommunication Planning and Designing Institute Co.Ltd,Nanjing 210019，China）

The sensitivity analysis of Web page ranking algorithm can achieve a further understanding on principle and condition scope of the score of welcome degree which the algorithm model given.Different changes in parameters will result in different degrees of sensitivity.Based on this problem,this article discusses the sensitivity of PageRank and HITS by mathematical content analysis of the algorithm.On the basis of analyzing the dependence of matrix G on the ratio parameter α, hyperlink matrix H and personalized vector νT,this article analyzes the influence of three specific parameters on PageRank vector.Finally,it considers the sensitivity of HITS.

PageRank；HITS；sensitivity analysis；scale parameter α；hyperlinks matrix H；personalized vector νT

TN0

A

1674－6236（2016）22-0077-03

2016-03-15稿件編號(hào)：201603173

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

馬莉娜（1987—），女，江蘇南京人，碩士。研究方向：企業(yè)管理、技術(shù)經(jīng)濟(jì)。