社交網絡中個體對群體影響力分析

顧亦然，馬德營，孟繁榮

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

1 概 述

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

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

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

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

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

2 相關概念及定義

2.1 介數中心性

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

(1)

2.2 節點間的貢獻度

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

(2)

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

3 個體對群體影響力算法

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

3.1 個體間影響力

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

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

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

Cxk-1xk+αixk*BCxk*Cxkj

(3)

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

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

(4)

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

3.2 個體對群體影響力

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

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

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

(5)

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

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

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

輸入：G=(V,E)

輸出：節點vi對群體R的影響力

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

2.計算網絡節點間貢獻度矩陣Cn

3.計算網絡每節點BC值

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

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

6.END

4 仿真分析

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

表1 網絡參數

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

4.1 網絡仿真分析

4.1.1 Email

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

表2 Email網絡各算法排名前三節點

(a)Email網絡各節點FiR

(b)Email網絡105、333、299號節點傳播結果

(c)Email網絡23、333、389號節點傳播結果

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

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

4.1.2 Zachary

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

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

表3 Zachary網絡各算法排名前20%節點

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

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

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

4.2 定量分析

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

圖3 FiR算法結果定量分析

5 結束語

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