基于多決策屬性的社會網(wǎng)絡(luò)核心節(jié)點(diǎn)識別

,

(西安理工大學(xué) 自動化與信息工程學(xué)院,西安 710048)

0 概述

識別社會網(wǎng)絡(luò)中的核心節(jié)點(diǎn)是網(wǎng)絡(luò)科學(xué)的重要研究內(nèi)容之一,在很多領(lǐng)域具有實(shí)際意義。例如:在謠言傳播網(wǎng)絡(luò)中,通過定位關(guān)鍵的傳播節(jié)點(diǎn),或者依靠領(lǐng)袖的領(lǐng)導(dǎo)能力引導(dǎo)公眾認(rèn)識,有效阻斷謠言的擴(kuò)散[1];在電信客戶流失預(yù)測分析中,找出高呼叫量流失客戶,將與其連接強(qiáng)度大的客戶看作是可能流失的客戶[2]。此外,由于網(wǎng)絡(luò)魯棒性和脆弱性,一方面通過保護(hù)核心節(jié)點(diǎn)維持網(wǎng)絡(luò)的可靠性,另一方面可以通過刪除核心節(jié)點(diǎn)達(dá)到破壞網(wǎng)絡(luò)的目的[3]。因此,準(zhǔn)確地識別出網(wǎng)絡(luò)中的核心節(jié)點(diǎn)是一項(xiàng)具有重要意義的課題。

由于網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性受到多個因素的影響,僅使用單一指標(biāo)難以準(zhǔn)確判斷節(jié)點(diǎn)的重要程度,因此需要從不同的角度出發(fā),結(jié)合多個重要性評價指標(biāo)進(jìn)行綜合評價。而現(xiàn)有的一些綜合評價方法雖然考慮了多項(xiàng)評價指標(biāo),但依賴主觀判斷的指標(biāo)選取降低了算法的可靠性,而且在評價過程中沒有考慮各個指標(biāo)之間的關(guān)聯(lián),降低了算法精度[4]。文獻(xiàn)[5]結(jié)合多個決策屬性提出一種基于局部線性嵌入(Locally Linear Embedding,LLE)的綜合評價方法,但同時對多個屬性進(jìn)行的評價行為帶來了較大的復(fù)雜度,限制了算法的擴(kuò)展使用。文獻(xiàn)[6]結(jié)合改進(jìn)的主成分分析法和TOPSIS法,雖然能夠有效地計算節(jié)點(diǎn)重要性,但其人為選取評價指標(biāo)構(gòu)造評價矩陣的過程使得算法缺乏客觀性。文獻(xiàn)[7]在評價過程中使用因子分析的方法計算各個評價指標(biāo)間的關(guān)聯(lián),避免了人為選取的主觀性,但是在因子分析的過程中可能會丟失重要信息,降低算法精度。

針對上述問題,本文在分析總結(jié)現(xiàn)有評價方法的基礎(chǔ)上,提出將多目標(biāo)優(yōu)化算法NSGA-Ⅱ結(jié)合KPP-Neg和KPP-Pos問題[8]作為目標(biāo)函數(shù),識別網(wǎng)絡(luò)中的核心節(jié)點(diǎn)。KPP-Neg和KPP-Pos問題是對社會網(wǎng)絡(luò)分析方法和系統(tǒng)科學(xué)分析方法的總結(jié),將其作為決策指標(biāo)可避免人為選取的主觀性,保證算法的全面性和可靠性。而多目標(biāo)優(yōu)化算法NSGA-Ⅱ則能高效求得目標(biāo)函數(shù)之間的均衡解。考慮到若網(wǎng)絡(luò)中檢測出較多的核心節(jié)點(diǎn)研究即失去意義[9],本文選取社會網(wǎng)絡(luò)分析中多個經(jīng)典的決策屬性對上述算法得到的節(jié)點(diǎn)再次進(jìn)行評價篩選,從而減少核心節(jié)點(diǎn)數(shù)目,提高算法精度。

1 算法描述

1.1 常用節(jié)點(diǎn)重要性評價指標(biāo)

文獻(xiàn)[8]將社會網(wǎng)絡(luò)分析方法和系統(tǒng)科學(xué)分析方法總結(jié)為KPP-Pos(Key Player Problem/Positive)和KPP-Neg(Key Player Problem/Negative)問題。KPP-Neg問題定義為尋找刪除后能夠最大程度分裂網(wǎng)絡(luò)的節(jié)點(diǎn)集,KPP-Pos問題定義為尋找最能夠覆蓋網(wǎng)絡(luò)的節(jié)點(diǎn)集[10]。文獻(xiàn)[11]對這2個問題提出了一種新的解決辦法——基于信息論中熵的概念,提出中心熵和連接熵的概念。節(jié)點(diǎn)的移除對中心熵造成較大影響的節(jié)點(diǎn)集,解決了KPP-Neg問題;對連接熵造成較大影響的節(jié)點(diǎn)集,解決了KPP-Pos問題。

連接熵定義如下:

(1)

其中,deg(vi)代表與節(jié)點(diǎn)vi相連的邊的總數(shù),N代表圖中所有邊的數(shù)目。

中心熵定義如下:

(2)

其中,paths(vi)是從節(jié)點(diǎn)vi到其他所有節(jié)點(diǎn)的最短路徑數(shù),paths(v1,v2,…,vM)代表圖中存在的所有最短路徑數(shù)。

本文算法的主要設(shè)計思想就是若某些節(jié)點(diǎn)的移除會對中心熵或者連接熵造成較大影響,這些節(jié)點(diǎn)就屬于核心節(jié)點(diǎn),2種熵值之間的差值決定了核心節(jié)點(diǎn)的數(shù)目。

1.2 多目標(biāo)優(yōu)化算法NSGA-Ⅱ

遺傳算法是一種全局優(yōu)化概率搜索算法,主要特點(diǎn)是不需要對目標(biāo)函數(shù)進(jìn)行操作,能夠直接對結(jié)構(gòu)對象進(jìn)行求解,現(xiàn)已被用于多個領(lǐng)域。遺傳算法的具體過程如下:

1)初始編碼。因?yàn)檫z傳算法只能在其運(yùn)算空間中進(jìn)行運(yùn)算,所以需要將待求解參數(shù)映射到其中。

2)適應(yīng)度計算。適應(yīng)度是遺傳算法中個體性能的評價指標(biāo),度值越高即個體適應(yīng)環(huán)境的能力越強(qiáng),這樣的個體也更有機(jī)會遺傳到下一代當(dāng)中進(jìn)行繁殖。

3)選擇。根據(jù)個體的適應(yīng)度值來選擇遺傳進(jìn)入下一代中的個體,適應(yīng)度值較大的優(yōu)良個體有更大的概率遺傳到下一代中。

4)交叉。按照交叉概率對不同個體的相同部分進(jìn)行交換,生成新的個體[12]。

5)變異。按照變異概率,對個體串結(jié)構(gòu)中基因的值進(jìn)行無規(guī)則改變。

6)終止。設(shè)定終止條件,如給定最大迭代次數(shù)或者種群中個體適應(yīng)度差異較小時停止。

文獻(xiàn)[13]提出的非支配排序遺傳算法NSGA在解決多目標(biāo)優(yōu)化問題中發(fā)揮了巨大作用,但由于其復(fù)雜度高,不能保存最優(yōu)個體,并且需人為設(shè)定共享半徑,使其不能被廣泛地使用。文獻(xiàn)[14]對NSGA進(jìn)行優(yōu)化,提出的NSGA-Ⅱ算法解決了NSGA存在的缺陷,在多目標(biāo)優(yōu)化問題中得到了廣泛使用。

2 NSGA-Ⅱ節(jié)點(diǎn)計算

2.1 目標(biāo)函數(shù)

文獻(xiàn)[8]通過對基于社會網(wǎng)絡(luò)分析方法和系統(tǒng)科學(xué)分析方法評價節(jié)點(diǎn)重要性的總結(jié)提出的KPP-Pos和KPP-Neg問題,從節(jié)點(diǎn)在整個網(wǎng)絡(luò)中的位置特性和刪除節(jié)點(diǎn)后網(wǎng)絡(luò)的分裂程度2個方面評價節(jié)點(diǎn),而不是對多個單一的屬性值的組合。所以,將這2個問題作為決策屬性可以保證算法的客觀性和可靠性。

針對KPP-Pos問題,文獻(xiàn)[15]提出用連接熵解決,即使節(jié)點(diǎn)集的連接熵有最大值,以節(jié)點(diǎn)集連接熵最大為第1個目標(biāo)函數(shù):

(3)

針對KPP-Neg問題,文獻(xiàn)[15]提出用中心熵解決,即使節(jié)點(diǎn)集的中心熵有最大值,以節(jié)點(diǎn)集連接熵最大為第2個目標(biāo)函數(shù):

(4)

2.2 約束條件

mindi

(5)

在式(5)中,N代表去掉該節(jié)點(diǎn)之后,網(wǎng)絡(luò)中所有的邊數(shù),即:

Nmin

(6)

minpaths(v1,v2,…,vM)

maxpaths(v1,v2,…,vM)

(7)

借助Dijkstra算法求解從節(jié)點(diǎn)vi出發(fā)到其他所有節(jié)點(diǎn)最短路徑數(shù)paths(vi),所以,有:

minpaths(vi)

(8)

2.3 核心節(jié)點(diǎn)集的數(shù)目

設(shè)M是評價節(jié)點(diǎn)重要性的所有屬性集合,包括節(jié)點(diǎn)度中心性、介數(shù)中心性、KPP-Pos和KPP-Neg、特征向量中心性等。M={m1,m2,…mn}?A是在實(shí)驗(yàn)中選取的部分目標(biāo)屬性,由于不同的網(wǎng)絡(luò)上對于核心節(jié)點(diǎn)的側(cè)重點(diǎn)不同,因此集合M的選取在不同的網(wǎng)絡(luò)上是不相同的。

3 基于多決策屬性的節(jié)點(diǎn)評價

為驗(yàn)證本文方法的可行性,選取美國的ARPA網(wǎng)絡(luò)和Zachary空手道俱樂部網(wǎng)絡(luò)(如圖1和圖2所示)進(jìn)行實(shí)驗(yàn)分析,并利用Matlab編程得出結(jié)果。

圖1 美國ARPA網(wǎng)絡(luò)

圖2 Zachary空手道俱樂部網(wǎng)絡(luò)

首先對ARPA網(wǎng)絡(luò)用現(xiàn)有的節(jié)點(diǎn)重要性評價方法進(jìn)行評價,結(jié)果如表1所示,將文獻(xiàn)[14-16]方法的評價結(jié)果作為對比。

表1 ARPA網(wǎng)絡(luò)節(jié)點(diǎn)重要性評估結(jié)果

用本文提出的方法對ARPA網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)。首先確定其約束條件,借助Ucinet和Gephi軟件得到刪除節(jié)點(diǎn)后的節(jié)點(diǎn)度和網(wǎng)絡(luò)中剩余邊的數(shù)目,即:

Nmin=22,Nmax=24,mindi=2,maxdi=4

使用Dijkstra算法求得網(wǎng)絡(luò)中一點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑數(shù),Pajek求得網(wǎng)絡(luò)中所有最短路徑數(shù),即:

minpaths(vi)=19,maxpaths(vi)=37

minpaths(v1,v2,…,vn)=380

maxpaths(v1,v2,…,vn)=420

設(shè)定種群大小和迭代次數(shù)均為100;錦標(biāo)賽選擇;錦標(biāo)賽規(guī)模為2;模擬二進(jìn)制交叉;交叉概率為0.8;非均勻變異;變異概率為0.05,在ARPA網(wǎng)絡(luò)上構(gòu)建Pareto邊界。

圖3給出了ARPA網(wǎng)絡(luò)的Pareto最優(yōu)解邊界圖,其中:橫軸代表了KPP-Neg問題,即節(jié)點(diǎn)集刪除后對網(wǎng)絡(luò)的分裂能力;縱軸代表了KPP-Pos問題,即節(jié)點(diǎn)集對網(wǎng)絡(luò)的覆蓋能力;點(diǎn)A代表節(jié)點(diǎn)集[2,3,15];點(diǎn)B代表節(jié)點(diǎn)集[3,6,12];點(diǎn)C代表節(jié)點(diǎn)集[3,6,14];點(diǎn)D代表節(jié)點(diǎn)集[3,12,19]。可以明顯看出,點(diǎn)B和點(diǎn)C都落在了Pareto邊界上,即這2個節(jié)點(diǎn)集不僅很好地覆蓋了全網(wǎng)絡(luò),而且移除后能夠很大程度地分裂剩余網(wǎng)絡(luò)。

圖3 APRA網(wǎng)絡(luò)Pareto邊界圖

從在給定相同的種群規(guī)模、進(jìn)化代數(shù)、交叉概率、變異概率的情況下,根據(jù)所需要的收斂代數(shù)判斷其收斂速度,一般來說,所需收斂代數(shù)越小代表算法的收斂速度越快。由表2可以看出,在相同的參數(shù)下,NSGA-Ⅱ所需的收斂代數(shù)小于NSGA的收斂代數(shù),即表明NSGA-Ⅱ的收斂速度較快且算法復(fù)雜度較低。

表2 APRA網(wǎng)絡(luò)NSGA和NSGA-Ⅱ的收斂代數(shù)

圖4給出了由上述不同方法得到的核心節(jié)點(diǎn)集刪除后對網(wǎng)絡(luò)的分裂程度。可以看出,節(jié)點(diǎn)集B和節(jié)點(diǎn)集C的刪除將網(wǎng)絡(luò)劃分成4個部分,節(jié)點(diǎn)集A、B僅將網(wǎng)絡(luò)分成2個部分,節(jié)點(diǎn)集B、C的分裂能力比A、B強(qiáng)。所以,選擇節(jié)點(diǎn)集B和C作為APRA網(wǎng)絡(luò)的核心節(jié)點(diǎn)集,這個結(jié)果與文獻(xiàn)[15]中的結(jié)果類似,驗(yàn)證了算法的正確性。

圖4 節(jié)點(diǎn)集移除后網(wǎng)絡(luò)的劃分情況

在Zachary空手道俱樂部網(wǎng)絡(luò)上尋找核心節(jié)點(diǎn)集,首先構(gòu)建該網(wǎng)絡(luò)的Pareto邊界圖,其中:

Nmin=22,Nmax=24

mindi=2,maxdi=4

minpaths(vi)=40

maxpaths(vi)=65

minpaths(v1,v2,…,vn)=1 056

maxpaths(v1,v2,…,vn)=1 100

Zachary空手道俱樂部網(wǎng)絡(luò)Pareto邊界圖如圖5所示,其中:橫軸代表了KPP-Neg問題,即節(jié)點(diǎn)集刪除后對網(wǎng)絡(luò)的分裂能力;縱軸代表了KPP-Pos問題,即節(jié)點(diǎn)集對網(wǎng)絡(luò)的覆蓋能力。 可以看出,有25個節(jié)點(diǎn)集落在了Pareto邊界上,代表這些節(jié)點(diǎn)集不僅很好地覆蓋了網(wǎng)絡(luò),且移除后很大程度地分裂了剩余網(wǎng)絡(luò)。但25個節(jié)點(diǎn)集對于該網(wǎng)絡(luò)來說產(chǎn)生了冗余,所以,采用二次評價的方法篩選節(jié)點(diǎn)集。

圖5 Zachary網(wǎng)絡(luò)Pareto邊界圖

在給定相同的種群規(guī)模、進(jìn)化代數(shù)、交叉概率和變異概率的情況下,根據(jù)所需要的收斂代數(shù)判斷其收斂速度。從表3中可以看出,在相同參數(shù)下,NSGA-Ⅱ所需的收斂代數(shù)小于NSGA,即表明NSGA-Ⅱ的收斂速度較快且算法復(fù)雜度較低。

表3 Zachary網(wǎng)絡(luò)NSGA和NSGA-Ⅱ的收斂代數(shù)

在得到的節(jié)點(diǎn)集上進(jìn)行二次評價,首先需要選取評價指標(biāo)集,本文選取社會網(wǎng)絡(luò)分析方法中點(diǎn)度中心性(DC)、特征向量中心性(EC)、接近中心性(CC)、介數(shù)中心性(BC)作為二次評價指標(biāo)。從表4中可以看出,節(jié)點(diǎn)集[1,2,3,33,34]和節(jié)點(diǎn)集[1,3,32,33,34]具有較高的指標(biāo)值。若A代表節(jié)點(diǎn)集[1,2,3,33,34],B代表節(jié)點(diǎn)集[1,3,32,33,34],圖6～圖9給出了A、B在整個網(wǎng)絡(luò)中的覆蓋能力及移除后對網(wǎng)絡(luò)的劃分情況。可以看出,A、B節(jié)點(diǎn)集不僅很好地覆蓋了全網(wǎng)絡(luò),而且在移除后,很大程度地分裂了剩余網(wǎng)絡(luò),所以選取該節(jié)點(diǎn)集作為Zachary空手道俱樂部網(wǎng)絡(luò)的核心節(jié)點(diǎn)集。在Zachary空手道俱樂部網(wǎng)絡(luò)中,通過繪制Pareto邊界圖,得到了落在邊界上滿足條件的25個節(jié)點(diǎn)集,而二次評價的方法進(jìn)一步將節(jié)點(diǎn)集的數(shù)目從25減少到2,有效地提高了算法的精度。

表4 Zachary網(wǎng)絡(luò)核心節(jié)點(diǎn)集評價結(jié)果

圖6 節(jié)點(diǎn)集A移除后的剩余網(wǎng)絡(luò)圖

圖7 節(jié)點(diǎn)集B移除后的剩余網(wǎng)絡(luò)圖

圖8 節(jié)點(diǎn)集A對網(wǎng)絡(luò)的覆蓋能力

圖9 節(jié)點(diǎn)集B對網(wǎng)絡(luò)的覆蓋能力

4 結(jié)束語

針對單一指標(biāo)評價的局限性和片面性,以及現(xiàn)有綜合評價方法不夠準(zhǔn)確等問題,本文使用多目標(biāo)優(yōu)化算法NSGA-Ⅱ解決KPP-Neg和KPP-Pos問題以尋找網(wǎng)絡(luò)中的核心節(jié)點(diǎn)集,當(dāng)?shù)玫降墓?jié)點(diǎn)集數(shù)量較大時對其進(jìn)行再次評價。在美國APRA網(wǎng)絡(luò)和Zachary空手道俱樂部網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果表明,本文方法能夠準(zhǔn)確地識別出核心節(jié)點(diǎn)集。下一步將結(jié)合實(shí)際項(xiàng)目和綜合應(yīng)用研究基于多決策屬性的節(jié)點(diǎn)重要性評價方法。

[1] 熊 熙,胡 勇.基于社交網(wǎng)絡(luò)的觀點(diǎn)傳播動力學(xué)研究[J].物理學(xué)報,2012,61(15):104-110.

[2] 王 林,李璐婷.基于社會網(wǎng)絡(luò)分析的客戶流失預(yù)測[D].西安:西安理工大學(xué),2014.

[3] 張 益.一種定量評估復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度的算法[J].計算機(jī)工程,2011,37(20):87-88,96.

[4] ATAPATTU S,TELLAMBURA C,JIANG Hai.Energy Detection Based Cooperative Spectrum Sensing in Cognitive Radio Networks[J].IEEE Transactions on Wireless Communications,2011,10(4):1232-1241.

[5] HU Fang,LIU Yuhua,JIN Jianzhi.Multi-index Evaluation Algorithm Based on Locally Linear Embedding for the Node Importance in Complex Networks[C]//Proceedings of International Symposium on Distributed Computing and Applications to Business,Engineering and Science.Washington D.C.,USA:IEEE Press,2014:138-142.

[6] 秦 李,楊子龍,黃曙光.復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)重要性綜合評價[J].計算機(jī)科學(xué),2015,42(2):60-64.

[7] ZHANG Mingqing,WU Xuguang.Evaluating Node Importance in Complex Networks Based on Factor Analysis[C]//Proceedings of International Conference on Computer Science and Network Technology.Washington D.C.,USA:IEEE Press,2011:1545-1548.

[8] BORGATTI S P.Identifying Sets of Key Players in a Social Network[C]//Proceedings of International Conference on Integration of Knowledge Intensive Multi-Agent Systems.Berlin,Germany:Springer,2003:21-34.

[9] 王 林,張婧婧.復(fù)雜網(wǎng)絡(luò)的中心化[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2006,3(1):13-20.

[10] 劉 堯.復(fù)雜網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)技術(shù)研究[D].鄭州:解放軍信息工程大學(xué),2009.

[11] 陳 勇,胡愛群,胡 嘯.通信網(wǎng)中節(jié)點(diǎn)重要性的評價方法[J].通信學(xué)報,2004,25(8):129-134.

[12] 周蓮英,蔣 玲,蔣大飛.改進(jìn)的NSGA-Ⅱ算法在MIMO-OFDMA系統(tǒng)多目標(biāo)資源分配中的應(yīng)用[J].無線通信技術(shù),2013,22(2):24-29.

[13] DEB K,PRATAP A,AGARWAL S,et al.A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

[14] 孫建龍,吳鎖平,陳燕超.基于改進(jìn)NSGA2算法的配電網(wǎng)分布式電源優(yōu)化配置[J].電力建設(shè),2014,35(2):86-90.

[15] ORTIZ-ARROYO D,HUSSAIN D M A.An Information Theory Approach to Identify Sets of Key Players[C]//Proceedings of the 1st European Conference on Intelligence and Security Informatics.Esbjerg,Denmark:[s.n.],2008:15-26.

[16] 張 翼,劉玉華,許凱華,等.一種基于互信息的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性評估方法[J].計算機(jī)科學(xué),2011,38(6):88-89,109.