基于隨機(jī)游動(dòng)的社會(huì)網(wǎng)絡(luò)個(gè)性化排名關(guān)鍵技術(shù)研究.pdf

1、隨著即時(shí)通信工具、微博、微信、論壇、博客、維基以及內(nèi)容共享的在線社交網(wǎng)絡(luò)的迅猛發(fā)展，人們獲取信息的方式已經(jīng)從簡(jiǎn)單的信息搜索和網(wǎng)頁(yè)瀏覽轉(zhuǎn)向網(wǎng)上社會(huì)關(guān)系的構(gòu)建與維護(hù)，并且基于社會(huì)關(guān)系的信息共享、交流和創(chuàng)造。如今，各式各樣的在線社交網(wǎng)絡(luò)已經(jīng)深入到了人們生活中的方方面面。社會(huì)網(wǎng)絡(luò)是一種由個(gè)人或組織以及他們之間的聯(lián)系構(gòu)成的復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)。除了在線社交網(wǎng)絡(luò)以外，Web網(wǎng)絡(luò)、文獻(xiàn)引用網(wǎng)絡(luò)，甚至基因網(wǎng)絡(luò)等都可以看成社會(huì)網(wǎng)絡(luò)。在社會(huì)網(wǎng)絡(luò)中，個(gè)性化排名主要

2、用于識(shí)別網(wǎng)絡(luò)中相對(duì)重要的節(jié)點(diǎn)，對(duì)于網(wǎng)絡(luò)的鏈接預(yù)測(cè)，個(gè)性化搜索和推薦都有重要的研究意義。本研究主要內(nèi)容包括：
　　⑴針對(duì)社會(huì)網(wǎng)絡(luò)的數(shù)據(jù)海量性，在轉(zhuǎn)移概率矩陣?yán)碚摷版準(zhǔn)诫S機(jī)游動(dòng)方法的基礎(chǔ)上，提出了一種MapReduce環(huán)境下的基于二叉樹(shù)隨機(jī)游動(dòng)的并行化節(jié)點(diǎn)個(gè)性化排名方法。首先，建立二叉樹(shù)隨機(jī)游動(dòng)模型。接著，基于該模型以每個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)生成一系列相互獨(dú)立的二叉樹(shù)陣列。最后，在MapReduce環(huán)境下，并行地實(shí)現(xiàn)相對(duì)于某根節(jié)點(diǎn)的迭代排名算

3、法，不同節(jié)點(diǎn)在同一根節(jié)點(diǎn)的二叉樹(shù)中出現(xiàn)的比例便是相應(yīng)節(jié)點(diǎn)相對(duì)于該根節(jié)點(diǎn)的排名值。理論分析表明，與鏈?zhǔn)诫S機(jī)游動(dòng)節(jié)點(diǎn)個(gè)性化排名算法相比，本文提出的算法在排名精度相同的情況下，具有迭代次數(shù)少、輸入輸出數(shù)據(jù)量小和運(yùn)算速度快等明顯優(yōu)勢(shì)。節(jié)點(diǎn)規(guī)模為百萬(wàn)量級(jí)的社會(huì)網(wǎng)絡(luò)實(shí)驗(yàn)驗(yàn)證了本算法的有效性。
　?、漆槍?duì)移動(dòng)社會(huì)網(wǎng)絡(luò)的位置動(dòng)態(tài)性，提出了一種基于鏈?zhǔn)诫S機(jī)游動(dòng)的面向位置屬性的個(gè)性化排名方法。首先，在移動(dòng)社會(huì)網(wǎng)絡(luò)中，篩選出那些包含指定位置的節(jié)點(diǎn)及其鄰

4、居節(jié)點(diǎn)，以及節(jié)點(diǎn)間的相互聯(lián)系，得到一個(gè)子網(wǎng)絡(luò)。接著，在子網(wǎng)絡(luò)中引入反映節(jié)點(diǎn)熱度的權(quán)威值和反映節(jié)點(diǎn)通暢程度的樞紐值，基于鏈?zhǔn)诫S機(jī)游動(dòng)方法在子網(wǎng)絡(luò)中對(duì)這兩個(gè)相互影響的值進(jìn)行統(tǒng)計(jì)分析，用最終計(jì)算出的權(quán)威值來(lái)確定該節(jié)點(diǎn)在該指定位置下的排名值。進(jìn)而，在某些不同的重要位置下進(jìn)行個(gè)性化排名并保存所有排名結(jié)果，便可以根據(jù)個(gè)性化節(jié)點(diǎn)位置屬性的動(dòng)態(tài)變化查詢到相對(duì)于該位置下所有節(jié)點(diǎn)的排名值。最后，經(jīng)真實(shí)的社會(huì)網(wǎng)絡(luò)數(shù)據(jù)實(shí)驗(yàn)表明，與著名的HubRank算法相比，

5、本文提出的方法具有查詢命中率高和執(zhí)行速度快等優(yōu)點(diǎn)。
　?、翘岢隽艘环N基于鏈?zhǔn)诫S機(jī)游動(dòng)的反向影響力排名方法。反向影響力指其他節(jié)點(diǎn)對(duì)某個(gè)性化節(jié)點(diǎn)的影響力。由于社會(huì)網(wǎng)絡(luò)通常存在大網(wǎng)絡(luò)小世界現(xiàn)象，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)往往都可以在很少步長(zhǎng)內(nèi)（例如6步）到達(dá)任一節(jié)點(diǎn)。根據(jù)這一現(xiàn)象，在有向的社會(huì)網(wǎng)絡(luò)中，以其他節(jié)點(diǎn)為初始點(diǎn)進(jìn)行鏈?zhǔn)诫S機(jī)游動(dòng)，用每個(gè)節(jié)點(diǎn)在有限步長(zhǎng)內(nèi)到達(dá)個(gè)性化節(jié)點(diǎn)的概率之和表示該節(jié)點(diǎn)相對(duì)于個(gè)性化節(jié)點(diǎn)的反向影響力，本文提出了一種基于鏈?zhǔn)诫S機(jī)

6、游動(dòng)的反向影響力近似計(jì)算方法。通過(guò)對(duì)真實(shí)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)的鏈接預(yù)測(cè)實(shí)驗(yàn)，驗(yàn)證了本文提出的方法的有效性。
　?、忍岢隽艘环N基于鏈?zhǔn)诫S機(jī)游動(dòng)的用戶對(duì)商品的社會(huì)推薦方法。在社會(huì)推薦系統(tǒng)中，關(guān)鍵是要確定其他相關(guān)用戶相對(duì)于某個(gè)性化用戶的不同的推薦權(quán)重。為此，首先將用戶之間的社會(huì)網(wǎng)絡(luò)與用戶對(duì)商品的評(píng)價(jià)網(wǎng)絡(luò)中的相同的用戶節(jié)點(diǎn)進(jìn)行合并，從而構(gòu)成一個(gè)社會(huì)推薦圖，接著在社會(huì)推薦圖上從個(gè)性化用戶出發(fā)，通過(guò)反復(fù)進(jìn)行用戶-商品-用戶的鏈?zhǔn)诫S機(jī)游動(dòng)，以不同用戶出