基于多决策属性的社会网络核心节点识别

,

(西安理工大学 自动化与信息工程学院,西安 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.