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

李澤鵬,左 楊,王宏宇

(1.北京大學(xué)高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,北京 100871;2.北京大學(xué)信息科學(xué)技術(shù)學(xué)院,北京 100871)

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

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

(1.北京大學(xué)高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,北京 100871;2.北京大學(xué)信息科學(xué)技術(shù)學(xué)院,北京 100871)

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

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

1 引言

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

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

中心度方法主要是通過(guò)社交網(wǎng)絡(luò)中節(jié)點(diǎn)的度或節(jié)點(diǎn)間最短路徑等因素來(lái)判斷社交網(wǎng)絡(luò)中節(jié)點(diǎn)的影響力,計(jì)算復(fù)雜程度較低,因此這類(lèi)方法被廣泛應(yīng)用于社交網(wǎng)絡(luò)的結(jié)構(gòu)分析技術(shù)中[11].

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

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

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

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

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

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

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

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

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

(1)

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

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

(2)

且將滿(mǎn)足式(2)的節(jié)點(diǎn)割集S*稱(chēng)為G的核.

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

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

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

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

2 連通中心度

在本文中,用圖G=(V,E)表示社交網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),其中V表示節(jié)點(diǎn)集,E表示邊(連接)集.若無(wú)特別說(shuō)明,均指無(wú)向圖.記n=|V|為G的節(jié)點(diǎn)數(shù),m=|E|為G的邊數(shù).

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

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

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

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

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

2.1 連通中心度的定義

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

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

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

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

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

0≤φij(vt)≤1.

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

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

2.2 連通中心度的性質(zhì)

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

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

性質(zhì)1 設(shè)節(jié)點(diǎn)v是網(wǎng)絡(luò)圖G的葉子節(jié)點(diǎn),則CCON(v)=0.

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

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

性質(zhì)3 設(shè)v是網(wǎng)絡(luò)圖G的一個(gè)節(jié)點(diǎn),v在G中的所有鄰居節(jié)點(diǎn)構(gòu)成的集合記為N(v),若N(v)在G中的導(dǎo)出子圖是一個(gè)完全圖,則CCON(v)=0.

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

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

2.3 連通中心度的計(jì)算

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

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

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

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

(4) 計(jì)算出節(jié)點(diǎn)vt的連通中心度CCON(vt).

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

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

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

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é)點(diǎn)是v5,最小的是v1.

進(jìn)一步,每個(gè)節(jié)點(diǎn)的連通中心度與其在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的具體位置有著重要的關(guān)系.例如,在網(wǎng)絡(luò)圖G中,除節(jié)點(diǎn)v1外,v7,v8的連通中心度是最小的,這是因?yàn)槠溆喙?jié)點(diǎn)之間的經(jīng)過(guò)v7或v8的互不相交的路以及最短路都很少.從而說(shuō)明在進(jìn)行信息傳播時(shí),節(jié)點(diǎn)v7或v8起到的作用很小,對(duì)整個(gè)網(wǎng)絡(luò)中的影響也就很小.另外,節(jié)點(diǎn)v4的度數(shù)小于v9的度數(shù),但v4的連通中心度大于v9的連通中心度.這說(shuō)明節(jié)點(diǎn)的連通中心度不依賴(lài)于其度數(shù)的大小.

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

節(jié)點(diǎn)對(duì)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)絡(luò)中節(jié)點(diǎn)的連通中心度

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

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

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

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

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

證畢.

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

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

證畢.

定理4 對(duì)完全二部圖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é)點(diǎn)vi的連通中心度為

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

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

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

證明

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

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

同理可得:

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

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

證畢.

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

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

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

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

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

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

證畢.

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

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

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

節(jié)點(diǎn)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可以看出,通過(guò)連通中心度來(lái)判斷Karate俱樂(lè)部網(wǎng)絡(luò)中各節(jié)點(diǎn)的影響力時(shí),影響力最大的5個(gè)節(jié)點(diǎn)依次為:節(jié)點(diǎn)1,節(jié)點(diǎn)34,節(jié)點(diǎn)33,節(jié)點(diǎn)3,節(jié)點(diǎn)32.因此,通過(guò)連通中心度能夠準(zhǔn)確地選擇影響力較大的節(jié)點(diǎn).

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

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

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

5 結(jié)論

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

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

[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]許進(jìn),席酉民,汪應(yīng)洛.系統(tǒng)的核與核度(I)[J].系統(tǒng)科學(xué)與數(shù)學(xué),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]吳信東,李毅,李磊.在線(xiàn)社交網(wǎng)絡(luò)影響力分析[J].計(jì)算機(jī)學(xué)報(bào),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年出生于甘肅定西.北京大學(xué)信息科學(xué)技術(shù)學(xué)院博士后,主要研究方向?yàn)閳D論與組合優(yōu)化,社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).

E-mail:lizepeng@pku.edu.cn

左 楊 男,1990年出生于安徽安慶.北京大學(xué)信息科學(xué)技術(shù)學(xué)院碩士研究生,主要研究方向?yàn)樯缃痪W(wǎng)絡(luò)結(jié)構(gòu)分析.

王宏宇 女,1988年出生于黑龍江牡丹江.北京大學(xué)信息科學(xué)技術(shù)學(xué)院博士研究生,主要研究方向?yàn)閳D論與組合優(yōu)化,社交網(wǎng)絡(luò)結(jié)構(gòu).

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; 責(zé)任編輯:梅志強(qiáng)

國(guó)家自然科學(xué)基金(No.61672050,No.61372191,No.61572492,No.61572046,No.61502012);國(guó)家973重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(No.2013CB329600);中國(guó)博士后科學(xué)基金(No.2016M591013);江西省教育廳項(xiàng)目(No.GJJ150686)

TP399

A

0372-2112 (2016)12-2967-08

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.12.022