李澤鵬,左 楊,王宏宇

(1.北京大學高可信軟件技術教育部重點實驗室,北京 100871;2.北京大學信息科學技術學院,北京 100871)

基于社交網(wǎng)絡結構的節(jié)點影響力度量方法

李澤鵬1,2,左 楊1,2,王宏宇1,2

(1.北京大學高可信軟件技術教育部重點實驗室,北京 100871;2.北京大學信息科學技術學院,北京 100871)

度量社交網(wǎng)絡節(jié)點影響力是社交網(wǎng)絡結構分析的關鍵問題之一.目前研究社交網(wǎng)絡節(jié)點影響力的方法主要有兩大類:中心度方法和節(jié)點刪除方法.前者主要通過度或最短路徑等因素來判斷節(jié)點的影響力,不考慮網(wǎng)絡的連通性；后者通過節(jié)點刪除后對網(wǎng)絡結構的破壞程度來判斷,計算復雜性很高,不適用于較大規(guī)模的社交網(wǎng)絡.通過結合社交網(wǎng)絡的局部連通度及節(jié)點間的最短路徑,提出了連通中心度來度量社交網(wǎng)絡中節(jié)點的影響力,并給出了連通中心度的計算方法和一些特殊網(wǎng)絡中節(jié)點的連通中心度的值.最后,通過實驗說明該指標能很好地度量社交網(wǎng)絡中節(jié)點的影響力.

社交網(wǎng)絡；節(jié)點影響力；中心度方法；連通中心度；最短路

1 引言

社交網(wǎng)絡的拓撲結構是網(wǎng)絡各項功能實現(xiàn)的基礎,對社交網(wǎng)絡的拓撲結構、功能及其之間的關系目前已有大量研究[1～3].分析社交網(wǎng)絡的拓撲結構,一個主要的方法是挖掘社交網(wǎng)絡中有重要影響力的節(jié)點,這些節(jié)點對社交網(wǎng)絡的信息傳播、網(wǎng)絡結構的演化起著關鍵的作用[4,5].因此,如何度量節(jié)點的影響力,如何在社交網(wǎng)絡中發(fā)現(xiàn)這些重要節(jié)點是研究社交網(wǎng)絡結構及功能的關鍵.

目前刻畫社交網(wǎng)絡節(jié)點影響力的方法主要有兩大類:一類是中心度方法,如度中心度[6]、緊密中心度[7]、介數(shù)中心度[8]、特征向量中心度[9,10]等；另一類是節(jié)點刪除方法,即通過度量節(jié)點刪除后對社交網(wǎng)絡的破壞程度來確定節(jié)點影響力的方法.

中心度方法主要是通過社交網(wǎng)絡中節(jié)點的度或節(jié)點間最短路徑等因素來判斷社交網(wǎng)絡中節(jié)點的影響力,計算復雜程度較低,因此這類方法被廣泛應用于社交網(wǎng)絡的結構分析技術中[11].

度中心度的方法是通過節(jié)點在社交網(wǎng)絡中度的大小來確定節(jié)點的影響力,即通過每個節(jié)點的鄰居節(jié)點數(shù)來判斷,其優(yōu)勢是計算代價小,可應用于大規(guī)模網(wǎng)絡中.但是,節(jié)點度的大小只能體現(xiàn)社交網(wǎng)絡結構的一個局部性質,所反映的是節(jié)點與其鄰居節(jié)點之間的關系,無法判斷節(jié)點在整個社交網(wǎng)絡中的影響力.為此,Chen等人[12]在度中心度的基礎上,進一步提出了局部中心度的方法來度量節(jié)點在社交網(wǎng)絡中的影響力.節(jié)點v的局部中心度CLOC(v)定義為:

其中Ni(u)表示到節(jié)點u的距離不超過i的所有節(jié)點構成的集合,i=1,2.局部中心度實際上是度中心度的推廣,節(jié)點v的局部中心度受到與v的距離不超過4的所有節(jié)點的影響,并且與v的距離越小對其影響越大.

緊密中心度和介數(shù)中心度方法主要是通過社交網(wǎng)絡中最短路徑來刻畫節(jié)點的影響力.節(jié)點v的緊密中心度CCLO(v)為:

其中d(v,w)表示節(jié)點v到節(jié)點w的距離,即它們之間的最短路徑的長度；節(jié)點v的介數(shù)中心度CBET(v)定義為:

其中σuw表示節(jié)點u與節(jié)點w之間最短路的條數(shù),σuw(v)表示這些最短路中經(jīng)過節(jié)點v的條數(shù).可以看出,緊密中心度所反映的是節(jié)點在社交網(wǎng)絡中的居中程度,節(jié)點的緊密中心度越大,說明此節(jié)點到其他節(jié)點的平均距離越小,即從此節(jié)點到其他節(jié)點的信息傳播越快,也就間接地表示該節(jié)點在社交網(wǎng)絡中的影響力越大.而介數(shù)中心度反映的是節(jié)點在社交網(wǎng)絡拓撲結構中位置的重要性,是對其他節(jié)點之間信息傳播影響的一種度量指標.節(jié)點的介數(shù)中心度越大,說明社交網(wǎng)絡中信息傳播時經(jīng)過該節(jié)點的信息量越大,即表示該節(jié)點在社交網(wǎng)絡中的影響力越大；反之也就越小.

特征向量中心度的方法主要是利用隨機游走的特征來判斷節(jié)點的重要程度.節(jié)點的特征向量中心度定義如下:

其中λ表示鄰接矩陣的最大特征值.特征向量中心度所反映的是節(jié)點的影響力與其鄰接節(jié)點的影響力相關,特別是與游走路徑上其他節(jié)點的影響力相關,其他節(jié)點影響力越大,當前節(jié)點的影響力也就越大,反之就越小.

另一類度量社交網(wǎng)絡中節(jié)點影響力的方法是節(jié)點刪除方法,主要通過刻畫節(jié)點刪除后對社交網(wǎng)絡結構的破壞程度來判斷節(jié)點的影響力,其考慮到社交網(wǎng)絡的整體連通程度,這類方法更多的是應用在系統(tǒng)科學領域的研究中,主要理論有網(wǎng)絡的堅韌集與堅韌度以及核與核度等.

對一個社交網(wǎng)絡圖G=(V,E),若節(jié)點子集S?V滿足G-S不連通,則稱S為G的一個節(jié)點割集.記C(G)為G中所有節(jié)點割集構成的集合；對一個節(jié)點割集S,記ω(G-S)為G-S的連通分支的數(shù)目.網(wǎng)絡圖G的堅韌度τ(G)[13]定義如下:

(1)

且將滿足式(1)的節(jié)點割集S*稱為G的堅韌集.網(wǎng)絡圖G的核度h(G)[14]定義如下:

h(G)=max{ω(G-V′)-|V′|:V′∈C(G)}

(2)

且將滿足式(2)的節(jié)點割集S*稱為G的核.

圖的核度最初被稱為離散數(shù)[15].Jung[15]提出圖的離散度是用于研究圖的Hamilton性問題的.此后,許進等[14]將圖的離散數(shù)引入到系統(tǒng)以及網(wǎng)絡的研究中,并形象地稱其為系統(tǒng)的核度.

從上述兩個定義可以看出,社交網(wǎng)絡圖的堅韌度與核度都是根據(jù)節(jié)點割集的階數(shù)和刪除這個節(jié)點割集后的網(wǎng)絡的連通分支數(shù)來定義的,均是刻畫社交網(wǎng)絡整體連通程度的指標.不同的是,根據(jù)圖的堅韌度來判斷時,堅韌度越大,說明連通性越好；但根據(jù)核度來判斷時,核度越小其連通性越好.相應地,堅韌集與核均是刻畫對網(wǎng)絡具有重要的或支配性的節(jié)點(或節(jié)點集)的指標,反映的是社交網(wǎng)絡的整體性質,無法對同一個網(wǎng)絡中不同節(jié)點之間的影響力作出判斷.而且,在應用堅韌度或核度來判斷社交網(wǎng)絡連通性及穩(wěn)定性時,計算量非常大,不適用于較大規(guī)模的社交網(wǎng)絡.對社交網(wǎng)絡中節(jié)點影響力,特別是在線社交網(wǎng)絡中節(jié)點影響力度量方法和模型的詳細介紹可參見文獻[16,17].

最近,仍有許多學者研究社交網(wǎng)絡的節(jié)點影響力.Ma,Ren和Ye等[18]提出了基于資源分配動態(tài)和k-層分解的節(jié)點影響力度量方法.Saito,Kimura 和Ohara等[19]提出了基于信息傳播的節(jié)點影響力度量方法,稱為超級傳遞者.Hu和Liu[20]結合特征向量中心度、介數(shù)中心度、緊密中心度、度中心度以及相互信息等因素,提出了基于線性判別分析的多指標算法.Kim和Anderson[21],Kas,Wachs和Carley等[22],Gao,Shi和Chen[23]研究了動態(tài)社交網(wǎng)絡下的節(jié)點影響力度量方法.另外,關于社交網(wǎng)絡影響力最大化的研究,可參見文獻[24～29].

本文在中心度方法與節(jié)點刪除方法的基礎上,提出了一種新的度量社交網(wǎng)絡中節(jié)點影響力的參數(shù):連通中心度.這個參數(shù)結合了節(jié)點在社交網(wǎng)絡結構中位置的重要性以及對其他節(jié)點之間的局部連通度的影響力.

2 連通中心度

在本文中,用圖G=(V,E)表示社交網(wǎng)絡的拓撲結構,其中V表示節(jié)點集,E表示邊(連接)集.若無特別說明,均指無向圖.記n=|V|為G的節(jié)點數(shù),m=|E|為G的邊數(shù).

對圖G=(V,E)中的兩個不相鄰的節(jié)點vi與vj,若節(jié)點子集S?V滿足在G-S中節(jié)點vi與vj不連通,則稱S為vi與vj的一個分離集.用c(vi,vj)表示G中節(jié)點vi與vj的最小分離集中節(jié)點的數(shù)目,稱c(vi,vj)為節(jié)點vi與vj的局部連通度.記

C(vi,vj)={v∈S:S是vi,vj的分離集且|S|=c(vi,vj)}.

例如,在圖1中,S={v4,v5}是節(jié)點v1與v9的一個分離集；S={v6,v7,v8}也是節(jié)點v1與v9的一個分離集；并且,節(jié)點v1與v9的局部連通度為2,C(v1,v9)= {v2,v3,v4,v5,v6}.

用p(vi,vj)表示G中節(jié)點vi與vj之間內(nèi)部互不相交的路的最大條數(shù).Menger[30]證明了c(vi,vj)與p(vi,vj)有如下關系:

定理1[30]設G=(V,E)是一個圖,vi與vj是G中不相鄰的兩個節(jié)點,則有c(vi,vj)=p(vi,vj).

2.1 連通中心度的定義

定義1 連通中心度.對一個圖G=(V,E),vi,vj是G中的兩個不相鄰的節(jié)點,任意節(jié)點vt∈V{vi,vj}對vi,vj的影響力定義為

其中σij表示節(jié)點vi與vj之間最短路的條數(shù),σij(vt)表示這些最短路中經(jīng)過節(jié)點vt的條數(shù).當vi,vj在G中相鄰時,定義φij(vt)=0.

節(jié)點vt的連通中心度定義為vt對G中所有的節(jié)點對vi與vj的影響力之和,即

特別,如果G-vt是一個完全圖,即G-vt中任意兩個節(jié)點是相鄰的,則定義CCON(vt)=0.

由定義1可知,對G中的任意兩個不相鄰的節(jié)點vi,vj以及vt∈V{vi,vj},有

0≤φij(vt)≤1.

若φij(vt)=0,則vt不在vi與vj的任何一個分離集中,也不在它們的最短路上,即說明在網(wǎng)絡G中,節(jié)點vt對vi,vj沒有影響；若φij(vt)=1,則節(jié)點vt分離vi與vj或節(jié)點vi與vj的任意最短路必經(jīng)過節(jié)點vt,說明在網(wǎng)絡G中,節(jié)點vt對vi,vj的影響很大.

連通中心度既考慮了經(jīng)過節(jié)點的最短路徑的數(shù)目,也考慮了此節(jié)點對其他節(jié)點對的局部連通性,是一個從網(wǎng)絡整體出發(fā)度量節(jié)點影響力的指標.節(jié)點的連通中心度越大,說明此節(jié)點對整個網(wǎng)絡的影響越大,重要性越高.反之,連通中心度越小,對網(wǎng)絡的影響越小,重要性越低.

2.2 連通中心度的性質

在一個社交網(wǎng)絡中,節(jié)點的連通中心度反映的是當前節(jié)點對其他節(jié)點相互交往過程中的影響力.連通中心度的大小受到社交網(wǎng)絡結構的限制.下面根據(jù)網(wǎng)絡的結構,分析連通中心度的性質.

根據(jù)定義1,如果節(jié)點v是G的葉子節(jié)點,那么vt對其余節(jié)點的影響力為0,即有:

性質1 設節(jié)點v是網(wǎng)絡圖G的葉子節(jié)點,則CCON(v)=0.

性質2 設G是包含n個節(jié)點的完全圖,則根據(jù)定義1可知,G中任意節(jié)點v的連通中心度為CCON(v)=0.

通過性質1和性質2可以看出,一個節(jié)點在社交網(wǎng)絡中的影響力與其度的大小沒有必然的聯(lián)系,而與網(wǎng)絡的整體結構或局部結構關系緊密.在性質1與性質2的基礎上,可得到更一般的結論.

性質3 設v是網(wǎng)絡圖G的一個節(jié)點,v在G中的所有鄰居節(jié)點構成的集合記為N(v),若N(v)在G中的導出子圖是一個完全圖,則CCON(v)=0.

通常,在一個規(guī)模較大的網(wǎng)絡中存在很多節(jié)點具有相同的影響力,下面給出判斷兩個節(jié)點具有相同連通中心度的一個充分條件.

性質4 設v,w是網(wǎng)絡圖G中的兩個節(jié)點,若G-v與G-w是同構的,則節(jié)點v與節(jié)點w的連通中心度相同,即有CCON(v)=CCON(w).

2.3 連通中心度的計算

對一個圖G=(V,E),分別用n=|V|和m=|E|表示G的節(jié)點數(shù)和邊數(shù).對G中的任意節(jié)點vt,計算vt的連通中心度最直觀的方式就是對每一對不相鄰的節(jié)點vi,vj計算出φij(vt),然后將所有的非相鄰節(jié)點對的值進行求和計算出CCON(vt),具體的計算步驟如下:

(1)需要計算G中每對不相鄰節(jié)點vi,vj間的內(nèi)部互不相交的路的條數(shù),即計算vi,vj的局部連通度,以及vi,vj之間最小節(jié)點割集的并構成的集合C(vi,vj).Ford 和Fulkerson[31,32]給出了一種利用最大流-最小割的方法來計算不相鄰節(jié)點的局部連通度.利用這種方法,Edmonds和Karp[33]給出一個時間復雜度為O(n·m2)的算法；對邊稠密的網(wǎng)絡,可利用Goldberg 和Tarjan[34]提出的relabel-to-front算法,其時間復雜度為O(n3).

(2)需要計算每對不相鄰節(jié)點間最短路經(jīng)的條數(shù).Floyd[35]給出了在一般圖中復雜度為O(n3)的算法,而對邊稀疏的網(wǎng)絡,Johnson[36]給出了一個時間復雜度為O(n2logn+nm)的算法.

(3) 根據(jù)定義1,計算節(jié)點vt∈V{vi,vj}對節(jié)點對vi,vj的影響力.

(4) 計算出節(jié)點vt的連通中心度CCON(vt).

綜上可知,通過上述算法計算圖G中任意節(jié)點vt的連通中心度CCON(vt)的時間復雜度為O(n3),其中n為G的節(jié)點數(shù).

以圖1所示的9個節(jié)點的網(wǎng)絡G為例,下面計算每個節(jié)點vt的連通中心度.G中任意不相鄰的節(jié)點對vi,vj的局部連通度、最短路的條數(shù)以及最小節(jié)點割集的并構成的集合見表1.

通過表1可得到G中節(jié)點連通中心度依次為:

CCON(v1)=0；CCON(v2)=12.1；CCON(v3)=3；

CCON(v4)=9；CCON(v5)=13.47；CCON(v6)=8.33；

CCON(v7)=CCON(v8)=2.07；CCON(v9)=8.67.

可以看出,影響力最大的節(jié)點是v5,最小的是v1.

進一步,每個節(jié)點的連通中心度與其在網(wǎng)絡拓撲結構中的具體位置有著重要的關系.例如,在網(wǎng)絡圖G中,除節(jié)點v1外,v7,v8的連通中心度是最小的,這是因為其余節(jié)點之間的經(jīng)過v7或v8的互不相交的路以及最短路都很少.從而說明在進行信息傳播時,節(jié)點v7或v8起到的作用很小,對整個網(wǎng)絡中的影響也就很小.另外,節(jié)點v4的度數(shù)小于v9的度數(shù),但v4的連通中心度大于v9的連通中心度.這說明節(jié)點的連通中心度不依賴于其度數(shù)的大小.

表1 圖1所示網(wǎng)絡中任意節(jié)點對的局部連通度、最短路條數(shù)和最小節(jié)點割集的并集的計算

節(jié)點對c(vi，vj)σijC(vi，vj)v1，v421{v2，v3，v5，v6，v9}v1，v522{v2，v3}v1，v621{v2，v3，v4，v5，v9}v1，v722{v2，v3，v4，v5，v6，v9}v1，v822{v2，v3，v4，v5，v6，v9}v1，v925{v2，v3，v4，v5，v6}v2，v621{v4，v5，v9}v2，v721{v4，v5，v6，v9}v2，v821{v4，v5，v6，v9}v2，v923{v4，v5，v6}v3，v421{v2，v5，v6，v9}v3，v621{v2，v4，v5，v9}v3，v721{v2，v4，v5，v6，v9}v3，v821{v2，v4，v5，v6，v9}v3，v922{v2，v4，v5，v6}v4，v521{v2，v6，v9}v4，v722{v2，v5，v6，v9}v4，v822{v2，v5，v6，v9}v4，v921{v2，v5，v6}v5，v623{v2，v4，v9}v5，v932{v2，v4，v6，v7，v8}v6，v721{v2，v4，v5，v9}v6，v821{v2，v4，v5，v9}

3 特殊網(wǎng)絡中節(jié)點的連通中心度

樹狀網(wǎng)絡是最簡單的一種連通網(wǎng)絡,下面通過一種簡單的方法,給出樹中任意非葉子節(jié)點的連通中心度.

定理2 設T=(V,E)是樹,v∈V是T的非葉子節(jié)點,則v的連通中心度為

其中r表示T-v的連通分支數(shù),nk表示T-v中第k個連通分支的節(jié)點數(shù),k=1,2,…,r.

證明 由于T是樹,對T中任意一對不相鄰的節(jié)點vi,vj,存在唯一的一條路連接節(jié)點vi與vj,因此有

所以,節(jié)點v只對T-v中不連通分支上的節(jié)點對有影響,從而

證畢.

定理3 設C=(V,E)是包含n個節(jié)點的圈,n≥5,則C中任意節(jié)點v的連通中心度為

證明 對C中任意節(jié)點v,C-v中不相鄰的節(jié)點對的數(shù)目為

證畢.

定理4 對完全二部圖Ks,t,s,t≥2,令Ks,t的二部劃分為V1,V2,其中V1={vi:0≤i≤s-1},V2= {uj:0≤j≤t-1},有

(1) 若s≠t,則任意節(jié)點vi的連通中心度為

任意節(jié)點uj的連通中心度為

其中i=0,1,…,s-1;j=0,1,…,t-1.

(2) 若s=t,則Ks,t中任意節(jié)點v的連通中心度為

證明

(1) 因為V1,V2是Ks,t的二部劃分,所以V1中的節(jié)點互不相鄰,V2中的節(jié)點也互不相鄰.故對V1中任意不相鄰節(jié)點對vi 1,vi2,它們之間存在|V2|條最短路,且對每個V2中的節(jié)點uj,有一條最短路經(jīng)過uj,因此,

其中j=0,1,…,t-1.

同理可得:

其中i=0,1,…,s-1.

(2) 若s=t,則由上述分析可知,對Ks,t中任意節(jié)點v,有

證畢.

定理5 對完全k-部圖Kn1,n2,…,nk,令它的k-部劃分為V1,V2,…,Vk,則對任意的節(jié)點vi∈Vi,vi的連通中心度為

其中i=1,2,…,k,n1+n2+…+nk=n.

證明 由于Kn1,n2,…,nk的不同部分之間的節(jié)點都是相鄰的,故每對不相鄰的節(jié)點屬于同一部分.對任意的節(jié)點對vr1,vr2∈Vr,vr1,vr2之間內(nèi)部不相交的路的條數(shù)為n-nr,因此Vi中的任意節(jié)點vi對vr1,vr2的影響力為:

其中i∈{1,2,…,k},且i≠r.進一步,Vr中互不相鄰的節(jié)點對的數(shù)目為:

因此,節(jié)點vi對Vr中所有節(jié)點對的影響了之和為:

所以,節(jié)點vi的連通中心度為:

證畢.

4 數(shù)據(jù)分析

本節(jié)以Karate俱樂部成員網(wǎng)絡[37]為例,如圖2所示,通過連通中心度計算每個成員的影響力,并將此指標與度中心度、緊密中心度和介數(shù)中心度等指標進行了比較,其中節(jié)點的標號與文獻[37]中是一致的.

表2 Karate俱樂部網(wǎng)絡節(jié)點影響力4種度量參數(shù)的比較

節(jié)點vCDEG(v)CCLO(v)CBET(v)CCON(v)1160．01724231．08235．83290．0147128．4547．993100．0169580．4088．91460．014086．3216．27530．011490．330．33640．0116315．8316．33740．0116315．8316．33840．0133300950．0156329．9631．281020．012990．450．451130．011490．330．331210．01111001320．01124001450．0153821．9628．531520．01124001620．01124001720．00862001820．01136001920．01124002030．0149315．5017．262120．01124002220．01136002310．01042002450．011909．6313．652530．011361．175．172630．011362．038．162720．01087002840．0137011．4615．702930．013510．956．213040．011632．0414．463140．013897．788．233260．0164074．1083．3633120．0156396．18117．3834160．01639145．23155．71

從表2可以看出,通過連通中心度來判斷Karate俱樂部網(wǎng)絡中各節(jié)點的影響力時,影響力最大的5個節(jié)點依次為:節(jié)點1,節(jié)點34,節(jié)點33,節(jié)點3,節(jié)點32.因此,通過連通中心度能夠準確地選擇影響力較大的節(jié)點.

連通中心度與介數(shù)中心度比較相似,介數(shù)中心度為0的節(jié)點的連通中心度也為0,但是,介數(shù)中心度不為0的節(jié)點,其連通中心度總是大于等于介數(shù)中心度,這是因為連通中心度在計算的過程中考慮了每對不相鄰節(jié)點間的內(nèi)部互不相交的路的條數(shù),即節(jié)點對的局部連通度.

一個節(jié)點v的連通中心度表示的是v對其他節(jié)點影響的大小,其值與度中心度、緊密中心度以及介數(shù)中心度沒有必然的聯(lián)系.例如,對節(jié)點30與節(jié)點31,CDEG(30)=CDEG(31),CCLO(30)CCON(31).因為節(jié)點27到其余很多節(jié)點的最短路或內(nèi)部互不相交的路經(jīng)過節(jié)點30,說明節(jié)點30對節(jié)點27與其他節(jié)點間的信息傳播起著重要的作用,從而使得節(jié)點30的連通中心度較大.而經(jīng)過節(jié)點31的最短路或內(nèi)部互不相交的路較少,因此節(jié)點31的連通中心度較小.這說明,在Karate俱樂部成員網(wǎng)絡中,節(jié)點30比節(jié)點31的影響力大.

節(jié)點對之間的內(nèi)部互不相交的路是信息并行傳遞的基礎,因此,利用連通中心度能更好地度量社交網(wǎng)絡中節(jié)點的影響力.

5 結論

本文在目前兩類度量網(wǎng)絡節(jié)點影響力方法的基礎上,即結合了中心度方法和節(jié)點刪除方法,提出了一種新的刻畫網(wǎng)絡中節(jié)點重要程度的方法.該方法既考慮了節(jié)點在網(wǎng)絡結構中位置的重要性,也考慮了節(jié)點對網(wǎng)絡局部連通性的影響,更全面地刻畫了節(jié)點的重要程度.在信息并行傳播的社交網(wǎng)絡中,其傳播路徑為兩個節(jié)點間的內(nèi)部互不相交的路,因此對具有這種特征的網(wǎng)絡,利用連通中心度來度量節(jié)點的重要性更準確一些.

不同性質的網(wǎng)絡具有不同的結構特征,我們所考慮的只是無向的連通網(wǎng)絡,對有向網(wǎng)絡和賦值網(wǎng)絡還需進一步的研究.另外,針對規(guī)模很大的網(wǎng)絡,計算其節(jié)點的連通中心度將耗費大量的計算資源,精確計算每個節(jié)點連通中心度不現(xiàn)實.所以,將連通中心度應用于大規(guī)模網(wǎng)絡中時,需要對計算過程做進一步的簡化,但要求對節(jié)點的連通中心度的影響不太大,這也是一個值得研究的問題.

[1]Newman M E.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256.

[2]Boccaletti S,Latora V,Moreno Y,et al.Complex networks:Structure and dynamics[J].Physics Reports,2006,424 (4):175-308.

[3]Zhang J,Zhou C,Xu X,et al.Mapping from structure to dynamics:A unified view of dynamical processes on networks[J].Physical Review E,2010,82 (2):026116.

[4]Zhou T,Wang B H.Catastrophes in scale-free networks[J].Chinese Physics Letters,2005,22 (5):1072-1075.

[5]Pastor-Satorras R,Vespignani A.Immunization of complex networks[J].Physical Review E,2002,65 (3):036104.

[6]Freeman L C.Centrality in social networks conceptual clarification[J].Social Networks,1979,1(3):215-239.

[7]Sabidussi G.The centrality index of a graph[J].Psychometrika,1966,31(4):581-603.

[8]Freeman L C.A set of measures of centrality based on betweenness[J].Sociometry,1977,40(1):35-41.

[9]Bonacich P.Factor and weighting approaches to status scores and clique identification[J].Journal of Mathematical Socilogy,1972,2(1):113-120.

[10]Bonacich P.Some unique properties of eigenvector centrality[J].Social Networks,2007,29(4):555-564.

[11]Borgatti S P,Everett M G.A graph-theoretic perspective on centrality[J].Social Networks,2006,28(4):466-484.

[12]Chen D B,Lü L Y,Shang M S,et al.Identifying influential nodes in complex networks[J].Physica A,2012,391 (4):1777-1787.

[13]Chvátal V.Tough graphs and Hamiltonian circuits[J].Discrete Mathematics,1973,5 (3):215-228.

[14]許進,席酉民,汪應洛.系統(tǒng)的核與核度(I)[J].系統(tǒng)科學與數(shù)學,1993,13(2):102-110. Xu J,Xi Y M,Wang Y L.On system core and coritivity (1)[J].Journal of System Science and Mathematical Science,1993,13(2):102-110.(in Chinese)

[15]Jung H A.On a class of posets and the corresponding comparability graphs[J].Journal of Combinatorial Theory Series B,1978,24(2):125-133.

[16]Sun J,Tang J.A survey of models and algorithms for social influence analysis[A].Social Network Data Analytics[C].New York:Springer,2011.177-214.

[17]吳信東,李毅,李磊.在線社交網(wǎng)絡影響力分析[J].計算機學報,2014,37(4):735-752. Wu X D,Li Y,Li L.Influence analysis of online social networks[J].Chinese Journal of Computers,2014,37(4):735-752.(in Chinese)

[18]Ma S J,Ren Z M,Ye C M,et al.Node influence identification via resource allocation dynamics[J].International Journal of Modern Physics C,2014,25(11):1450065.

[19]Saito K,Kimura M,Ohara K,et al.Super mediator—A new centrality measure of node importance for information diffusion over social network[J].Information Sciences,2016,329:985-1000.

[20]Hu F,Liu Y H.Multi-index algorithm of identifying important nodes in complex networks based on linear discriminant analysis[J].Modern Physics Letters B,2015,29(03):1450268.

[21]Kim H,Anderson R.Temporal node centrality in complex networks[J].Physical Review E,2012,85(2):605-624.

[22]Kas M,Wachs M,Carley K M,et al.Incremental algorithm for updating betweenness centrality in dynamically growing networks[A].Advances in Social Networks Analysis and Mining (ASONAM),2013 IEEE/ACM International Conference on IEEE[C].Niagara Falls,Canada:IEEE/ACM,2013.33-40.

[23]Gao Z X,Shi Y,Chen S Z.Measures of node centrality in mobile social networks[J].International Journal of Modern Physics C,2015,26(09):1550107.

[24]Zhang X,Zhu J,Wang Q,et al.Identifying influential nodes in complex networks with community structure[J].Knowledge-Based Systems,2013,42(2):74-84.

[25]Shakarian P,Salmento J,Pulleyblank W,et al.Reducing gang violence through network influence based targeting of social programs[A].Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].New York,USA:ACM,2014.1829-1836.

[26]He X,Kempe D.Stability of influence maximization[A].Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C]. New York,USA:ACM,2014.1256-1265.

[27]Zhou C,Zhang P,Zang W,et al.Maximizing the long-term integral influence in social networks under the voter model[A].Proceedings of the 23rd International Conference on World Wide Web Conferences Steering Committee[C].Seoul,Korea:ACM,2014.423-424.

[28]Morone F,Makse H A.Influence maximization in complex networks through optimal percolation[J].Nature,2015,524(7563):65-68.

[29]Lamba H,Narayanam R.A model-independent approach for efficient influence maximization in social networks[J].Social Network Analysis & Mining,2015,5(1):1-11.

[30]Menger K.Zur allgemeinen Kurventheorie[J].Fundamenta Mathematicae,1927,10:96-115.

[31]Ford L P,Fulkerson D R.Maximal flow through a network[J].Canadian Journal of Mathematics,1956,8(3):399-404.

[32]Ford L P,Fulkerson D R.Flows in Networks[M].Princeton NJ:Princeton University Press,1962.

[33]Edmonds J,Karp R M.Theoretical improvements in algorithmic efficiency for network flow problems[J].Journal of the ACM,1972,19(2):248-264.

[34]Goldberg V A,Tarjan E R.A new approach to the maximum flow problem[J].Journal of the ACM,1988,35(4):921-940.

[35]Floyd R W.Algorithm 97:Shortest path[J].Communications of the ACM,1962,5(6):345.

[36]Johnson D B.Efficient algorithms for shortest paths in sparse networks[J].Journal of the ACM,1977,24(1):1-13.

[37]Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33(4):452-473.

李澤鵬(通訊作者) 男,1987年出生于甘肅定西.北京大學信息科學技術學院博士后,主要研究方向為圖論與組合優(yōu)化,社交網(wǎng)絡拓撲結構.

E-mail:lizepeng@pku.edu.cn

左 楊 男,1990年出生于安徽安慶.北京大學信息科學技術學院碩士研究生,主要研究方向為社交網(wǎng)絡結構分析.

王宏宇 女,1988年出生于黑龍江牡丹江.北京大學信息科學技術學院博士研究生,主要研究方向為圖論與組合優(yōu)化,社交網(wǎng)絡結構.

An Influence Measure of Nodes Based on Structures of Social Networks

LI Ze-peng1,2,ZUO Yang1,2,WANG Hong-yu1,2

(KeyLaboratoryofHighConfidenceSoftwareTechnologies(PekingUniversity),MinistryofEducation,Beijing100871,China; 2.SchoolofElectronicsEngineeringandComputerScience,PekingUniversity,Beijing100871,China)

Identifying the influence of nodes is one of the major research topics in the structural analysis of social networks.The current measures of researching the node influence can be divided into two categories:centrality measure and node removal measure.The former mainly identifies the influence of the node by degree or shortest path,without considering the connectivity of social networks; while the latter by the damage of the structure of a social network when some nodes are removed.The node removal measure is incapable to be applied in large-scale since the computational complexity.We propose a new parameter,connectedness centrality,to identify the influence of nodes in networks by combining the local connectivity and shortest paths.We give a method to compute the connectedness centrality of the node and obtain the precise values in some specific networks.Finally,an experiment using a real-word network shows that our method can well identify the influence of the node in social networks.

social networks; node influence; centrality measure; connectedness centrality; shortest path

2015-01-30;

2016-01-20; 責任編輯:梅志強

國家自然科學基金(No.61672050,No.61372191,No.61572492,No.61572046,No.61502012);國家973重點基礎研究發(fā)展計劃(No.2013CB329600);中國博士后科學基金(No.2016M591013);江西省教育廳項目(No.GJJ150686)

TP399

A

0372-2112 (2016)12-2967-08

??學報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.12.022