社交網(wǎng)絡中個體對群體影響力分析

顧亦然，馬德營，孟繁榮

(南京郵電大學 自動化學院，江蘇 南京 210023)

1 概 述

影響力分析是復雜網(wǎng)絡的重要研究內容，現(xiàn)實社會中的諸多系統(tǒng)都是以復雜網(wǎng)絡(complex network)的形式存在[1]。比如社會網(wǎng)絡、互聯(lián)網(wǎng)、交通網(wǎng)絡、生物網(wǎng)絡、社交網(wǎng)絡等。其中，社交網(wǎng)絡用戶影響力的研究成為當前的熱點之一。

為了深入研究及分析社交網(wǎng)絡的節(jié)點重要性，學者們從網(wǎng)絡結構等方面對節(jié)點影響力進行了廣泛研究[2-6]。其中度中心性[3]、PageRank[4]、k-shell[5]、介數(shù)中心性[6]等算法刻畫了節(jié)點在網(wǎng)絡拓撲結構上的重要程度。度中心性(degree centrality，DC)刻畫網(wǎng)絡的局部特性，無法從全局刻畫網(wǎng)絡特征；PageRank算法認為節(jié)點的重要性取決于網(wǎng)絡中指向該節(jié)點的節(jié)點數(shù)量和質量，容易陷入懸掛節(jié)點；k-shell是將網(wǎng)絡一層層分解找出不同層次不同影響力的節(jié)點，其度量重要性比較粗粒化。

此外，節(jié)點的重要性不僅體現(xiàn)在拓撲結構上，其社會關系、行為特性同樣對鄰居節(jié)點產(chǎn)生不可忽視的作用。Richardson等[7]提出影響力的計算以及使其最大化是一算法問題。Wang等[8]發(fā)現(xiàn)影響力的傳播大多發(fā)生在社團內部。王金龍等[9]提出了相對權重影響力模型并對影響力傳播路徑進行分析。肖云鵬等[10]提出了基于節(jié)點動態(tài)行為的影響力傳播模型，但其主要是刻畫影響力強度而未定量分析影響力。

當前，在線社交網(wǎng)絡發(fā)展迅速，社交平臺用戶之間或因為現(xiàn)實關系或共同的價值觀等逐漸形成網(wǎng)絡群體，在群體影響力的相互作用下，網(wǎng)絡群體行為涌現(xiàn)的更加迅速。例如，在微博社交網(wǎng)絡中，由于興趣等關注點的不同，一個用戶可能隸屬于不同社團，又由于親密關系的不同，一個用戶又可以在不同社團中進行消息的傳遞，那么這樣的節(jié)點實際上成為不同社團間信息傳播的橋梁，具有控制網(wǎng)絡信息傳播的能力。其傳播的影響力不僅僅是按照最短路徑產(chǎn)生作用，親密關系也成為消息傳遞，信息分享的一個重要因素。因此影響力的傳遞作用不僅和社交網(wǎng)絡的拓撲結構有關還和社會關系的因素有關，如文獻[11]發(fā)現(xiàn)節(jié)點貢獻度與節(jié)點重要性及其影響力范圍都存在一定關系。

因此，針對社交網(wǎng)絡中橋節(jié)點這樣的特殊位置節(jié)點在信息傳播中的重要性，考慮到此類節(jié)點信息交流的繁忙程度，以介數(shù)中心性作為描述節(jié)點拓撲結構重要性的參數(shù)；考慮到親密關系對傳播的影響，以節(jié)點間的貢獻度來描述節(jié)點親密程度，提出了一種個體對群體影響力算法，以此刻畫該節(jié)點對整個網(wǎng)絡的影響力貢獻情況，即個體對網(wǎng)絡群體的影響力。另外還對計算結果進行定量分析，用以研究其內在規(guī)律。

2 相關概念及定義

2.1 介數(shù)中心性

介數(shù)中心性(betweenness centrality，BC)是以經(jīng)過某一節(jié)點的最短路徑數(shù)目來刻畫節(jié)點重要性的指標。它體現(xiàn)了網(wǎng)絡中節(jié)點對網(wǎng)絡信息流動的影響力[12]。具體地，節(jié)點vi的介數(shù)中心性如下：

(1)

2.2 節(jié)點間的貢獻度

社交網(wǎng)絡中節(jié)點之間的共同鄰居越多說明節(jié)點間的關系越密切。其對彼此的影響力就不僅與自身所處的拓撲位置有關，還與共同鄰居作用有關。現(xiàn)實生活中，節(jié)點vi對vj的影響程度和節(jié)點vj對vi的影響程度是有區(qū)別的，因此引入貢獻度[11]這一概念。節(jié)點vi對vj的貢獻度定義如下：

(2)

其中，Γi和Γj分別為節(jié)點vi和vj鄰居節(jié)點的集合。

3 個體對群體影響力算法

文中將影響力看作是一種能夠在節(jié)點之間進行傳遞的能量。那么，從節(jié)點vi傳遞到vj的能量多少，就是節(jié)點vi對vj的影響力。結合網(wǎng)絡上刻畫節(jié)點控制信息流動的指標介數(shù)中心性以及節(jié)點之間相互影響作用的貢獻度概念，進一步描述個體間影響力的傳遞機制，建立個體對群體的影響力算法。

3.1 個體間影響力

正如上文所說，將影響力看作一種能夠在節(jié)點之間流動的能量，該能量沿著節(jié)點連邊進行擴散。如節(jié)點vi傳遞到vj的能量多少，就是節(jié)點vi對vj的影響力，可見，節(jié)點間的影響力刻畫的是節(jié)點之間影響力傳遞能力的大小。

定義：個體間影響力fn(i,j)為沿最短路徑從節(jié)點vi開始擴散到節(jié)點vj的影響力。

以計算fn(i,j)為例，計算過程如下：設從節(jié)點vi到節(jié)點vj的最短路徑為vi→vx1→vx2…vxk-1→vj，其距離為dij，則有：

Cxk-1xk+αixk*BCxk*Cxkj

(3)

其中，α為根據(jù)路徑遠近設置的權重因子。

由于節(jié)點的影響力會因節(jié)點之間的距離遠近產(chǎn)生差異，因此引入權重因子α[13]來分配計算權重。權重因子α與節(jié)點之間的距離dij存在以下關系：

(4)

其中，dij為始末兩節(jié)點間距離；dik為初始節(jié)點vi到節(jié)點vk的最短距離，k取正整數(shù)。

3.2 個體對群體影響力

如果說個體間的影響力刻畫的是節(jié)點之間影響力傳遞能力的大小，那么個體對群體影響力就是刻畫節(jié)點影響力的全局特性，即節(jié)點的影響力擴散對全網(wǎng)的影響程度。

定義：個體對群體影響力為節(jié)點vi對群體R中所有其他節(jié)點的影響力之和，記為FiR。

在實際計算中，F(xiàn)iR從源節(jié)點依次計算至整個群體，顯然復雜度太高。在研究中發(fā)現(xiàn)，并非要計算至整個網(wǎng)絡，原因有二：其一，根據(jù)微信以及Facebook最新數(shù)據(jù)分析，復雜在線網(wǎng)絡兩節(jié)點間平均距離為3左右；其二，由實際計算比對中發(fā)現(xiàn)，路徑的距離dij>3時，路徑權重α的大小對于計算結果排序并無明顯影響。基于上述分析，將FiR進一步定義如下：個體vi對群體R的影響力FiR為vi對距源節(jié)點路徑距離dij≤3所有節(jié)點的影響力之和。公式為：

(5)

其中，Vi表示距節(jié)點vi路徑距離dij≤3的節(jié)點集合。

3.3 個體對群體影響力算法描述

綜上所述，算法描述如下：

輸入：G=(V,E)

輸出：節(jié)點vi對群體R的影響力

1.通過廣度優(yōu)選搜索算法獲取節(jié)點vi到集合Vi中節(jié)點的路徑與距離表D_path

2.計算網(wǎng)絡節(jié)點間貢獻度矩陣Cn

3.計算網(wǎng)絡每節(jié)點BC值

4.計算節(jié)點vi到集合Vi中每個節(jié)點的影響力fn(i,j)

5.由式5將每條路徑影響力加和，求得FiR

6.END

4 仿真分析

文中研究的FiR算法刻畫的是節(jié)點影響力的全局特性，即節(jié)點的影響力擴散對全網(wǎng)的影響程度。顯然，個體對群體的影響力是衡量節(jié)點重要性的指標之一。另外影響力大的節(jié)點往往是信息傳播中的重要節(jié)點，信息傳播能力強，傳播至整個群體速度較快。基于這一思想，本節(jié)使用不同網(wǎng)絡數(shù)據(jù)，通過經(jīng)典的傳染病模型進行仿真可以較為直觀地分析節(jié)點信息傳播情況，以驗證算法的有效性。實驗使用的網(wǎng)絡分別為Email和Zachary，兩網(wǎng)絡參數(shù)如表1所示。

表1 網(wǎng)絡參數(shù)

首先使用SI傳染病模型，對Email網(wǎng)絡進行傳播驗證，其傳播概率為β=0.03。

4.1 網(wǎng)絡仿真分析

4.1.1 Email

對Email網(wǎng)絡進行FiR、BC、PageRank和k-shell算法分析，結果如表2所示，其中FiR的分析結果如圖1(a)所示。

表2 Email網(wǎng)絡各算法排名前三節(jié)點

(a)Email網(wǎng)絡各節(jié)點FiR

(b)Email網(wǎng)絡105、333、299號節(jié)點傳播結果

(c)Email網(wǎng)絡23、333、389號節(jié)點傳播結果

根據(jù)表2排序結果，首先將四種算法排在第一位的105、333、299號節(jié)點進行傳播仿真，結果如圖1(b)所示。可以看出，F(xiàn)iR計算出來的105號節(jié)點在傳播初期明顯優(yōu)于其他影響力指標得出的節(jié)點；基于上述的思想將FiR計算出來的23、333節(jié)點以及k-shell排序第二的389號節(jié)點進行傳播仿真實驗，結果如圖1(c)所示。從圖中亦能看出，在整個傳播仿真中23號節(jié)點較優(yōu)于333號節(jié)點和389號節(jié)點。

綜上可知，該算法能夠較為準確地衡量個體對群體的影響力。

4.1.2 Zachary

在Zachary網(wǎng)絡中分別計算節(jié)點的FiR、BC、PageRank和k-shell，得到的結果如表3所示。

為了更全面地驗證算法，本節(jié)傳播仿真采用SIR傳播。將文中算法排名前20%節(jié)點分別和其他三種算法得出的排名前20%節(jié)點進行傳播比對，傳播比對過程中去掉兩算法中相同的節(jié)點，選取時間步為40，傳播100次取平均，結果如圖2所示。由圖2(a)可知，文中算法選取的節(jié)點不但感染峰值比例高于后者，而且到達峰值的時間也比BC早；圖2(b)中兩者的差異更為明顯；圖2(c)中兩個最大感染比例差異雖沒有圖2(a)、(b)大，但到達最大值的時間卻比較滯后。通過上述分析對比，文中算法在SIR傳播仿真中依然有較好表現(xiàn)。

表3 Zachary網(wǎng)絡各算法排名前20%節(jié)點

(a)FiR與BC排名前20%對比

(b)FiR與PageRank排名前20%對比

(c)FiR與K-shell排名前20%對比

4.2 定量分析

對算法計算結果的定量分析過程如下：首先將Email網(wǎng)絡FiR進行升序排列，如圖3(a)所示，分別對橫縱坐標取對數(shù)，對曲線的走向進行分析發(fā)現(xiàn)，起始階段含有較多的節(jié)點但是這部分節(jié)點影響力的變化范圍卻很小；在曲線頂部雖然節(jié)點數(shù)較少，但其影響力卻明顯快速增加。通過數(shù)值計算可以得到前15.36%的節(jié)點影響力值總和等于后84.64%的節(jié)點影響力值總和。由此可知，只需對前15.36%節(jié)點施加影響力便能很大程度上影響整個網(wǎng)絡。當然進一步分析前20%節(jié)點對群體影響力占總影響力為58.38%，并未出現(xiàn)或接近公眾普遍認知的“二八效應”。同時，將FiR值均分150個區(qū)間段，取每段中間值代替每段的數(shù)值，計算落在每段節(jié)點的頻數(shù)，其頻數(shù)分布符合冪率分布,分布曲線為y=0.14*x-0.70。將數(shù)值和頻數(shù)取對數(shù)進行擬合，擬合的結果如圖3(b)所示，其斜率γ=-0.7。可見，網(wǎng)絡中少數(shù)節(jié)點的影響力遠遠超過大部分普通節(jié)點的影響力。

圖3 FiR算法結果定量分析

5 結束語

由于節(jié)點影響力物理表征和刻畫方法到目前為止并沒有一個相對完整的體系，文中將影響力看作是一種能夠在節(jié)點之間進行傳遞的能量，提出了FiR的計算方法，并建立了算法模型，進行了SI和SIR傳播仿真分析。結果表明，該算法在傳播仿真中表現(xiàn)優(yōu)異，能夠準確地找出對群體影響力大的節(jié)點。進一步分析FiR的分布情況得出影響力值的分布情況符合冪律分布，具有無標度現(xiàn)象。