,

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

0 概述

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

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

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

1 算法描述

1.1 常用節(jié)點重要性評價指標

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

連接熵定義如下:

(1)

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

中心熵定義如下:

(2)

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

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

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

遺傳算法是一種全局優(yōu)化概率搜索算法,主要特點是不需要對目標函數進行操作,能夠直接對結構對象進行求解,現已被用于多個領域。遺傳算法的具體過程如下:

1)初始編碼。因為遺傳算法只能在其運算空間中進行運算,所以需要將待求解參數映射到其中。

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

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

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

5)變異。按照變異概率,對個體串結構中基因的值進行無規(guī)則改變。

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

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

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

2.1 目標函數

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

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

(3)

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

(4)

2.2 約束條件

mindi

(5)

在式(5)中,N代表去掉該節(jié)點之后,網絡中所有的邊數,即:

Nmin

(6)

minpaths(v1,v2,…,vM)

maxpaths(v1,v2,…,vM)

(7)

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

minpaths(vi)

(8)

2.3 核心節(jié)點集的數目

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

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

為驗證本文方法的可行性,選取美國的ARPA網絡和Zachary空手道俱樂部網絡(如圖1和圖2所示)進行實驗分析,并利用Matlab編程得出結果。

圖1 美國ARPA網絡

圖2 Zachary空手道俱樂部網絡

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

表1 ARPA網絡節(jié)點重要性評估結果

用本文提出的方法對ARPA網絡進行實驗。首先確定其約束條件,借助Ucinet和Gephi軟件得到刪除節(jié)點后的節(jié)點度和網絡中剩余邊的數目,即:

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

使用Dijkstra算法求得網絡中一點到其他所有節(jié)點的最短路徑數,Pajek求得網絡中所有最短路徑數,即:

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

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

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

設定種群大小和迭代次數均為100;錦標賽選擇;錦標賽規(guī)模為2;模擬二進制交叉;交叉概率為0.8;非均勻變異;變異概率為0.05,在ARPA網絡上構建Pareto邊界。

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

圖3 APRA網絡Pareto邊界圖

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

表2 APRA網絡NSGA和NSGA-Ⅱ的收斂代數

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

圖4 節(jié)點集移除后網絡的劃分情況

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

圖5 Zachary網絡Pareto邊界圖

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

表3 Zachary網絡NSGA和NSGA-Ⅱ的收斂代數

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

表4 Zachary網絡核心節(jié)點集評價結果

圖6 節(jié)點集A移除后的剩余網絡圖

圖7 節(jié)點集B移除后的剩余網絡圖

圖8 節(jié)點集A對網絡的覆蓋能力

圖9 節(jié)點集B對網絡的覆蓋能力

4 結束語

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

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

[2] 王 林,李璐婷.基于社會網絡分析的客戶流失預測[D].西安:西安理工大學,2014.

[3] 張 益.一種定量評估復雜網絡節(jié)點重要度的算法[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] 秦 李,楊子龍,黃曙光.復雜網絡的節(jié)點重要性綜合評價[J].計算機科學,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] 王 林,張婧婧.復雜網絡的中心化[J].復雜系統(tǒng)與復雜性科學,2006,3(1):13-20.

[10] 劉 堯.復雜網絡中關鍵節(jié)點發(fā)現技術研究[D].鄭州:解放軍信息工程大學,2009.

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

[12] 周蓮英,蔣 玲,蔣大飛.改進的NSGA-Ⅱ算法在MIMO-OFDMA系統(tǒng)多目標資源分配中的應用[J].無線通信技術,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] 孫建龍,吳鎖平,陳燕超.基于改進NSGA2算法的配電網分布式電源優(yōu)化配置[J].電力建設,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] 張 翼,劉玉華,許凱華,等.一種基于互信息的復雜網絡節(jié)點重要性評估方法[J].計算機科學,2011,38(6):88-89,109.