顧亦然，馬德營(yíng)，孟繁榮

(南京郵電大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210023)

1 概 述

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

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

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

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

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

2 相關(guān)概念及定義

2.1 介數(shù)中心性

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

(1)

2.2 節(jié)點(diǎn)間的貢獻(xiàn)度

社交網(wǎng)絡(luò)中節(jié)點(diǎn)之間的共同鄰居越多說明節(jié)點(diǎn)間的關(guān)系越密切。其對(duì)彼此的影響力就不僅與自身所處的拓?fù)湮恢糜嘘P(guān)，還與共同鄰居作用有關(guān)?，F(xiàn)實(shí)生活中，節(jié)點(diǎn)vi對(duì)vj的影響程度和節(jié)點(diǎn)vj對(duì)vi的影響程度是有區(qū)別的，因此引入貢獻(xiàn)度[11]這一概念。節(jié)點(diǎn)vi對(duì)vj的貢獻(xiàn)度定義如下：

(2)

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

3 個(gè)體對(duì)群體影響力算法

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

3.1 個(gè)體間影響力

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

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

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

Cxk-1xk+αixk*BCxk*Cxkj

(3)

其中，α為根據(jù)路徑遠(yuǎn)近設(shè)置的權(quán)重因子。

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

(4)

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

3.2 個(gè)體對(duì)群體影響力

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

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

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

(5)

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

3.3 個(gè)體對(duì)群體影響力算法描述

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

輸入：G=(V,E)

輸出：節(jié)點(diǎn)vi對(duì)群體R的影響力

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

2.計(jì)算網(wǎng)絡(luò)節(jié)點(diǎn)間貢獻(xiàn)度矩陣Cn

3.計(jì)算網(wǎng)絡(luò)每節(jié)點(diǎn)BC值

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

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

6.END

4 仿真分析

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

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

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

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

4.1.1 Email

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

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

(a)Email網(wǎng)絡(luò)各節(jié)點(diǎn)FiR

(b)Email網(wǎng)絡(luò)105、333、299號(hào)節(jié)點(diǎn)傳播結(jié)果

(c)Email網(wǎng)絡(luò)23、333、389號(hào)節(jié)點(diǎn)傳播結(jié)果

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

綜上可知，該算法能夠較為準(zhǔn)確地衡量個(gè)體對(duì)群體的影響力。

4.1.2 Zachary

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

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

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

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

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

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

4.2 定量分析

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

圖3 FiR算法結(jié)果定量分析

5 結(jié)束語(yǔ)

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