網(wǎng)絡(luò)結(jié)構(gòu)與效應(yīng)原理：第14章 網(wǎng)絡(luò)信息的鏈接分析

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

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

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

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

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

320麥當(dāng)勞

＊

16五方院＊

＊215俏江南

＊

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

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

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