網(wǎng)絡結構與效應原理：第14章 網(wǎng)絡信息的鏈接分析

網(wǎng)絡信息的鏈接分析

現(xiàn)代搜索引擎的兩方面核心技術之一（以第14章為基礎）12搜索引擎關心的基本問題計算機顯示屏一次只能顯示5-6個結果，典型搜索引擎掌握的網(wǎng)頁超過10億對用戶提交的一個查詢，如何從這種海量網(wǎng)頁集合中將最可能滿足用戶需求的少數(shù)幾個結果找出來，展現(xiàn)在計算機顯示屏上？“最可能滿足”的多義性同一個查詢，不同的需求（蘋果，病毒等）；不同的查詢，相同的需求（電腦，計算機等）3傳統(tǒng)信息檢索技術的要點

（informationretrieval，IR）基于詞語之間的相關性（relevance）similarity(q,d)≈Σscore(d,term)傳統(tǒng)應用背景文檔集合：圖書，規(guī)范的文獻查

詢：主題詞，關鍵詞查詢意圖：獲取與查詢詞有關的書籍和文章用

戶：圖書管理人員“查詢目標包含查詢詞”是一個合理假設在形成查詢詞的時候就有這樣的潛意識4現(xiàn)在查找學術文獻有類似預期但人們在網(wǎng)絡上不光是要找“文獻”，而是多方面意義的“信息”例如，人們給出“北京大學”查詢詞，多數(shù)會有什么預期？查詢“大學”呢？（意圖會相當多樣化）5為什么能恰到好處？主頁放在最前面，一定不是因為其中包含許多“北京大學”字樣很可能是由于許多包含“北京大學”字樣的網(wǎng)頁指向它利用鏈接中隱含的信息6這個兩個結果哪一個較好？7有效利用鏈接關系蘊含的信息，是搜索引擎超越傳統(tǒng)信息檢索系統(tǒng)、技術進步的最重要標志W(wǎng)ebpage之間的鏈接有兩層含義：關系，描述8餐館推薦問題甲乙丙丁新辣道＊＊＊321海底撈＊＊＊

320麥當勞

＊

16五方院＊

＊215俏江南

＊

＊2138667不能完全區(qū)分看推薦人的“水平”完全區(qū)分開來9反復改進原理（例）假設查詢詞“newspaper”左邊是與“newspaper”字面上相關的網(wǎng)頁。右邊是它們所指向的網(wǎng)頁，得到的“票數(shù)”表示一定的認可度10反復改進原理（續(xù)）

（principleofrepeatedimprovement）也可以反過來評估“推薦者”的分量然后可以在考慮推薦者分量的情況下重新評估網(wǎng)站相對于“newspaper”的重要性（相當于加權評分）11反復改進原理這個過程可以反復進行下去12網(wǎng)頁的“中樞”與“權威”性萬維網(wǎng)中一篇網(wǎng)頁的兩面屬性。觀念：被很多網(wǎng)頁指向：權威性高，認可度高指向很多網(wǎng)頁：中樞性強HITS算法：計算網(wǎng)頁的權威值（auth）和中樞值（hub）Hyperlink-InducedTopicSearch13auth(p)和

hub(p)的計算方法輸入：一個有向圖初始化：對于每一個節(jié)點p，權威值auth(p)=1，中樞值hub(p)=1利用中樞值更新權威值對于每一個節(jié)點p，讓auth(p)等于指向p的所有節(jié)點q的hub(q)之和利用權威值更新中樞值對于每一個節(jié)點p，讓hub(p)等于p指向的所有節(jié)點q的auth(q)之和重復上述兩步若干（k）次在搜索引擎領域，auth值或hub值高的網(wǎng)頁，有時分別稱為“權威網(wǎng)頁”和“中樞網(wǎng)頁”。一篇網(wǎng)頁可以兼具二者。14歸一化與極限數(shù)值隨迭代次數(shù)遞增Auth和hub值的意義在于相對大小在每一輪結束后做歸一化：值／總和歸一化結果隨迭代次數(shù)趨向于一個極限相繼兩次迭代的值不變極限與初值無關，即存在“均衡”15PageRank：節(jié)點的一種重要性測度搜索引擎形成查詢結果網(wǎng)頁排序的重要參數(shù)基本要領：每一個節(jié)點將自己的值均分給出向鄰居每個節(jié)點將從鄰居收到的值加起來多次迭代！16上圖的算例經(jīng)過約70次迭代，最后收斂到：A=0.615,B=0.923,C=D=1.23117PageRank基本算法描述輸入：一個有n個節(jié)點的網(wǎng)絡（有向圖），設所有節(jié)點的PageRank初始值為1/n。選擇操作的步驟數(shù)k對PageRank做k次更新操作，每次使用以下規(guī)則：每個節(jié)點將自己當前的PageRank值通過出向鏈接均分傳遞給所指向的節(jié)點若沒有出向鏈接，則認為傳遞給自己（或者說保留）每個節(jié)點以從入向鏈接獲得的（包括可能自傳的）所有值之和更新它的PageRank18一個計算網(wǎng)頁排名的實例每個節(jié)點的初值都是1/8最后收斂結果見下圖19PageRank基本算法在某些結構上表現(xiàn)很不好PageRank算法不象HITS算法那樣需要歸一化，但有新問題F和G兩個節(jié)點顯得很“自私”：吸收別人的價值，但不向外傳導致它們最后各自1/2，其他人都0這也顯示了共謀（colluding）制造垃圾網(wǎng)頁的一個原理20PageRank值很快集中到F和G21PageRank的同比縮減與統(tǒng)一補償規(guī)則同比縮減在每次運行基本PageRank更新規(guī)則后，將每一節(jié)點的PageRank值都乘以一個小于1的比例因子s，0<s<1，經(jīng)驗值在0.8-0.9之間。統(tǒng)一補償在每一節(jié)點的PageRank值上統(tǒng)一加上(1-s)/n。這樣，既維持了“ΣPR=1”的性質，也防止了PR值不恰當?shù)丶械絺€別節(jié)點。2223隨機游走：PageRank的另一種等價理解想象一個人從一篇隨機選擇的網(wǎng)頁開始，隨機選擇其中的鏈接瀏覽到下一篇網(wǎng)頁，并不斷如此進行，稱為“隨機游走”?？紤]一篇網(wǎng)頁X，問：經(jīng)過k步隨機游走到達X的概率是多少？可以證明：到達X的概率等于運行PageRank基本算法k步得到的值。隨機游走概念稍加修改也可以和同比縮減統(tǒng)一補償?shù)腜ageRank等價。24小結信息一旦刻畫成一種網(wǎng)絡，其中的信息經(jīng)常自然地隱含著一種“推薦”關系，人們可以利用這種關