基于PageRank算法的社交網(wǎng)絡(luò)意見領(lǐng)袖識別算法

◆馬玉燃

基于PageRank算法的社交網(wǎng)絡(luò)意見領(lǐng)袖識別算法

◆馬玉燃

（貴州航天職業(yè)技術(shù)學(xué)院 貴州 553106）

PageRank算法[1]是目前被廣泛應(yīng)用的一種重要性的排序方法，它根據(jù)節(jié)點(diǎn)之間的鏈接結(jié)構(gòu)來給每個(gè)節(jié)點(diǎn)打分。本文在分析經(jīng)典PageRank算法平均分配權(quán)值缺點(diǎn)的基礎(chǔ)上，為網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)設(shè)置各自的權(quán)威度，并結(jié)合用戶瀏覽網(wǎng)頁的現(xiàn)實(shí)情況，使用戶可以根據(jù)主觀意向選擇節(jié)點(diǎn)對應(yīng)的鏈接，提出Au-2Step-PageRank（Authority-2Step-PageRank）算法。實(shí)驗(yàn)表明該算法可以更加準(zhǔn)確高效地挖掘有向社交網(wǎng)絡(luò)中的意見領(lǐng)袖。

PageRank算法；社交網(wǎng)絡(luò)；搜索引擎；PR值

1 引言

社交網(wǎng)絡(luò)是由個(gè)人以及群體構(gòu)成的由一個(gè)或多個(gè)因素關(guān)聯(lián)起來的一種社交結(jié)構(gòu)?；ヂ?lián)網(wǎng)空間為用戶產(chǎn)生新的社交方式提供了極大的可行性。1960年，社交網(wǎng)絡(luò)的概念第一次在美國伊利諾斯大學(xué)提出。之后，成立了第一個(gè)社交網(wǎng)站，即“Six Degrees.com”。如今，社交網(wǎng)絡(luò)受到極大的歡迎，它給用戶提供了大量的交流工具。無論是新成員的加入，還是成員之間建立新的聯(lián)系，整個(gè)社交網(wǎng)絡(luò)都會得到增長，社交網(wǎng)絡(luò)數(shù)據(jù)也在急劇膨脹。

在分析這些社交網(wǎng)絡(luò)的時(shí)候，在線社會網(wǎng)絡(luò)不斷發(fā)展，商業(yè)活動也逐漸進(jìn)入這個(gè)領(lǐng)域，如何更快更好地分析和識別社交網(wǎng)絡(luò)中的意見領(lǐng)袖，對廣告?zhèn)鞑?、市場營銷都有著極其重要的作用。在社交網(wǎng)絡(luò)中挖掘意見領(lǐng)袖，不僅可以挖掘出當(dāng)下的熱點(diǎn)信息，也可以用來對未來信息傳播的預(yù)測，對輿情監(jiān)測有著極為重要的意義。

2 PageRank算法及其改進(jìn)算法的研究

2.1 PageRank算法的研究現(xiàn)狀

隨著對排序算法的研究不斷加深，產(chǎn)生了許多對PageRank算法的改進(jìn)算法。受計(jì)算機(jī)象棋算法設(shè)計(jì)中一個(gè)很成功的策略：“多看幾步”的啟發(fā)，張麗[2]對PageRank算法進(jìn)行改進(jìn)并提出了N-StepPageRank算法，在計(jì)算網(wǎng)頁的轉(zhuǎn)移概率時(shí)利用了網(wǎng)頁N 步的鏈接信息，從而提高排名的精確度，但是N-StepPageRank與經(jīng)典PageRank之間的關(guān)系沒有顯示出來。

古文麗[3]等人對PageRank進(jìn)行的改進(jìn)同時(shí)解決了權(quán)威度和內(nèi)容相關(guān)行兩方面需求，更符合用戶的需求；蔣永輝[4]提出的NPRO算法提出半模糊核聚類方法引入樣本隸屬度概念，有效提高了訓(xùn)練精度和分類速度，但是設(shè)計(jì)的參數(shù)較多且不同環(huán)境下需要設(shè)置不同參數(shù)，參數(shù)的設(shè)定過程較為煩瑣。

趙亞娟[5]等人針對PageRank平均分配權(quán)值的問題對其進(jìn)行了改進(jìn)，根據(jù)“網(wǎng)頁質(zhì)量”對權(quán)值進(jìn)行分配，提高了信息獲取的準(zhǔn)確性，但是算法的復(fù)雜度明顯增加；王冬[6]等人同樣針對經(jīng)典PageRank平均分配權(quán)值的缺陷，提出了NDPagerank（Non-average distribution PageRank）算法，同時(shí)計(jì)算復(fù)雜度也有所增加。

本文重點(diǎn)針對經(jīng)典PageRank算法平均分配權(quán)值的缺點(diǎn)，在進(jìn)行權(quán)值分配時(shí)為每個(gè)節(jié)點(diǎn)賦予相應(yīng)的權(quán)威度，并且參照用戶實(shí)際操作情況，模擬用戶瀏覽網(wǎng)頁時(shí)可以根據(jù)主觀意向進(jìn)行選擇下一步操作，從而對網(wǎng)絡(luò)中的噪音信息進(jìn)行了有效的過濾。在此基礎(chǔ)上，參考N-StepPageRank算法提出了Au-2S-PageRank算法，解決了經(jīng)典PageRank算法因平均分配權(quán)值對結(jié)果造成的影響。

3 Au-2S-PageRank算法的提出

3.1 Au-PageRank（Authority-PageRank）算法

在此基礎(chǔ)上對經(jīng)典PageRank改進(jìn)后可以提高對網(wǎng)絡(luò)中節(jié)點(diǎn)排名的準(zhǔn)確性。

3.2 2S-PageRank（2Step-PageRank）算法

在現(xiàn)實(shí)中，用戶在瀏覽網(wǎng)頁時(shí)，通常可以根據(jù)鏈接顯示的文本信息和自己的主觀意向去判斷那個(gè)網(wǎng)頁更為重要或者更加符合自己的需求。因此假設(shè)用戶在進(jìn)行網(wǎng)頁的鏈接選擇時(shí)，可以看到鏈接到的網(wǎng)頁中的內(nèi)容，即用戶可以多看到一層網(wǎng)頁內(nèi)容，從而進(jìn)行選擇。如圖1所示。

圖1 2Step-PageRank圖示

在此基礎(chǔ)上計(jì)算出的概率轉(zhuǎn)移矩陣將會比經(jīng)典PageRank的轉(zhuǎn)移矩陣更加稀疏，在計(jì)算時(shí)可以加快收斂速度。

3.3 Au-2S-PageRank（Authority-2Step-PageRank）算法

結(jié)合以上兩種算法的思想，將網(wǎng)絡(luò)中節(jié)點(diǎn)的權(quán)威度和現(xiàn)實(shí)情況結(jié)合，使用戶可以在上網(wǎng)時(shí)多看一步，根據(jù)公式（2）（3）（4）提出Au-2S- PageRank算法，公式如下：

該算法考慮有向網(wǎng)絡(luò)中節(jié)點(diǎn)的權(quán)威度，并結(jié)合現(xiàn)實(shí)情況對pagerank算法進(jìn)行改進(jìn)，針對節(jié)點(diǎn)的PR值實(shí)現(xiàn)不平均分配，可以較好地區(qū)分網(wǎng)頁的重要性程度，并且在計(jì)算時(shí)可以加快收斂速度。

4 實(shí)驗(yàn)及結(jié)果

4.1 實(shí)驗(yàn)數(shù)據(jù)

為了驗(yàn)證改進(jìn)算法的效果，使用SNAP提供的推特ID數(shù)據(jù)模擬網(wǎng)頁之間的有向圖進(jìn)行試驗(yàn)。所使用的數(shù)據(jù)集基本情況如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)基本情況

4.2 算法執(zhí)行結(jié)果

經(jīng)過對數(shù)據(jù)的預(yù)處理，選取部分具有代表性的節(jié)點(diǎn)分別對經(jīng)典PageRank算法，Au-PageRank算法，2S-PageRank算法以及Au-2S-PageRank算法進(jìn)行測試。首先分別測試四種算法的運(yùn)行時(shí)間，分別選取節(jié)點(diǎn)數(shù)為1000、2000、3000、4000，結(jié)果如圖2所示。

由圖可知，四種算法的運(yùn)行時(shí)間都會隨著節(jié)點(diǎn)數(shù)目的增加而增加，但是其各自的運(yùn)行時(shí)間增加幅度不盡相同。其中PageRank、2S-PageRank和Au-2S-PageRank三種算法隨著節(jié)點(diǎn)數(shù)的增加，其運(yùn)行時(shí)間的增長情況較為接近，而Au-PageRank的運(yùn)行時(shí)間隨著節(jié)點(diǎn)數(shù)的增加大大延長；此外，改進(jìn)后的Au-2S-PageRank算法在節(jié)點(diǎn)增加時(shí)，運(yùn)行時(shí)間明顯優(yōu)于經(jīng)典PageRank算法，但是由于其中含有了Au-PageRank算法的思想，導(dǎo)致后續(xù)隨著節(jié)點(diǎn)的繼續(xù)增加運(yùn)行時(shí)間會高于2S-PageRank算法。

圖2 四種算法的運(yùn)行時(shí)間折線圖

5 結(jié)論

本文在分析經(jīng)典pagerank算法缺點(diǎn)的基礎(chǔ)上，考慮有向網(wǎng)絡(luò)中節(jié)點(diǎn)的權(quán)威度，并結(jié)合現(xiàn)實(shí)情況對pagerank算法進(jìn)行改進(jìn)，針對節(jié)點(diǎn)的PR值實(shí)現(xiàn)不平均分配，可以較好地區(qū)分節(jié)點(diǎn)的重要性程度。實(shí)驗(yàn)表明改進(jìn)后的Au-2S-PageRank算法在運(yùn)行時(shí)間和準(zhǔn)確性兩方面優(yōu)于經(jīng)典PageRank算法。Au-2S-PageRank是針對經(jīng)典PageRank算法在分配權(quán)值時(shí)進(jìn)行平均分配的缺點(diǎn)進(jìn)行的改進(jìn)，對于其PageRank他方面的缺點(diǎn)并未涉及，因此有待于日后進(jìn)一步研究改進(jìn)。

[1]Sergey Brin，Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine.[J]. Computer Networks，1998（30）.

[2]張麗. PageRank算法的改進(jìn)[J]. 科學(xué)技術(shù)與工程，2007（05）：673-677.

[3]古文麗，陳瑋，陳嬌，等. 一種改進(jìn)的PageRank算法[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用，2012（02）：214-217.

[4]蔣永輝，吳洪麗. 新的PageRank優(yōu)化算法[J]. 計(jì)算機(jī)工程與應(yīng)用，2012（06）：94-95+154.

[5]趙亞娟，閆娜. 一種基于網(wǎng)頁質(zhì)量的PageRank算法改進(jìn)分析[J]. 電腦知識與技術(shù)，2014（27）：6365-6366+6368.

[6]王冬，雷景生. 一種基于PageRank的頁面排序改進(jìn)算法[J]. 微電子學(xué)與計(jì)算機(jī)，2009（04）：210-213.