基于復雜網絡的社交網絡用戶影響力研究

徐杰，王菊韻，張海云

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

基于復雜網絡的社交網絡用戶影響力研究

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

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

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

社交網絡；用戶影響力；網絡節點重要度；k-核分解

1 引言

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

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

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

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

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

3 仿真實驗與結果分析

3.1 數據來源及模型構建

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

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

圖2 slavko的好友關系網絡

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

3.2 用戶影響力分析

3.2.1 度中心性研究

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

(1)

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

圖3 各節點的度中心性值

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

(2)

其中max為樣本數據的最大值，min為樣本數據的最小值。

整個網絡中度中心性最大值為0.174174，最小值為0。

表1 度中心性值排名前10的節點

3.2.2 介數中心性研究

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

(3)

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

圖4 各節點的介數中心性值

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

表2 介數排名前10的節點

3.2.3 接近中心性研究

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

(4)

其中，dij是節點i到節點j的距離。

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

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

圖5 各節點的接近中心值

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

表3 接近數排名前30的節點

3.2.4 聚類系數研究

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

(5)

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

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

圖6 各節點的聚類系數值

表4 聚類系數排名前30的節點

用戶聚類系數用戶聚類系數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分別為度中心性值、介數、接近數、聚類系數歸一化后的取值。圖7給出了所有用戶節點(UserID)及其對應的均值(AverageValue)。結果顯示，v186，v78，v263，v33，v42，v21等用戶節點在整個網絡中的影響力是比較大的。

圖7 各用戶節點的均值

目前，很多節點重要度排序方法并不能有效的將每個節點的重要度清楚的劃分，很多特征相似的節點是無法做到精細的排名的。圖8給出了所有用戶影響力排序(Rank)與其對應均值(AverageValue)之間的關系圖。可以看出，除去孤立點外(均值全部為零)，這種重要度劃分方法是接近線性關系的，能夠將某些相似節點的重要度區分出來。

圖8 總排序中各節點的均值

3.3 K-核分解法檢驗

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

圖9 14-核分解

圖10 15-核分解

圖11 18-核分解

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

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

整個網絡中各節點的k-殼值與排序分布如圖12所示，大部分相同k-殼值節點能夠收斂在特定的排序范圍內。

圖12 各節點的k-殼值與排序分布圖

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

4 與HITS算法的比較與分析

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

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

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

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

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

5 總結和展望

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

[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]任曉龍，呂琳媛.網絡重要節點排序方法綜述[J].科學通報，2014，59(13)：1175-1197.

[4]丁兆云，賈焰，周斌，唐府.社交網絡影響力研究綜述[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]汪小帆，李翔，陳關榮.網絡科學導論[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