βNodeRank：一種對社交網絡節點重要性評估的方法

徐達 杜彥輝 蘆天亮 翟瑞

摘 要： 現有基于PageRank算法的社交網絡節點重要性評估方法聚焦在社交網絡節點出入度、邊權值上，忽略了社交網絡節點所在網絡結構上位置差異的因素。分析現有基于PageRank算法的方法對社交網絡節點重要性評估缺陷，提出改進評估方法βNodeRank。通過原理分析和實驗分析對改進方法的優勢進行比較，結果表明改進方法在社交網絡節點重要性評估上更加合理。

關鍵詞： PageRank； βNodeRank； 社交網絡； 節點重要性； 社區； 評估

中圖分類號： TN711?34； TP20 文獻標識碼： A 文章編號： 1004?373X（2018）17?0085?05

Abstract： The available PageRank algorithm based node importance evaluation methods for social network mainly focus on the node access degree and edge weight of social network， but ignores the effect of location difference of the social network node on network structure. An improved node importance evaluation method for social network is proposed on the basis of βNodeRank by analyzing the node importance evaluation defects of social network based on the available PageRank algorithm. The advantage of this improved method is analyzed with principle analysis and experiment analysis， and the results show that the method is reasonable for node importance evaluation of social network.

Keywords： PageRank； βNodeRank； social network； node importance； community； evaluation

0 引 言

隨著針對社交網絡上信息溯源、信息傳播機理和信息干預與管控等研究的興起，對社交網絡節點重要性評估成為社交網絡研究的重要基礎和分支。數據處理能力的提升和社交網絡提供大量高價值數據給節點重要性評估方法研究提供了支持，但在社交網絡節點重要性評估方法研究中也存在諸多挑戰。社交網絡上用戶是否產生、傳遞信息受到內因和外因的作用；社交網絡用戶之間關系復雜，社交網絡用戶不同程度聚集在一起，除通過如共同標簽、共同需求、共同興趣等社交網絡社區劃分外，很難找到其他明確劃分社交網絡用戶聚集的界限。這都對評估社交網絡中傳遞信息最快節點、最活躍節點帶來了困難，因此對社交網絡節點重要性評估需要充分考慮社交網絡區別其他復雜網絡的特性。

本文分析了一種基于節點度的評估方法[1]，針對原方法從社交網絡節點連接情況出發而忽略節點所處社交網絡結構位置影響的不足，提出一種結合節點度和社區因素的改進評估方法，從理論分析和真實數據測量研究社交網絡節點重要性評估。不同于已有方法[2?3]對節點度的具體分析或降低算法復雜度，改進方法結合社交網絡社區因素，能夠更合理完成社交網絡節點重要性評估。

1 相關工作

社交網絡是一種典型的復雜網絡，具有“小世界”“度分布”“聚集”等特征[4]。對復雜網絡節點重要性排序研究，許多研究者選擇從復雜網絡節點的某種或多種統計特征的角度來分析節點重要性。

文獻[1]基于PageRank排名算法，提出DWCN?NodeRank方法對節點重要性評估，完成對加權有向社交網絡節點重要性排序。文獻[3]考慮節點間邊的權值，認為節點重要性與節點的入度、出度和總度相關，提出改進PageRank排名算法對復雜網絡節點重要性排序的方法。文獻[5]提出一種改進基于凝聚度的節點重要性評估方法，引入節點連接邊的重要度評估，綜合考慮節點的連接特性對節點重要度的影響。通過節點的連接情況對網絡中節點重要性評估是常見的研究方法，但忽略了節點所處網絡結構位置對節點重要性的影響。

文獻[6]基于社交網絡真實數據分析得出結論，集聚度高節點相對集聚度低節點在復雜網絡上擴散信息更快。Kitsak等提出節點重要性與節點所處復雜網絡的位置相關[7]，并利用k核分解，通過遞歸將整個網絡劃分成層次，得出節點重要性排序指標；首次通過理論和實驗驗證，節點重要性與節點所處復雜網絡的位置是相關的。研究從網絡結構特性出發，但指標有一定的局限性。

在社交網絡節點重要性評估中，節點入度、出度和總度是重要的指標，節點所處網絡結構位置也對節點重要性評估具有重要影響。本文從社交網絡節點度出發，同時考慮節點社區連接情況對社交網絡節點重要性評估。

2 基于NodeRank節點重要性評估

圖1中網絡共有16個節點、33條邊、3個社區（虛線圈表示社交網絡社區），其中節點5和節點10分別從屬兩個社區。由上述結果可知節點5在整個網絡中NR值最小，則認為節點5為整個網絡中最不重要的節點。分析圖1網絡可知，節點5作為“騎墻節點”在網絡中連接節點4和節點6、社區1和社區2，在圖1所示網絡中的重要性不言而喻。由DWCN?NodeRank[1]得出的結論與文獻[7?9]中方法得出的結論都有較大出入，分析DWCN?NodeRank在圖1網絡中節點重要性排序過程，發現DWCN?NodeRank聚焦于節點的出入強度、有向邊的權值，而忽略了復雜網絡中多社區與重疊社區對社交網絡節點重要性排序的影響。

3 基于βNodeRank節點重要性評估方法

PageRank算法是為互聯網頁面排名而設計，社交網絡與互聯網雖然都是復雜網絡，但兩者存在明顯的區別，直接基于PageRank算法對社交網絡節點重要性評估是不合理的。在社交網絡中通常由性質相似的節點組成社交網絡社區，社區結構是對社交網絡節點聚集特性的刻畫[10]。社交網絡中，節點從屬一個或多個社區，當節點從屬的社區越多，則表明節點越趨近社交網絡結構中心，在社交網絡結構中越重要。對社交網絡節點重要性評估需要將節點按現實情況劃分至各社區，考慮節點在社區間連通的貢獻，提高社交網絡節點重要性評估的準確性。因此社交網絡節點的重要性評估需要考慮節點出入度、邊權值和節點社區等因素。Zhang等基于PageRank排名算法，提出DWCN?NodeRank方法對節點重要性排序[1]，忽略節點對社區連通貢獻，不能滿足對社交網絡節點重要性評估，需要進行改進。針對上述問題，本文在分析和總結現有方法基礎上，提出基于[βNodeRank]方法對社交網絡節點重要性評估的方法。

首先，大量的實驗數據結論[7?9]表明社交網絡中某些節點度數較低，但處于整個網絡中的關鍵位置。其次，社交網絡中個體之間的相似性、個體之間的某種聯系和個體的興趣愛好等讓個體在社交網絡中呈現聚集狀態形成各類網絡社區，在社區內信息傳播、擴散的速度更快，社區是社交網絡節點重要性評估不可忽視的因素。綜上所述，提出改進方法[βNodeRank]，設置調節參數[βι]對社交網絡節點重要性評估引入社區因素：

式中，[βι=tN]，[t]為節點從屬社區數，[N]為社交網絡節點總數。對圖1所示重疊社區社交網絡基于[βNodeRank]節點重要性評估的結果如表1所示。在圖1所示網絡重要節點重要性評估過程中，相比NodeRank方法所得結論，[βNodeRank]方法所得結論節點15和節點14的重要性排名略微有所下降，節點5的重要性排名大幅度提升；分析圖示網絡結構，節點15和節點14都具有節點度數高、從屬社區單一，節點5具有節點度數低、從屬社區多的特點。在[βNodeRank]引入調節參數[β]，能夠提高節點度數低但從屬社區多節點的NR值，降低節點度數高但從屬社區單一節點的NR值。由此可見， [βNodeRank]對圖1所示網絡中節點重要性評估更加合理，所得結果與文獻[7?9]中方法得出結論也更接近。

COPRA算法在標簽傳播過程中采用同步更新的策略，節點[t]次迭代基于[t-1]次迭代鄰居標簽列數據對，主要的步驟如下：

1） 對社交網上所有節點進行初始化，每個節點引入唯一標簽列，標簽列中的數據對根據社交網中節點的連接狀況進行添加。

2） 設定從屬系數閾值[1v]，[v]是節點的最大社區從屬數。一個節點標簽中所有數據對都小于設定閾值，保留最大的從屬系數的數據對，將其他數據刪除，如果超過一對的最大從屬系數對，將其中進行隨機選擇。在節點標簽列數據被刪除后，將對其從屬系數更新，保持從屬系數和為1。

3） 經過若干次迭代后，當[t]次迭代結果和[t-1]次結果相同，則停止迭代。

4） 根據結果具有相同標簽的節點將被劃分至同一社區。

實驗結果證明COPRA算法雖然迭代過程具有隨機性[11]，但能夠對有向加權網絡進行準確的社區劃分。圖2為人工合成網絡基于COPRA算法[11]進行社區劃分。網絡初始化后，設定閾值為[v=3]，如圖2a）所示節點15標簽列數據對為{（0，[14]），（1，[14]），（3，[14]），（4，[14]）}，在迭代前對節點15標簽列數據對更新為（1，1），經過數次運算，得到重疊社區劃分結果如圖2b）所示，人工合成網絡共有社區數3個，節點5和節點10分別從屬2個不同社區。

引入病毒模型模擬消息在社交網絡中的擴散能為社交網絡節點重要性評估方法比較提供支撐。本文引入Wang等提出的傳染病模型[12]，模擬社交網絡上信息擴散。在2011年文獻[13]研究成果中已經證明信息量越大的節點重要性越強。本文利用該成果，定義社交網絡中被感染次數越多的節點重要性越強。

4 實驗仿真

為驗證改進方法[βNodeRank]的可行性和準確性，基于真實社交網絡數據進行實驗。實驗環境為Intel[?] CoreTM i5?4570 CPU@ 3.20 GHz，4 GB內存，Window 7旗艦版SP1操作系統，Gephi?0.9.1，Matlab R2010b編程環境。

社交網絡數據采用Newman實驗室采集美國大學生橄欖球聯賽社會網（Football），并引入病毒模型[12]模擬信息的擴散。本文對社交網絡進行病毒感染，分別選擇不同的節點為初始感染點，設定[α] =0.85（[α]為未感染節點直接與感染節點連接被感染率），[ζi，t]=0.15（[ζi，t]為節點[i]在時刻[t]的免疫率），[δ]=0.5（[δ]為感染病毒節點自身痊愈率），對社交網絡進行感染，當感染節點占所有節點數的85%時，停止病毒傳播，實驗20次后，取各節點被感染次數的眾數為最終結果。實驗網絡共包括節點115個、邊613條、整個網絡平均度為10.66、平均加權度為5.33。對Football網絡節點進行編號后，基于COPRA算法對Football社交網絡進行社交網絡社區發現，得知該網絡共有社區10個，隨之確定各節點從屬社區，并標記各節點[βι]值，基于[βNodeRank]方法對節點重要性排序。

基于[βNodeRank]方法對Football網絡節點重要性評估，經運算得出如圖3a）所示結果與基于DWCN?NodeRank方法得出圖3b）所示結果進行對比分析。在兩種方法中阻尼系數均設置為0.85，結果值準確度為[10-5]，橫坐標為Football網絡各節點編號，縱坐標為結果值。

對比分析兩種方法所得結果，在節點編號相同的情況下，兩者結果數據值差異較大，但大體上兩者結果分布形態相對接近，少許節點有出入。本文選取部分代表性節點進行分析，兩種方法得出網絡節點重要性評估結果中排名前10的節點分別如表2所示。

將社區節點分為10簇代表網絡中社區情況，圖4表示節點在Football網絡中連接情況。其中圖4a）為所有節點相互之間的連接情況。由表2數據對比分析，排名前3的節點0、節點2和節點12在網絡中連接情況分別如圖4b），圖4c）和圖4d）所示。相對節點2和節點12度數高但只連接3個社區，節點0度數高并且連接5個社區在社交網絡上更加重要。值得說明的是節點12被感染的次數為10次，連接社區為3個，但是節點12所連接的節點大部分是高分值節點，所以節點12在兩種節點重要性評估方法中都具有較高評分值。對比分析兩種方法的結果，[βNodeRank]在社交網絡上重要節點排序過程中能調整度數相對較低，但連接社區多節點的重要性強度。依據節點重要性重新排序，所得結果也與病毒感染模型[12]結論吻合。

基于真實網絡數據的分析得出，改進方法更合理、準確地對社交網絡節點重要性評估，評估方法所得結論符合PageRank算法“從高評分頁面鏈接得到的頁面也是高評分頁面”的回歸思想，并且能夠提高重要節點分值，降低非重要節點分值。

5 結 語

本文分析了基于PageRank算法對社交網絡節點重要性評估方法中忽略社區作用的缺陷，在此基礎上針對原算法不足，提出改進的社交網絡節點重要性評估方法。結果表明，改進的評估方法[βNodeRank]加入社區因素后，對社交網絡節點重要性進行評估，所得評估結果更加合理。社交網絡節點重要性評估高度復雜，因此本方法仍然存在不足之處，未來，可進一步的考慮社交網絡多因素影響。本方法的提出有助于進一步的分析和探討。

參考文獻

[1] ZHANG K， LI P， ZHU B， et al. Evaluation method for node importance in directed?weighted complex networks based on PageRank [J]. Journal of Nanjing University of Aeronautics & Astronautics， 2013， 45（3）： 429?434.

[2] 楊宏偉，張勇，王煥坤，等.基于負載流的點加權復雜網絡節點重要性評估方法研究[J].計算機應用研究，2013，30（1）：134?137.

YANG Hongwei， ZHANG Yong， WANG Huankun， et al. New measure of node importance based on load flow in node?weighted complex networks [J]. Computer application research， 2013， 30（1）： 134?137.

[3] LI G L， LI H， WANG Y R， et al. The solution to node importance in complex networks based on PageRank algorithm [J]. Applied mechanics & materials， 2014， 599： 1777?1780.

[4] 劉建國，任卓明，郭強，等.復雜網絡中節點重要性排序的研究進展[J].物理學報，2013，62（17）：9?18.

LIU Jianguo， REN Zhuoming， GUO Qiang， et al. Node importance ranking of complex networks [J]. Acta physica Sinica， 2013， 62（17）： 9?18.

[5] 王甲生，吳曉平，廖巍，等.改進的加權復雜網絡節點重要度評估方法[J].計算機工程，2012，38（10）：74?76.

WANG Jiasheng， WU Xiaoping， LIAO Wei， et al. Improved method of node importance evaluation in weighted complex networks [J]. Computer engineering， 2012， 38（10）： 74?76.

[6] CENTOLA D. The spread of behavior in an online social network experiment [J]. Science， 2010， 329（5996）： 1194?1197.

[7] KITSAK M， GALLOS L K， HAVLIN S， et al. Identification of influential spreaders in complex networks [J]. Nature physics， 2010， 6（11）： 888?893.

[8] JIAN Z， PAN J， ZHOU Y. Node importance evaluation based on network heterogeneity [C]// 2010 IEEE International Confe?rence on Communications and Mobile Computing. Piscataway： IEEE， 2010： 188?194.

[9] 李拓晨，侯磊，李永立.一種基于網絡整體影響力的節點重要性評估方法[J].情報學報， 2015，34（11）：1143?1151.

LI Tuochen， HOU Lei， LI Yongli. Evaluation method for node importance based on the whole network prestige [J]. Journal of the China society for scientific and technical information， 2015， 34（11）： 1143?1151.

[10] BALAKRISHNAN H， DEO N. Discovering communities in complex networks [C]// 2006 Southeast Regional Conference. Melbourne： [s.n.]， 2006： 280?285.

[11] GREGORY S. Finding overlapping communities in networks by label propagation [J]. New journal of physics， 2009， 12（10）： 2011?2024.

[12] WANG Y， CHAKRABARTI D， WANG C， et al. Epidemic spreading in real networks： an eigenvalue viewpoint [C]// 2003 IEEE International Symposium on Reliable Distributed Systems. Piscataway： IEEE， 2003： 25?34.

[13] 張翼，劉玉華，許凱華，等.一種基于互信息的復雜網絡節點重要性評估方法[J].計算機科學，2011，38（6）：88?89.

ZHANG Yi， LIU Yuhua， XU Kaihua， et al. Evaluation method for node importance based on mutual information in complex networks [J]. Computer science， 2011， 38（6）： 88?89.