基于多決策屬性的社會網絡核心節點識別

,

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

0 概述

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

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

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

1 算法描述

1.1 常用節點重要性評價指標

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

連接熵定義如下:

(1)

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

中心熵定義如下:

(2)

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

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

1.2 多目標優化算法NSGA-Ⅱ

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

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

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

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

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

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

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

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

2 NSGA-Ⅱ節點計算

2.1 目標函數

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

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

(3)

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

(4)

2.2 約束條件

mindi

(5)

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

Nmin

(6)

minpaths(v1,v2,…,vM)

maxpaths(v1,v2,…,vM)

(7)

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

minpaths(vi)

(8)

2.3 核心節點集的數目

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

3 基于多決策屬性的節點評價

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

圖1 美國ARPA網絡

圖2 Zachary空手道俱樂部網絡

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

表1 ARPA網絡節點重要性評估結果

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

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

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

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

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

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

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

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

圖3 APRA網絡Pareto邊界圖

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

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

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

圖4 節點集移除后網絡的劃分情況

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

圖5 Zachary網絡Pareto邊界圖

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

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

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

表4 Zachary網絡核心節點集評價結果

圖6 節點集A移除后的剩余網絡圖

圖7 節點集B移除后的剩余網絡圖

圖8 節點集A對網絡的覆蓋能力

圖9 節點集B對網絡的覆蓋能力

4 結束語

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

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

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

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

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

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

[12] 周蓮英,蔣 玲,蔣大飛.改進的NSGA-Ⅱ算法在MIMO-OFDMA系統多目標資源分配中的應用[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算法的配電網分布式電源優化配置[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] 張 翼,劉玉華,許凱華,等.一種基于互信息的復雜網絡節點重要性評估方法[J].計算機科學,2011,38(6):88-89,109.