鄭孝遙，楊文建，鮑 煜，羅永龍

（安徽師范大學(xué)數(shù)學(xué)計算機科學(xué)學(xué)院，安徽 蕪湖241003）

1 引言

以用戶為中心的社交網(wǎng)絡(luò)已成為互聯(lián)網(wǎng)的一大發(fā)展趨勢，并成為人們分享、獲取和傳播信息的重要渠道。社交網(wǎng)絡(luò)是以計算機網(wǎng)絡(luò)為基礎(chǔ)，建立一個人與人之間相互了解的網(wǎng)絡(luò)結(jié)構(gòu)［1］。社交網(wǎng)絡(luò)中的節(jié)點影響力一直是一個重要的研究內(nèi)容，其在社會輿論傳播和導(dǎo)向、群體行為形成和發(fā)展等方面都具有重要作用［2］。隨著社交網(wǎng)絡(luò)中用戶規(guī)模呈指數(shù)級增長，節(jié)點影響力度量的精確性和計算效率成為一個關(guān)鍵問題［3，4］。

目前，國內(nèi)外對社交網(wǎng)絡(luò)中節(jié)點影響力度量方法的研究主要有三種［5～7］：

（1）基于節(jié)點度的度量方法。在該類方法中，以節(jié)點的度作為評判標(biāo)準(zhǔn)，對節(jié)點影響力進行量化，但其只考慮了鄰居節(jié)點對當(dāng)前節(jié)點影響力的貢獻，忽略了節(jié)點影響力傳播路徑上其它節(jié)點對其的影響，導(dǎo)致影響力度量不夠準(zhǔn)確［8］。

（2）基于最短路徑的度量方法。該方法主要包括緊密中心度和介數(shù)中心度兩種度量方法［9］。緊密中心度考慮了節(jié)點消息傳播的速度，節(jié)點傳播速度越快，節(jié)點影響力越高。介數(shù)中心度考慮了節(jié)點在網(wǎng)絡(luò)中所處位置的重要性，認為節(jié)點位置越重要，消息通過其的概率越高，其影響力越大。但是，由于該類方法均需要花費最低O（cne）（n＝|V|，e＝|E|，c是趨近于2的常數(shù)）的時間計算最短路徑，因此時間效率太低。

（3）基于隨機游走的度量方法，包括特征向量中心度、Katz中心度、PageRank等［10］。特征向量中心度考慮鄰接節(jié)點影響力，將鄰接節(jié)點影響力的線性和作為當(dāng)前節(jié)點影響力判定的依據(jù)。Katz中心度考慮當(dāng)前節(jié)點的隨機游走路徑，依據(jù)隨機游走路徑上的節(jié)點影響力加以懲罰得出當(dāng)前節(jié)點影響力。PageRank算法考慮節(jié)點的數(shù)量和質(zhì)量，每個節(jié)點的影響力均在網(wǎng)絡(luò)中均勻流動，最終以迭代收斂值作為節(jié)點的影響力權(quán)值，但當(dāng)節(jié)點較多時迭代計算代價較高。

傳統(tǒng)的社交網(wǎng)絡(luò)影響力度量方法由于計算復(fù)雜度高，已不能適應(yīng)當(dāng)前社交網(wǎng)絡(luò)的發(fā)展需求，隨著大數(shù)據(jù)技術(shù)的發(fā)展，如何在海量的社交網(wǎng)絡(luò)數(shù)據(jù)中快速準(zhǔn)確地計算和分析出用戶節(jié)點的影響力是一個亟待解決的研究課題。

針對上述三種主要方法中存在的度量不準(zhǔn)確、計算復(fù)雜度高等問題，本文提出一種基于隨機游走的分布式PageRank算法，本文稱為Reverse PageRank。經(jīng)過在公開數(shù)據(jù)集的實驗仿真，驗證了該算法在迭代次數(shù)較少時具有較好的精確度和時間性能。

2 相關(guān)研究

由于PageRank算法能夠較準(zhǔn)確地度量社交網(wǎng)絡(luò)節(jié)點的全局影響力，因此基于PageRank的影響力度量方法越來越受重視。本節(jié)主要介紹兩種典型的隨機游走PageRank算法：傳統(tǒng)的隨機游走算法［11］和Fast PageRank算法［5］。

2.1 傳統(tǒng)隨機游走PageRank算法

考慮用戶在瀏覽網(wǎng)頁時，會以某個概率1－ε（ε＝0.15）沿著網(wǎng)頁中的鏈接訪問網(wǎng)頁，以ε的概率隨機選取一個網(wǎng)頁訪問（由于用戶會以ε的概率隨機選取一個網(wǎng)頁訪問，因此本文將其稱為跳轉(zhuǎn)因子）。

傳統(tǒng)隨機游走PageRank 算法正是基于上述思想，模擬上述過程，實現(xiàn)了傳統(tǒng)迭代式PageRank算法的分布式計算。令n為節(jié)點數(shù)目，e為邊數(shù)，K為模擬次數(shù)總數(shù)與e的比值，ε為跳轉(zhuǎn)因子，為vi的PageRank值。算法首先初始化然后循環(huán)Ke次，對于每次循環(huán)，隨機選取節(jié)點vi，重復(fù)下列操作：對vi以1－ε的概率隨機選取后繼節(jié)點vj，以ε的概率重新選取新節(jié)點賦給vi，對于第一種情況，加1，將vj賦給vi，對于第二種情況，跳出重復(fù)。模擬結(jié)束后，得出的即為PageRank值，按其值排序即可得到影響力排名。

傳統(tǒng)隨機游走PageRank 算法實現(xiàn)了傳統(tǒng)迭代式PageRank算法的分布式計算，但由于其每一步均具有很強的隨機性，運算結(jié)果與傳統(tǒng)迭代式PageRank算法會有較大偏差［12，13］。

2.2 Fast PageRank算法

Fast PageRank算法最早是由Sarma A D 于2013年提出的，其思想是將傳統(tǒng)隨機游走PageRank產(chǎn)生的鏈路分割，僅考慮當(dāng)前以及隨機產(chǎn)生的下一個節(jié)點，在每次循環(huán)時對所有節(jié)點模擬單步隨機游走，即該算法在單次循環(huán)可分布式。該算法每次循環(huán)結(jié)束時均需要修改下次循環(huán)每個節(jié)點的模擬次數(shù)，從而利用上次計算結(jié)果為節(jié)點的PageRank值計算提供修正，提高了計算精確性。

令n為節(jié)點數(shù)目，e為邊數(shù)，ε為跳轉(zhuǎn)因子，單個節(jié)點的隨機游走次數(shù)初始值K＝clogn，其中（δ為任意常數(shù)，t為調(diào)整系數(shù)，W為隨機變量），為節(jié)點vi的隨機游走次數(shù)，為節(jié)點vi的影響力值，為當(dāng)前循環(huán)中隨機游走經(jīng)過邊（vi，vj）的次數(shù)。算法首先初始化然后循環(huán)Blogn/ε（B是一個充分大的數(shù)）次。對于每一次循環(huán)，首先初始化然后于對每每次個模節(jié)擬點，重復(fù)次模擬。對于每次模擬，以1－ε的概率隨機選取vi的后繼節(jié)點vj，以ε的概率重新選取新節(jié)點賦給vi，對于第一種情況，加1。每次循環(huán)所有節(jié)點模擬結(jié)束后，計算外層循環(huán)結(jié)束后得出的即為PageRank值，按其值排序即可得到影響力排名。

Fast PageRank算法每次修改模擬次數(shù)時需要將所有節(jié)點集中，即使其在每次循環(huán)時對節(jié)點并行處理，其在進行模擬次數(shù)修改時也需要大量計算機間的通信，時間效率較低。

本文基于逆向查找訪問消息傳播路徑的思想，給出一種改進的隨機游走PageRank算法。

3 Reverse PageRank

3.1 算法思想

本文將社交網(wǎng)絡(luò)中的用戶抽象成節(jié)點，用戶之間的訪問抽象成邊，則社交網(wǎng)絡(luò)可用有向圖D ＝（V，E）表示，其中V 是節(jié)點集合，V ＝｛v1，v2，…，vn｝；E 是所有節(jié)點間有向邊的集合。假設(shè)節(jié)點vi訪問了節(jié)點vj，則節(jié)點vi和節(jié)點vj之間存在一條有向邊eij（eij∈E）。

則算法思想可抽象為：

Step 1 對于每個eij∈E；

Step 2 如果transmit （vj，vk）返回true，轉(zhuǎn)step 3；否則，轉(zhuǎn)step 4；

Step 3 對vj、vk必存在ejk∈E，將vi?vj，vj?vk，轉(zhuǎn)step 2；

Step 4 對于eij，可以得到消息逆向傳播路徑vi→vj→vk→… →vx ，其中認為vx為消息原創(chuàng)者，則消息的傳播路徑為vx→…→vk→vj→vi。本模型認為，vi訪問vj這個行為，向此路徑上除vi外的其他節(jié)點反饋了影響力，此影響力在本模型中被數(shù)值化為1。

其中，transmit （vj，vk）所實現(xiàn) 的功能 為若vj為消息傳播源，則不需要繼續(xù)查找消息傳播源，返回false；反之，則繼續(xù)查找消息傳播源，將下一步隨機游走節(jié)點保存在vk中，返回true，具體實現(xiàn)見算法1。

算法1 函數(shù)transmit（vi，vj）

本文基于用戶之間的消息傳播，采用逆向查找消息原創(chuàng)者的思想找到消息的一條傳播路徑，當(dāng)然此路徑具有很強的隨機性。本文采用多次模擬的思想將其優(yōu)化，使結(jié)果更準(zhǔn)確。

3.2 算法實現(xiàn)

3.1節(jié)敘述了算法思想，將此思想進一步形式化，即可得到算法，本文將其稱為Reverse PageRank，如算法2所示。

算法2 Reverse PageRank 算法

輸入：節(jié)點的個數(shù)n，每條邊模擬隨機游走次數(shù)K，跳轉(zhuǎn)因子ε；

輸出：每個節(jié)點的影響力值。

算法步驟：

從本質(zhì)上看，本文算法是一個隨機游走算法，與傳統(tǒng)隨機游走PageRank 算法很類似。二者之間不同的是，傳統(tǒng)隨機游走PageRank算法每一步的選擇均是隨機的，而Reverse PageRank 對有向圖中每條邊進行隨機游走模擬，即將原本對每條邊分布不均勻的模擬次數(shù)均勻地分配給每條邊，真實反映消息在社交網(wǎng)絡(luò)中傳播的路徑。另外，與Fast PageRank相比，Reverse PageRank以深度優(yōu)先搜索消息逆向傳播路徑為主要思想；而Fast PageRank是對整個社交網(wǎng)絡(luò)中所有節(jié)點均進行一次隨機游走后才開始下一次隨機游走，且后一次隨機游走是以前一次隨機游走為基礎(chǔ)，是一種廣度優(yōu)先的隨機游走。

4 仿真實驗

4.1 實驗數(shù)據(jù)及評價

本文仿真實驗分別選取了三種不同數(shù)量級的數(shù)據(jù)集來分別測試，其中數(shù)據(jù)集1、3來源于斯坦福大學(xué)的大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)集［16］。數(shù)據(jù)集1是一個技術(shù)新聞類用戶社區(qū)數(shù)據(jù)；數(shù)據(jù)集2為真實的博客用戶訪問數(shù)據(jù)，來源于文獻［17］；數(shù)據(jù)集3是斯洛伐克的一個在線社交網(wǎng)絡(luò)數(shù)據(jù)集。表1中給出了具體的數(shù)據(jù)規(guī)模。

Table 1 Test datasets表1 測試數(shù)據(jù)集

本文首先將表1中的數(shù)據(jù)用傳統(tǒng)迭代式PageRank算法計算出每個節(jié)點的真實PageRank值，并將其作為節(jié)點在社交網(wǎng)絡(luò)中影響力的參考基準(zhǔn)。其次是分別運行傳統(tǒng)隨機游走PageRank 算法、Fast PageRank 算 法 以 及 本 文 的Reverse PageRank算法得出其節(jié)點影響力排名。最后將三種對比算法得到的影響力排名與基準(zhǔn)排名進行比對，測算出對比算法排名的準(zhǔn)確性，本文用趨近度來表示準(zhǔn)確性。趨近度定義為：

其中n表示社交網(wǎng)絡(luò)節(jié)點影響力排名的前n個節(jié)點；Nref（n）表示真實社交網(wǎng)絡(luò)影響力排名前n個節(jié)點所組成的集合，本文用傳統(tǒng)迭代式PageRank作為基準(zhǔn)；Ncmp（n）表示比較算法社交網(wǎng)絡(luò)影響力排名前n個節(jié)點所組成的集合。

根據(jù)趨近度的定義，當(dāng)n從1開始變化時可形成一條趨近度的曲線，本文以該曲線作為算法準(zhǔn)確性的評判標(biāo)準(zhǔn)。比較算法得出排名與傳統(tǒng)迭代式PageRank算法趨近度越高，相應(yīng)曲線越趨近于上界1，表明算法的準(zhǔn)確性越好。

4.2 實驗結(jié)果及分析

為了比較公平性，本文只對隨機游走參數(shù)K（K代表模擬的游走次數(shù)）和跳轉(zhuǎn)因子ε進行設(shè)置，并比較在不同參數(shù)設(shè)置下傳統(tǒng)隨機游走算法（RandomPR）［11］、Fast PageRank（FastPR）［5］和本文中的Reverse PageRank（ReversePR）的趨近度。圖1～圖3中分別給出了三個數(shù)據(jù)集在游走參數(shù)K＝｛1，5，10，20，50｝情況下，阻尼系數(shù)ε在［0.1，0.9］的趨近度。由于篇幅限制，本文只給出了三種阻尼系數(shù)ε的實驗結(jié)果圖，分別是0.1、0.9 和FastPR 與ReversePR 的性能臨界時的ε的值。

從圖1～圖3中可以看出：

（1）在K、ε取任意值時，ReversePageRank均比傳統(tǒng)隨機游走PageRank算法更靠近上界1。因此，Reverse PageRank算法明顯優(yōu)于傳統(tǒng)隨機游走RandomPR 算法。

（2）Reverse PageRank 在ε取 值［0.4，0.90］時，比Fast PageRank 算法更靠近上界1，即當(dāng)模擬次數(shù)較少、跳轉(zhuǎn)因子較大時，Reverse PageRank優(yōu)于Fast PageRank算法。

（3）隨著社交網(wǎng)絡(luò)中節(jié)點和邊的數(shù)量增加，Reverse PageRank相對Fast PageRank算法的優(yōu)勢逐漸增大。

通過實驗分析，可得Reverse PageRank 算法優(yōu)于傳統(tǒng)隨機游走PageRank 算法，并且當(dāng)K較小、ε較大時，Reverse PageRank優(yōu)于Fast PageRank算法。當(dāng)K較大時，F(xiàn)ast PageRank 比Reverse PageRank更趨近傳統(tǒng)迭代式PageRank，但Fast PageRank每次迭代都需要計算所有節(jié)點的下一次模擬次數(shù)，因此當(dāng)社交網(wǎng)絡(luò)節(jié)點數(shù)量較大時，其算法時間性能將急劇下降。而本文提出的算法在K較小、ε較大時即與傳統(tǒng)迭代式PageRank算法有更好的趨近度。通過三個不同數(shù)量級上的實驗對比分析，本文提出的Reverse PageRank 在兼顧計算時間和效率的情況下可以在K在［1，20］、ε在［0.4，0.9］時獲得一個較優(yōu)的度量值。因此，Reverse PageRank 算法在社交網(wǎng)絡(luò)節(jié)點數(shù)目較大時具有較強的適用性。

從第4節(jié)的仿真實驗可以看出，Reverse PageRank相對于傳統(tǒng)隨機游走PageRank 可以更好地與傳統(tǒng)迭代式PageRank 趨近，同時與Fast PageRank相比，本文提出的Reverse PageRank算法在迭代次數(shù)較少的情況下，跳轉(zhuǎn)因子ε較大時，精度明顯優(yōu)于Fast PageRank。這是因為在真實社交網(wǎng)絡(luò)中，大部分消息都是以較低概率向鄰居節(jié)點傳播，只有少部分消息以較大的概率向周圍節(jié)點傳播［15］，因此跳轉(zhuǎn)因子值較大時模擬出的隨機游走能比較恰當(dāng)?shù)胤从痴鎸嵣缃痪W(wǎng)絡(luò)中的消息傳播，也一定程度上體現(xiàn)了本文算法設(shè)計的合理性。

5 結(jié)束語

本文提出的Reverse PageRank算法是基于逆向查找消息傳播源的思想，提出了一種改進的隨機游走PageRank算法。實驗表明，該算法在模擬次數(shù)較少、跳轉(zhuǎn)因子較大時相對傳統(tǒng)隨機游走PageRank算法以及Fast PageRank算法準(zhǔn)確度更高，當(dāng)社交網(wǎng)絡(luò)較大時，利用其做影響力度量將比其他兩種算法更有優(yōu)勢。

Figure 1 Simulation experiments on Slashdot0811dataset（V ＝77 360，E ＝905 468）圖1 Slashdot0811數(shù)據(jù)集仿真實驗（V ＝77 360，E ＝905 468）

Figure 3 Simulation experiments on Pokec dataset（V ＝1 632 803，E ＝30 622 564）圖3 Pokec數(shù)據(jù)集仿真實驗（V ＝1 632 803，E ＝30 622 564）

［1］ Wu Xin－dong，Li Yi，Li Lei.Influence analysis of online social networks［J］.Chinese Journal of Computers，2014，37（4）：735－752.（in Chinese）

［2］ Zhao Zhi－ying，Yu Hai，Zhu Zhi－Liang，et al.Identifying influential spreaders based on network community structure［J］.Chinese Journal of Computer，2014，37（4）：753－766.（in Chinese）

［3］ Liu Zhi－peng，Pi De－chang.Mining social influence of nodes from mobile datasets［J］.Journal of Computer Research and Development，2013，50（Suppl.）：244－248.（in Chinese）

［4］ Chen Hao，Wang Yi－tong.Threshold－based heuristic algorithm for influence maximization［J］.Journal of Computer Research and Development，2012，49（10）：2181－2188.（in Chinese）

［5］ Das Sarma A，Molla A R，Pandurangan G，et al.Fast distributed PageRank computation［J］.Theoretical Computer Science，2015，56（10）：113－121.

［6］ Ding Zhao－yun，Jia Yan，Zhou Bin，et al.Survey of influence analysis for social networks［J］.Computer Science，2014，41（1）：48－53.（in Chinese）

［7］ Liu Yan－h(huán)eng，Li Fei－peng，Sun Xin，et al.Social network model based on the transmission of information［J］.Journal of Communications，2013，34（4）：1－9.（in Chinese）

［8］ Zhao W，Chen H F，F(xiàn)ang H T.Convergence of distributed randomized PageRank algorithms［J］.IEEE Transactions on Automatic Control，2013，58（12）：3255－3259.

［9］ Ding Z，Jia Y，Zhou B，et al.Mining topical influencers based on the multi－relational network in micro－blogging sites［J］.China Communications，2013，10（1）：93－104.

［10］ Sarma A D，Nanongkai D，Pandurangan G，et al.Distributed random walks［J］.Journal of the ACM （JACM），2013，60（1）：1－31.

［11］ Page L，Brin S，Motwani R，et al.The PageRank citation ranking：bringing order to the Web［J］.Stanford Infolab，1999，9（1）：1－14.

［12］ Henzinger M R，Heydon A，Mitzenmacher M，et al.Measuring index quality using random walks on the Web［J］.Computer Networks，1999，31（11－16）：1291－1303.

［13］ Li L，Xu G，Zhang Y，et al.Random walk based rank aggregation to improving web search.［J］.Knowledge Based Systems，2011，24（7）：943－951.

［14］ Lee S，Jin H L，Lim J，et al.Robust stereo matching using adaptive random walk with restart algorithm［J］.Image and Vision Computing，2015，37：1－11.

［15］ Csáji B C，Jungers R M，Blondel V D.PageRank optimization by edge selection［J］.Discrete Applied Mathematics，2014，169（6）：73－87.

［16］ https：//snap.stanford.edu/data/index.html.

［17］ Zhong E，F(xiàn)an W，Wang J，et al.ComSoc：adaptive transfer of user behaviors over composite social network［C］∥Proc of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2012：696－704.

附中文參考文獻：

［1］ 吳信東，李毅，李磊.在線社交網(wǎng)絡(luò)影響力分析［J］.計算機學(xué)報，2014，37（4）：735－752.

［2］ 趙之瀅，于海，朱志良，等.基于網(wǎng)絡(luò)社團結(jié)構(gòu)的節(jié)點傳播影響力分析［J］.計算機學(xué)報，2014，37（4）：753－766.

［3］ 劉志鵬，皮德常.從移動數(shù)據(jù)中挖掘網(wǎng)絡(luò)節(jié)點的影響力［J］.計算機研究與發(fā)展，2013，50（Suppl）：244－248.

［4］ 陳浩，王軼彤.基于閾值的社交網(wǎng)絡(luò)影響力最大化算法［J］.計算機研究與發(fā)展，2012，49（10）：2181－2188.

［6］ 丁兆云，賈焰，周斌，等.社交網(wǎng)絡(luò)影響力研究綜述［J］.計算機科學(xué)，2014，41（1）：48－53.

［7］ 劉衍珩，李飛鵬，孫鑫，等.基于信息傳播的社交網(wǎng)絡(luò)拓撲模型［J］.通信學(xué)報，2013，34（4）：1－9.