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

（安徽師范大學數學計算機科學學院，安徽 蕪湖241003）

1 引言

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

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

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

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

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

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

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

2 相關研究

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

2.1 傳統隨機游走PageRank算法

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

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

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

2.2 Fast PageRank算法

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

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

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

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

3 Reverse PageRank

3.1 算法思想

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

則算法思想可抽象為：

Step 1 對于每個eij∈E；

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

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

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

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

算法1 函數transmit（vi，vj）

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

3.2 算法實現

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

算法2 Reverse PageRank 算法

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

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

算法步驟：

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

4 仿真實驗

4.1 實驗數據及評價

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

Table 1 Test datasets表1 測試數據集

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

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

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

4.2 實驗結果及分析

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

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

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

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

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

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

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

5 結束語

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

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

Figure 3 Simulation experiments on Pokec dataset（V ＝1 632 803，E ＝30 622 564）圖3 Pokec數據集仿真實驗（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，Fang 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，Fan 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］ 吳信東，李毅，李磊.在線社交網絡影響力分析［J］.計算機學報，2014，37（4）：735－752.

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

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

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

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

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