徐杰，王菊韻，張海云

(1.中國傳媒大學 理學院，北京100024；2.北京化工大學 信息科學與技術學院，北京100029)

基于復雜網(wǎng)絡的社交網(wǎng)絡用戶影響力研究

徐杰1，2，王菊韻1，張海云1

(1.中國傳媒大學 理學院，北京100024；2.北京化工大學 信息科學與技術學院，北京100029)

基于復雜網(wǎng)絡理論對社交網(wǎng)絡用戶影響力進行分析，可以為社會營銷、輿情監(jiān)測、信息檢索等眾多領域的研究提供支持。傳統(tǒng)的網(wǎng)頁排序算法雖然可以對有向社交網(wǎng)絡的用戶影響力進行分析，但仍存在缺陷且復雜度較高。本文提出了一種對無向社交網(wǎng)絡進行用戶影響力評價的方法，弱化了將有向網(wǎng)絡視為無向網(wǎng)絡研究而帶來的誤差，并可以高效地得到重要節(jié)點，適用范圍更廣。首先，本文采用網(wǎng)絡節(jié)點的度中心性、介數(shù)中心性、接近中心性、聚類系數(shù)作為節(jié)點重要度評價指標，通過對計算數(shù)據(jù)歸一化處理并取均值得到用戶影響力排序的基準。其次，采用k-核分解法粗粒化地將重要度相似的節(jié)點進行歸類，來檢驗排序的合理性。最后，通過仿真實驗以及k-核分解、與HITS算法比較驗證了此方法的科學性和正確性。

社交網(wǎng)絡；用戶影響力；網(wǎng)絡節(jié)點重要度；k-核分解

1 引言

復雜網(wǎng)絡的相關研究已經(jīng)成為多個學科共同關注的前沿熱點。隨著各種在線社交網(wǎng)絡不斷涌現(xiàn)，大量具有研究價值的網(wǎng)絡數(shù)據(jù)應運而生。對社交網(wǎng)絡用戶影響力進行分析，可以為社會營銷、輿情監(jiān)測、信息檢索等眾多領域的研究提供支持。此研究已成為一個新興且熱門的研究課題。

針對不同類型的網(wǎng)絡和不同的研究問題，節(jié)點的重要性判斷標準也不同，在線社會網(wǎng)絡用戶的重要性刻畫方法也多種多樣。其中最為常用的方法為Kleinberg提出的HITS算法[1]、Page和Brin提出的PageRank算法[2]兩種網(wǎng)頁排序算法以及對其進行改進的算法。HITS和PageRank算法在20世紀90年代后期幾乎同時提出，后成為搜索引擎領域中的網(wǎng)頁重要度排序的經(jīng)典算法。任曉龍等人的《網(wǎng)絡重要節(jié)點排序方法綜述》[3]與兆云等人的《社交網(wǎng)絡影響力研究綜述》[4]對兩種算法進行了詳細的介紹與分析。后來通過各種各樣的方法將社交網(wǎng)絡數(shù)據(jù)抽象成有向網(wǎng)絡模型，網(wǎng)頁排序算法開始被用于社交網(wǎng)絡的研究。代表性的研究工作有Song等人[5]考慮博文新穎度提出的InfluenceRank算法。Haveliwala等人[6]考慮了用戶之間的鏈接與主題內(nèi)容，運用PageRank思想對用戶影響力進行了研究。Zhongwu Zhai 等人[7]基于正向有權網(wǎng)絡假設，發(fā)現(xiàn)了一種基于興趣的PageRank算法來識別重要用戶。Meeyoung Cha[8]通過研究用戶行為與影響力之間的關系，以及與斯皮爾曼等級相關系數(shù)比較來得出用戶影響力排名。Shaozhi Ye[9]通過分析Twitter的用戶行為與粉絲數(shù)量、推文的響應數(shù)，提出了一種將用戶主頁內(nèi)容作為重要度排序指標的方法。但網(wǎng)頁排序算法仍存在缺陷且復雜度高。算法的收斂性和有效性不能同時保證，并且通常只適用于特定類型的社交網(wǎng)絡。針對這些問題，本文提出了一種直接對無向社交網(wǎng)絡進行用戶影響力評價的方法，弱化了將有向網(wǎng)絡視為無向網(wǎng)絡研究而帶來的誤差，并且可以高效地得到重要用戶節(jié)點，適用范圍更廣。

2 四指標綜合用戶影響力評價方法

20世紀90年代，HITS首次用不同指標(權威值和樞紐值)同時對網(wǎng)絡中的節(jié)點進行排序，本研究綜合了網(wǎng)絡節(jié)點的度中心性、介數(shù)中心性、接近中心性、聚類系數(shù)等四個指標對無向網(wǎng)絡節(jié)點重要度進行評價的方法。該方法如圖1所示，首先按照一定規(guī)則建立社交網(wǎng)絡模型，并對網(wǎng)絡節(jié)點的四個指標進行計算。其次，對四個指標的計算結果分別進行歸一化處理，消除指標之間的量綱影響。然后，對歸一化后的四個指標取均值，均值即為用戶影響力排序的基準，根據(jù)均值的大小比較得到最終用戶影響力排序。最后，運用k-核分解法對排序結果進行檢驗。

圖1 四指標綜合用戶影響力評價方法示意圖

3 仿真實驗與結果分析

3.1 數(shù)據(jù)來源及模型構建

本文使用的數(shù)據(jù)來源于http：//lovro.lpt.fri.uni-lj.si/，此主頁為盧布爾雅那學者lovrosubelj對網(wǎng)絡科學方面研究內(nèi)容的共享的開發(fā)數(shù)據(jù)。所使用的建模及計算工具為大型復雜網(wǎng)絡分析軟件Pajek。

對于大型復雜網(wǎng)絡的研究通常先需要對大型網(wǎng)絡分解成社區(qū)或團體等規(guī)模相對較小的網(wǎng)絡，以便進行研究。本文選用Facebook用戶slavko的好友圈數(shù)據(jù)，根據(jù)slavko的好友圈中用戶之間的好友關系建立無向網(wǎng)絡。無向網(wǎng)絡模型中共包含334個用戶節(jié)點，2218條邊。為了方便表示，將用戶節(jié)點分別標記為v1，v2，……，v334。建立的無向網(wǎng)絡模型如圖2所示。

圖2 slavko的好友關系網(wǎng)絡

該網(wǎng)絡模型能夠直觀地描述網(wǎng)絡的1階度分布信息，即網(wǎng)絡中不同度的節(jié)點各自所占的比例。但是，具有相同度分布的兩個網(wǎng)絡可能具有非常不同的其他性質或行為，還需要考慮包含更多結構信息的高階拓撲特性來刻畫網(wǎng)絡，如網(wǎng)絡的度相關性及同配性(2階度分布特性)。大量的實證研究表明，不同的在線社會網(wǎng)絡可以呈現(xiàn)不同的同配、異配或接近中性的特征。根據(jù)Ugander J等人的研究，含有7億多個節(jié)點的Facebook網(wǎng)絡呈現(xiàn)出同配性，r=0.226[11]。經(jīng)計算，本文所建網(wǎng)絡模型的同配系數(shù)r=0.2473，大于0，也呈現(xiàn)出同配性。因此，此網(wǎng)絡模型能夠較好地刻畫該團體網(wǎng)絡用戶之間的好友關系。

3.2 用戶影響力分析

3.2.1 度中心性研究

在社會關系網(wǎng)絡中，位置越中心的節(jié)點其價值越大，最直接的度量就是度中心性，一個包含N個節(jié)點的網(wǎng)絡中，度為的節(jié)點的度中心性值定義為：

(1)

基于Pajek計算得到各用戶節(jié)點(UserID)的度中性值(DegreeCentrality)，如圖3所示。

圖3 各節(jié)點的度中心性值

表1給出了網(wǎng)絡中度中心性排名前10的用戶節(jié)點及其對應的度中心性值和數(shù)據(jù)歸一化處理后的取值。表中數(shù)據(jù)采用min-max歸一化(后面各指標的計算也均采用此方法)，轉換函數(shù)如下：

(2)

其中max為樣本數(shù)據(jù)的最大值，min為樣本數(shù)據(jù)的最小值。

整個網(wǎng)絡中度中心性最大值為0.174174，最小值為0。

表1 度中心性值排名前10的節(jié)點

3.2.2 介數(shù)中心性研究

度中心性雖然能直觀的描述節(jié)點的重要度，但很容易忽視網(wǎng)絡中一些在控制信息傳輸上起著重要作用的節(jié)點。例如，一個連接2個較大子網(wǎng)的節(jié)點，其本身的度值雖然不高，但在兩個子網(wǎng)的信息傳輸上卻卻承受了較大的信息流量。節(jié)點i的介數(shù)定義為：

(3)

基于Pajek計算得到各用戶節(jié)點(User ID)的介數(shù)(Betweenness centrality)，如圖4所示。

圖4 各節(jié)點的介數(shù)中心性值

表2給出了網(wǎng)絡中介數(shù)中心性排名前10的用戶節(jié)點及其對應的介數(shù)取值和數(shù)據(jù)歸一化處理后的取值。整個網(wǎng)絡中，介數(shù)最大值為0.16854，最小值為0。介數(shù)越大的用戶節(jié)點，在整個網(wǎng)絡的最短路徑中所占數(shù)目越多。

表2 介數(shù)排名前10的節(jié)點

3.2.3 接近中心性研究

無權網(wǎng)絡中，最短路徑上節(jié)點數(shù)目的多少對網(wǎng)絡中信息的傳輸效率是有影響的，一個含有N個節(jié)點的網(wǎng)絡中的節(jié)點i的接近數(shù)定義為

(4)

其中，dij是節(jié)點i到節(jié)點j的距離。

接近數(shù)與介數(shù)一樣，都考慮到了整個網(wǎng)絡中任意兩個節(jié)點之間的最短路徑，但是，接近數(shù)最大的節(jié)點表示信息的流動具有最佳的觀察視野。一般而言，介數(shù)最大的節(jié)點并不一定就是接近數(shù)最大的節(jié)點。就社交網(wǎng)絡而言，一個用戶節(jié)點的接近數(shù)越大，其在整個網(wǎng)絡中信息能夠傳播的視野范圍也就越大，影響力也就越大，反之，影響力越小。

基于Pajek計算得到各用戶節(jié)點(UserID)的接近數(shù)(Closenesscentrality)，如圖5所示。

圖5 各節(jié)點的接近中心值

表3給出了網(wǎng)絡中接近中心性排名前10的用戶節(jié)點及其對應的接近數(shù)取值和數(shù)據(jù)歸一化處理后的取值。整個網(wǎng)絡中接近數(shù)的最大值為0.447613，最小值為0。

表3 接近數(shù)排名前30的節(jié)點

3.2.4 聚類系數(shù)研究

聚類系數(shù)可以定量刻畫社交網(wǎng)絡中一個人的任意兩個朋友之間也互為朋友的概率。這種可能性的大小反映了這個人的朋友圈的緊密程度。網(wǎng)絡中一個度為ki的節(jié)點i的聚類系數(shù)定義為

(5)

其中，Ei是節(jié)點i的Ei個鄰節(jié)點之間實際存在的邊數(shù)。在現(xiàn)實的網(wǎng)絡中，尤其是在特定的網(wǎng)絡中，由于相對高密度連接點的關系，節(jié)點總是趨向于建立一組嚴密的組織關系。這種相互關系可以利用聚類系數(shù)進行量化表示。聚類系數(shù)越大，其所在局部網(wǎng)絡的凝聚力越大，影響力也相對較大，反之，影響力越小。而這些節(jié)點通常并非是度值、介數(shù)、接近數(shù)較高的節(jié)點。

基于pajek計算得到各用戶節(jié)點(UserID)的聚類系數(shù)值(Clusteringcoefficient)，如圖6所示。表4給出了網(wǎng)絡中聚類系數(shù)排名前30的用戶節(jié)點及其對應的聚類系數(shù)值和數(shù)據(jù)歸一化處理后的取值。整個網(wǎng)絡中聚類系數(shù)的最大值為1，最小值為0。在一定時間內(nèi)，用戶之間的關系是可能發(fā)生變化的，可以隨時取消或添加好友，而聚類系數(shù)較大的節(jié)點，在一定時間內(nèi)，周圍節(jié)點對其取消關注的概率相對較小，周圍節(jié)點對其添加關注的概率相對較大。

圖6 各節(jié)點的聚類系數(shù)值

表4 聚類系數(shù)排名前30的節(jié)點

用戶聚類系數(shù)用戶聚類系數(shù)v791v270.9333333v841v1780.89010989v1721v2950.872727273v2201v1360.87012987v2351v2300.869565217v2531v2260.866666667v2581v1420.855072464v2851v1280.847619048v2891v2180.847619048v3021v70.833333333v3031v2370.833333333v3171v2450.833333333v3271v2750.833333333v3000.954545455v1580.826086957v1600.952380952v890.8222222

3.2.5 用戶影響力排序

用戶影響力指標為四個指標歸一化后所取均值，均值大小即代表影響力大小，記為Ai，計算公式為

(6)

其中，DCi，BCi，CCi，Ci分別為度中心性值、介數(shù)、接近數(shù)、聚類系數(shù)歸一化后的取值。圖7給出了所有用戶節(jié)點(UserID)及其對應的均值(AverageValue)。結果顯示，v186，v78，v263，v33，v42，v21等用戶節(jié)點在整個網(wǎng)絡中的影響力是比較大的。

圖7 各用戶節(jié)點的均值

目前，很多節(jié)點重要度排序方法并不能有效的將每個節(jié)點的重要度清楚的劃分，很多特征相似的節(jié)點是無法做到精細的排名的。圖8給出了所有用戶影響力排序(Rank)與其對應均值(AverageValue)之間的關系圖?？梢钥闯觯ス铝Ⅻc外(均值全部為零)，這種重要度劃分方法是接近線性關系的，能夠將某些相似節(jié)點的重要度區(qū)分出來。

圖8 總排序中各節(jié)點的均值

3.3 K-核分解法檢驗

本文將slavko好友圈的facebook關系網(wǎng)絡進行分解，通過比較相同k-殼值節(jié)點的排序，來判斷排序是否合理。K值的大小需要研究者根據(jù)數(shù)據(jù)自行決定，通常以3、5或10為間隔取k-殼值。為了更細致的說明各個節(jié)點的歸類情況，現(xiàn)取1為間隔，最終可得到k-殼值分別為0，1，2……，18的分解網(wǎng)絡。如圖11所示的18-核分解。由于所取間隔較小，存在k-殼值不同的節(jié)點的排序交叉集中的現(xiàn)象。

圖9 14-核分解

圖10 15-核分解

圖11 18-核分解

選取部分數(shù)據(jù)來進行分析。表5給出了間隔分別為1，2，5時的節(jié)點排序集中范圍的三組數(shù)據(jù)。選定k殼值間隔，通過比較在此間隔內(nèi)的節(jié)點數(shù)目及其對應的排序集中范圍和落在此范圍內(nèi)的節(jié)點所占比例，可以看出，k-殼值相同的節(jié)點的重要性排序是相對集中的，具有相似的影響力，且k-殼值大的節(jié)點影響力排名也相對靠前。

表5 間隔分別為1，2，5的節(jié)點排序集中范圍

整個網(wǎng)絡中各節(jié)點的k-殼值與排序分布如圖12所示，大部分相同k-殼值節(jié)點能夠收斂在特定的排序范圍內(nèi)。

圖12 各節(jié)點的k-殼值與排序分布圖

據(jù)此，我們可以看出本文所用的社交網(wǎng)絡用戶影響力評價體系是具有一定科學性的，排序結果也相對準確。

4 與HITS算法的比較與分析

HITS算法是一個經(jīng)典的網(wǎng)頁排序算法，它通過每個節(jié)點的權威值與樞紐值相互校正迭代來確定每個節(jié)點的影響力值，記為hub值。

建立slavko用戶好友圈的有向網(wǎng)絡并運用HITS算法計算出各節(jié)點的hub值。將本文方法與HITS算法進行結果比較，若取兩種方法的影響力排名前30的節(jié)點(如表6與表7所示)，則含有17個共同節(jié)點，重合率56.67%；若取兩種方法的影響力排名前40的節(jié)點，則含有32個共同節(jié)點，重合率80%；若取兩種方法的影響力排名前50名，則含有46個共同節(jié)點，重合率92%?？梢钥闯?，本文所用排序算法與HITS算法能夠在很大程度上吻合。

表6 HITS算法排序在1-30名的用戶節(jié)點的hub值

表7 本文所用算法排序在1-30名的用戶節(jié)點

對于大型的網(wǎng)絡，不同的排序算法得到的結果也必然存在差異，這是因為對衡量節(jié)點重要度所選取的角度不同，但都具有一定參考意義。通常HITS算法是作用在一定范圍的，很容易忽略一些末梢節(jié)點，并且易受垃圾連接的影響或發(fā)生主題漂移，結果的有效性稍差，而本文方法能夠找到HITS算法中一些容易被忽視的重要節(jié)點。傳統(tǒng)的網(wǎng)頁排序算法需要考慮到收斂性和有效性的問題，本文所用方法就無需考慮此問題，對于規(guī)模相對小的網(wǎng)絡而言，能體現(xiàn)出明顯的優(yōu)勢。在適用范圍上，網(wǎng)頁排序算法通常只適用于特定類型的社交網(wǎng)絡，本文方法則可以根據(jù)不同規(guī)則運用不同類型的社交網(wǎng)絡數(shù)據(jù)建立模型，適用范圍更廣。

5 總結和展望

本文提出了一種度中心性、介數(shù)中心性、接近中心性、聚類系數(shù)四指標綜合用戶影響力評價方法，通過對計算數(shù)據(jù)歸一化處理并取均值得到用戶影響力排序。通過仿真實驗以及k-核分解、與HITS算法比較驗證了此方法的科學性和正確性。這種方法弱化了將有向網(wǎng)絡視為無向網(wǎng)絡研究而帶來的誤差，并可以高效地得到重要節(jié)點，適用范圍更廣。

[1]Kleinberg J.Authoritative sources in a hyperlinked environment [J].IBM Research Report，1997，no RJ10076；Journal of the ACM，1999，46(5)：604-632.

[2]Page，Brin S，Motwami R，Winograd T.The PageRank citation ranking：Bring order to the Web [J].Tech Report，Stanford Digital Library Technology Project，1998.

[3]任曉龍，呂琳媛.網(wǎng)絡重要節(jié)點排序方法綜述[J].科學通報，2014，59(13)：1175-1197.

[4]丁兆云，賈焰，周斌，唐府.社交網(wǎng)絡影響力研究綜述[J].計算機科學，2014，41(1).

[5]Song X，Yun C，Hino K.Identifyirig opinion leaders in the blngosphere[C].the 16th ACM International Conference on Information and Knowledge Management(CIKM’07)，Lisboa，Portugal，2007，971-974.

[6]T H Haveliwala.Topic-sensitive PageRank：a context-sensitive ranking algorithm for Web search[J].IEEE Transactions on Knowledge and Data Engineering，2003，15(4)：784-796.

[7]Zhongwu Zhai，Hua Xu，Peifa Jia.Identifying Opinion Leaders in BBS[J].2008 IEEEWICACM International Conference on Web Intelligence and Intelligent Agent Technology WIIAT 08，2008.

[8]Cha M，Haddadi H，Benevenuto F.Measuring User Influence in Twitter：The Million Follower Fallacy[J].ICWSM，2010，10，10-17.

[9]Ye S，Wu S F.Measuring message propagation and social influence on Twitter.com[M].Berlin ：Springer Berlin Heidelberg，2010，216-231.

[10]Kitsak M，Gallos L K，Havlin S.Indentification of influential spreaders incomplex networks [J].Nature Physics，2010，6(11)：888-893.

[11]Ugander J，Karrer B，Backstrom L.The anatomy of the Facebook social graph[J].2010，aXiv：1111 4503v1.

[12]汪小帆，李翔，陳關榮.網(wǎng)絡科學導論[M].北京：高等教育出版社，2012.

(責任編輯：宋金寶)

Research on the Influence of Social Network Users Based on Complex Network

XU Jie1，2，WANG Ju-yun1，ZHANG Hai-yun1

(1.Science School，Communication University of China，Beijing 100024，China；2.School of Information Science and Technology，Beijing University of Chemical Technology，Beijing 100029，China)

Based on complex network theory，analysis of social network users influence can provide support for the study of social marketing，public opinion monitoring，information retrieval，and many other fields.Although it is possible for users to analyze the influence of social networks users based on the traditional PageRank algorithm，but there is still insufficient and high complexity.This article puts forward a kind of evaluation system that evaluate the influence to social network usersbased on undirected network，weakening the error caused by regarding directed network as undirected network，and can quickly get the important nodes，applies more broadly.First of all，using node's degree centrality，betweenness centrality，closeness centrality，clustering coefficient as a network node importance index，calculated by the data normalization and take the mean final evaluation，as a baseline for evaluation of important network node.Secondly，the k-core decomposition method was used to test sorting through coarse-graining to classify the nodes that have similar important degree.Finally，this paper takes an example，and verifies this method of the scientific and correct through the k-core decomposition and comparingwith HITS.

social networks；the influence of users；network node important degree；the k-core decomposition

2016-10-10

徐杰(1993-)，男(漢族)，河北保定人，北京化工大學碩士研究生，E-mail：1207394505@qq.com.

TP

A

1673-4793(2017)02-0067-07