基于網頁排名算法的敏感性分析

馬莉娜，張家健，李立維

（1.河海大學 商學院，江蘇 南京　210000；2.江蘇省郵電規劃設計院有限公司 江蘇 南京210019）

基于網頁排名算法的敏感性分析

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

（1.河海大學 商學院，江蘇 南京210000；2.江蘇省郵電規劃設計院有限公司 江蘇 南京210019）

對網頁排名算法的敏感性分析，能夠進一步了解關于算法模型所給出的歡迎度評分的原理和條件范圍。基于參數的不同變化會導致不同程度的敏感性這一問題，本文通過對算法的數學內容分析，研究PageRank和HITS的敏感性問題。在分析矩陣G對于比例參數α、超鏈接矩陣H和個性化向量vT的依賴性的基礎上，分析了3個特定參數對PageRank向量的影響，最后，對HITS的敏感性進行分析。

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

作為搜索引擎的核心部件，網頁排名算法決定了搜索到的相關結果以何種順序呈現給用戶，其性能的優劣將會直接影響搜索引擎的服務質量和用戶的搜索體驗[1]。對網頁排名算法的敏感性分析，能夠進一步了解關于算法模型所給出的歡迎度評分的原理和條件范圍，同樣可以通過它的敏感性進一步了解網頁排名算法模型的“個性”。

1　PageRank的敏感性分析

1.1α的敏感性分析

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

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

1.2H的敏感性分析

針對超鏈接矩陣H的傳統算法是采用平均加權的方式以產生H矩陣的元素，即一個頁面的所有出鏈均以隨機上網者的鏈接概率的形式被賦予相等的權重，但是這種方法的缺點在于對隨機上網者的描述方式不夠準確，因為相比于隨機選擇一個出鏈頁面并超鏈接到新的頁面，上網者可能會根據許多有價值的內容或者有關的描述性錨文本來選擇出鏈并連接到新的頁面[4-5]。因此，相比于簡短的廣告頁面，智能上網者更可能轉跳到內容充實的頁面，因此對這些內容更加充實的頁面應該賦予更高的概率權值。可以通過將與頁面中的出鏈位置、與出鏈關聯的錨文本長度、由鏈接相連的兩個文檔之間的內容相似性等有關的度量加以結合的方法來填入原始超鏈接矩陣H中的元素，其中，利用訪問日志以發現上網者的瀏覽習慣和喜好是填充H矩陣中元素的有效方法之一[6]，例如網絡管理員通過分析上網者的訪問日發現其正停留在頁面P1上并且連接到P2的可能性是連接到P3的可能性的兩倍。此時H矩陣中第1行的出鏈概率便可得到相應調整。不同的方法調整后的矩陣如下：（1）使用傳統的超鏈接矩陣使用隨機上網者方法描述：

（2）當對頁面P1應用智能上網者時描述為：

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

針對πT對于H中的變化的敏感性，傳統擾動分析指出，對于轉移矩陣為P而穩態向量為πT的馬爾可夫鏈，πT對于P中的擾動敏感|λ2（P）|≈1；對于PageRank的敏感性分析，當|λ2（G）|≤α時，對于一個可約的 S，可知 λ2（G）|=α。當α→1時，PageRank向量將對G中的變化越來越敏感，此時G與α、H和νT有關；對于單獨分析超鏈接矩陣H的結構變化對PageRank向量的敏感性的影響，可以通過計算導數：

分析該式可知，當α→1時，（I-αS）-1中的元素趨向于無窮大，PageRank向量對于網絡圖結構中的微小變化也更為敏感。同時，與改變一個不重要的頁面相比，增加一條連接或增加某個重要頁面中鏈接的權重，對PageRank向量的敏感性也具有更大影響[8]。

1.3νT的敏感性分析

跳轉矩陣E是PageRank模型最早的修改之一，使用eνT作為跳轉矩陣，其中νT＞0是一個概率向量，使用νT代替1/neT意味著該跳轉概率不再是均勻分布。由于νT是所有元素均為正的概率向量，因此每個結點仍然直接與其他所有結點相連，即為G素矩陣，由此可知PageRank向量是該馬爾可夫鏈存在的唯一一個穩態向量。每當上網者發生跳轉時，其將根據中所給出的概率分布跳到下一個頁面，當G=αS＋（1-α）eνT時，冪法變為：

該式將每次迭代中所加的常數向量由eT/n變為νT，但是冪法的優點和結論繼續保持，即漸進收斂率、稀疏向量-矩陣乘法、最小存儲與易于編程等性質均得到保留。與此同時，不同個性化向量將給出不同的PageRank排名，即 πT（νT）是νT的函數[9]。但是，個性化向量νT使得與查詢無關、與用戶無關的PageRank變得依賴于用戶，并且計算負擔也增加了。

分析個性化向量νT的影響需要計算πT對νT的導數：

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

2　HITS的敏感性分析

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

3　結束語

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

文獻綜述：

[1]楊博 等.基于超鏈接多樣性分析的新型網頁排名算法[J].計算機學報,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稿件編號：201603173

江蘇省社科聯研究基金（201035）

馬莉娜（1987—），女，江蘇南京人，碩士。研究方向：企業管理、技術經濟。