基于多属性决策的复杂网络关键影响力节点的识别研究

张格豪,刘 伟,王睿鑫垚,厉鑫鹏,龚子忱,陈一源,陈海洋

(无锡学院 物联网工程学院,江苏 无锡 214105)

0 引言

复杂网络的研究已成为现代科学的热点之一,因为复杂网络具有高度的动态性、多样性、非线性和不确定性,对复杂网络中具有关键影响力的节点的研究也成为当下复杂网络研究的热点之一[1-4],可以通过找到网络中最具有关键影响力的节点,并预测网络的演化趋势和危机事件。关键节点是指对网络结构和功能具有重要影响的节点,研究复杂网络的关键影响力节点对于解决诸如网络攻击和崩溃、疾病传播、社交网络的社区发现、推荐系统、金融风险管理、轨道交通等现实问题具有重要意义[5-9],在城市公交网络中通过识别关键公交网络节点可保证城市公交网络的安全运营。此外,还可以通过识别网络中的关键影响力节点来设计和优化网络的性能和功能,促进网络的发展和创新。因此,对复杂网络中关键影响力节点的研究已经成为许多领域的关键问题之一,如计算机科学、生物学、社会学等[10]。

在先前的研究中,为了识别复杂网络中的关键影响力节点,提出了许多定量分析方法,主要包括系统科学分析方法[11]和社交网络分析方法。在系统科学分析方法中,节点的重要性等同于节点从网络中删除的破坏性。如节点收缩法[12],节点收缩法即是将节点及其邻居节点进行收缩成一个新的节点,观察网络是否能够非常好地凝聚在一起,是识别重要节点的一个标准,虽然节点收缩方法可以导致网络拓扑结构的变化,但它们可能会忽略节点之间的关系信息。社交网络分析方法认为节点的重要性可以通过节点中心性来度量,包括度中心性(Degree Centrality, DC)[13]、紧密度中心性(Closeness Centrality, CC)[14]、介数中心性(Betweenness Centrality, BC)[15]、K-壳分解法(K-shell decomposition)[2]、特征向量中心性(Eigenvector Centrality, EC)[13]、结构洞(Structural Holes, SH)[16]、桥中心性(Bridgeness Centrality, Bri)[17]等。这些中心性度量从不同的方面来描述节点的影响力。DC通过邻居节点的数量来描述节点的影响力,但它没有考虑全局网络结构。BC根据通过节点的最短路径的数量来识别有影响力的节点,但在真实网络中信息流可能不会沿着最短路径流动。CC通过评估访问其他节点的难易程度来评估节点的影响力,但它不适用于非中心化网络。K-shell通过确定节点在网络中的位置来识别节点的影响力,但其忽略了节点在网络中的全局影响力。EC根据观察节点邻居节点的数量及邻居节点的影响力来确定节点的重要性,但在真实网络上可能会出现分数局部化现象。SH通过节点与其邻居节点的约束系数来描述节点的影响力,约束系数越小,就越容易获取资源,但它只描述了节点局部性质。Bri从全局考虑节点在网络中的连通性影响力,但它忽略了节点之间的影响力。

目前,已经有许多中心性度量算法来识别网络中的具有关键影响力的节点,其中大多数仅采用单一指标来评估节点的影响力,所有这些单一性方法都有其自身的缺点和局限性。因此,诸多研究者提出了基于多属性融合的方法,如陈妤等[18]基于排序学习的方法,选择了度中心性、特征向量中心性、K-shell3个属性作为节点重要性的特征指标。于会等[19]基于TOPSIS选取了4种指标作为决策评价方案,通过计算各节点方案到最佳理想方案的距离来确定节点的重要性。胡钢等[20]提出了基于信息熵理论计算各属性的权重值,并通过计算基于相关系数矩阵的各节点方案与正负理想方案的距离来确定节点的重要性。Yang等[21]提出了基于灰度关联分析和SIR模型,动态地计算各属性的权重值。宁阳等[22]基于节点度和改进的K-shell迭代次数指标,计算每个属性的贡献权重值。基于多属性融合的方法可以结合各种中心性算法的优点,并对网络中的节点进行综合评估,可以更加准确地识别网络中的具有关键影响力节点。

本文提出了一种新的方法,称之为多属性决策得分算法(Multi-attribute Decision-making Score,简称MADS),用于识别复杂网络中具有关键影响力的节点。本方法综合考虑了融合了不同的中心性度量方法作为网络的多属性,本文从节点的全局影响力和局部影响力两个角度,结合了介数中心性(BC)、紧密度中心性(CC)和桥中心性(Bri)3个不同方面的指标作为识别网络中具有重要影响力节点的3个属性指标。为了提高本方法的适用性,本文提出了一种基于灰度关联分析和信息熵加权理论的新的权重计算方法来综合性地确定每个属性的权重。本文采用了网络的脆弱性评价指标在Dolphins、Football、Email、Netscience、Usair、Yeast6个复杂网络数据集上进行实验数据对比分析,实验分析结果证明了本文提出的MADS算法能够更全面地评估网络中的节点,能够有效地识别出具有关键影响力的节点。

1 相关概念

1.1 中心性度量

假设一个简单的有n个节点的网络G=(V,E) ,其中V表示网络中所有节点的集合,E表示网络中所有边的集合。

定义1.1 介数中心性(Betweenness Centrality)

节点v的BC值就定义为通过节点v的所有节点对之间的最短路径分数,计算公式如下:

(1)

定义1.2 紧密度中心性(Closeness Centrality)

节点v的 CC 值就定义为到节点v的所有其他节点的最短路径距离之和的倒数,计算公式如下:

(2)

其中,dav是节点a和v之间最短路径的距离。

定义1.3 桥中心性(Bridgeness Centrality)

节点v的Bridgeness值就定义公式如下:

(3)

其中,NG(v)表示节点v的邻居节点,ρab表示节点a和b之间最短路径的数目,ρab(v) 表示从节点a和b之间通过节点v的最短路径总条数。

1.2 SIR传播模型

SIR模型[13]是一个广泛应用于流行病网络中的传播、社交网络的谣言传播、城市交通网络堵车问题等诸多真实网络中,用于评价网络节点挖掘算法的指标之一。该模型首先假设网络具有3种状态:S(susceptible易感态,表示当前节点容易被感染后的邻居节点所感染),I(infected感染态,表示当前节点目前处于被感染状态,一定时间后会转变为免疫态),R(recovered免疫态,表示当前节点已对病毒免疫,且不会进行传播)。

本文通过SIR传播模型来计算各节点的传播能力,具体而言,把每个节点都作为传播源(易感态I),每一步都以概率为α感染其邻居节点(感染态S),并可能有概率β在下一步恢复(免疫态R)。在t时刻,计算时刻t初始感染节点的总感染节点数SIR(t)=S(t)+I(t),以SIR(t)来表示时刻t初始感染节点的传播能力,最后SIR(t)会达到一个定值,不再增加,本文用SIR来表示最终的定值。SIR的值越大,即表明该节点的传播能力越强。本文的α设置为0.1,β设置为 0.5 ,本文对每个节点的传播能力计算都重复100次独立实验,对于每个节点的传播能力计算,本文进行了100次独立实验,并取100次实验结果的平均值作为该节点的SIR值。

1.3 灰度关联分析

灰度关联分析主要包括4个部分:确立灰度关系、选取参考序列、计算灰度关联系数、计算灰度关联数。本文以表现每个节点的传播能力的SIR值作为参考序列,即(YSIR)T={y1SIR,y2SIR,…,yNSIR},以每个节点的BC、CC、Bri3个属性的值分别作为比较序列,即(Yj)T={y1j,y2j,…,ynm},(j=1,2,..,m),n为节点的数目,m为总属性的数目。

灰度关联数R的计算方式如下:

(4)

其中:

(5)

α为区分系数,且α∈[0,1],本文α取0.5。

2 MADS算法

2.1 构造规范化决策矩阵

假设某网络有n个节点,决策得分属性为BC、CC、Bri3个属性指标。

构建原始决策属性矩阵A(n×3):

(6)

对矩阵A进行无量纲化处理,进而得到规范化决策矩阵B(n×3):

(7)

2.2 用灰度关联和信息熵理论计算属性权重

第一步,计算每个节点的SIR值SIRi,在原始矩阵A(n×3)上加入一列新列(SIR)T={SIR1,SIR2,…,SIRn},构成矩阵S(n×4):

(8)

第二步,根据式(4)计算出每个节点的每个属性值与SIR值的灰度关联系数:

r(yiSIR,yij),i=1,2,…,n;j=1,2,3

(9)

根据式(5)得到每个属性与SIR值的灰度关联值:

R(YSIR,Yj),j=1,2,3,

(10)

最后得到灰度关联向量R:

R=(R(YSIR,Y1),R(YSIR,Y2),R(YSIR,Y3))。

(11)

第三步,计算3个属性基于灰度分析的权重系数uj:

(12)

灰度关联加权的属性权重向量U为:

U=(u1,u2,u3)

(13)

第四步,基于信息熵理论计算各属性的权重vj,计算公式为:

(14)

信息熵加权的属性权重向量V为:

V=(v1,v2,v3)

(15)

第五步,计算最终的各属性权重wj,计算公式如下:

wj=(Uj+Vj)/2,j=1,2,3

(16)

得到最终权重向量W为:

W=(w1,w2,w3)

(17)

2.3 综合评估节点的影响力

计算每个节点的MADS值:

MADSi=(bci1w1+cci2w2+brii3w3),i=1,2,...,n

(18)

其中,MADSi为每个节点的影响力评估指标,MADS的值越大,表明节点越重要,在网络中的影响力越大。

2.4 算法过程

MADS算法流程由图1所示。

图1 MADS算法流程

3 实验数据分析

3.1 网络的鲁棒性和脆弱性评价指标

网络的鲁棒性和脆弱性指标用于评价在移除某个节点后,网络结构和功能的完整性突变越大表明移除的节点越重要。通常会采用某种重要影响力节点识别排序算法对节点进行排名,从排名高的节点开始逐一删除,用ρ表示已删除节点的数目占总节点数的比例,用σ表示最大连通片的节点数目的比例[23],网络的鲁棒性(robustness)可用R表示[24]。

(19)

其中,ρ和σ分别代表已删除节点数目和最大连通片节点数目在节点总数中所占比例。

基于网络的鲁棒性可定义所实施的删除方法的脆弱性V:

V=1/2-R,R∈(0,1/2)

公安机关、银行等有关部门应及时开展信息预警，适时以真实案例为宣传切入点，揭露“套路贷”犯罪的行为特征，倡导民众通过正规渠道借款，远离不正规的非法放贷组织、个人，自觉抵制非法放贷行为，严防上当受骗。

(20)

在本研究中,采用网络的脆弱性V指标来评估方法的有效性,并计算其V值,V指标越大,表明根据该方法识别的关键节点准确率更高,可以从网络整体上反应具有关键影响力节点挖掘算法的有效性。

3.2 复杂网络数据集

为验证本文所提出的MADS算法的适用性和有效性,本文使用了Dolphins、Football、Email、Netscience、Usair、Yeast6个真实复杂网络数据集。这6个复杂网络数据集的基本拓扑特征如表1所示。

表1 6个复杂网络数据集的基本拓扑特征:网络节点数N和边数M,平均聚类系数C,网络节点的平均度k

(1)Dolphins网络是一个描述海豚之间社交关系的网络数据集。

(2)Football网络是一个描述美国橄榄球比赛的社交网络数据集。

(3)Email网络是从Rovira I Virgili大学的电子邮件记录中提取出来的,记录了一些用户之间的电子邮件通信,以及他们之间的社交关系。

(4)Netscience网络指一个记录了学术界或其他领域合作者之间合作关系的网络数据集,揭示研究者之间的合作关系。

(6)Yeast网络数据集是一个描述酵母细胞蛋白质之间相互作用关系的网络数据集。

为了验证本文提出的MADS(ours)方法的有效性,本文将MADS(ours)与桥中心性(Bridgeness)、介数中心性(Betweenness)、紧密度中心性(Closeness)、特征向量中心性(Eigenvector)及结构洞(Sh)这5种不同方面的中心性度量方法进行脆弱性评价对比分析,即V-指标越大,则表明该方法识别的关键节点越准确。

3.3 实验数据对比分析

实验数据对比分析如图2—7所示。

图2 MADS(ours)方法与桥中心性(Bridgeness)、介数中心性(Betweenness)、紧密度中心性(Closeness)、特征向量中心性(Eigenvector)及结构洞(Sh)在Dolphins网络上的网络脆弱性对比分析

图3 MADS(ours)方法与桥中心性(Bridgeness)、介数中心性(Betweenness)、紧密度中心性(Closeness)、特征向量中心性(Eigenvector)及结构洞(Sh)在Football网络上的网络脆弱性对比分析

图4 MADS(ours)方法与桥中心性(Bridgeness)、介数中心性(Betweenness)、紧密度中心性(Closeness)、特征向量中心性(Eigenvector)及结构洞(Sh)在Usair网络上的网络脆弱性对比分析

图5 MADS(ours)方法与桥中心性(Bridgeness)、介数中心性(Betweenness)、紧密度中心性(Closeness)、特征向量中心性(Eigenvector)及结构洞(Sh)在Email网络上的网络脆弱性对比分析

图6 MADS(ours)方法与桥中心性(Bridgeness)、介数中心性(Betweenness)、紧密度中心性(Closeness)、特征向量中心性(Eigenvector)及结构洞(Sh)在Netscience网络上的网络脆弱性对比分析

从评价排名角度进行分析:由表2可以观察到,MADS(ours)在Usair、Netscience网络的脆弱性评价标准中排列第一名,在Dolphins、Football、Email、Yeast网络中,均排列第二名,综合排名位列第一名,由表3,通过与Bridgeness、Betweenness等其他方法在每个网络上的V指标的对比量化分析,可以观察到MADS(ours)的V指标综合增长了2.6%。从而可以证明:本文提出的MADS方法在识别网络具有重要影响力节点上具有非常显著的有效性和适用性。

表2 每个方法在每个网络中脆弱性评价排名和综合排名Rank

表3 MADS(ours)方法与其他方法在每个网络上的V指标对比分析

同时,由表3可以观察到,MADS(ours)比Bridgeness提高了2.3%,比Closeness提高了4.0%,虽然比Betweenness降低了0.2%,但由于Betweenness的综合排名位列第一,可以说明MADS(ours)非常有效地保留了Betweenness的优势。由此可以证明,本文提出的MADS方法能够非常有效地融合了各属性的优势,展现了本方法具有非常显著的适用性和稳健性。

从网络的角度进行分析:由表2可以观察到,MADS(ours)方法在Dolphins、Football、Usair3个小型网络和Email、Netscience、Yeast3个较大型网络中与其他方法相比,V指标都有显著提高,在Dolphins小网络中提高了5.6%,在Yeast网络中提高了3.6%,由此可以证明,MADS(ours)方法的创新性及优越性,能够很好地识别出网络中具有关键影响力的节点。

综上所述,本文提出的MADS方法在识别复杂网络具有关键影响力节点方面,具有非常高的有效性和适用性,能够更加准确地识别出网络中具有关键影响力的节点,克服了传统单一性中心性度量方法的局限性。

4 结语

本文提出了一种新的复杂网络中识别具有关键影响力节点的方法,采用了多属性决策将不同方面的中心性度量方法进行融合。该方法综合考虑了节点与节点之间的局部影响力以及节点在网络中的全局影响力,同时从节点传播能力及信息熵方面综合权衡了不同属性的权重值。具体而言,本文将节点的介数中心性、紧密度中心性以及桥中心性进行融合,并根据所得到的结果进行网络的脆弱性对比分析。实验结果表明,本文提出的MDAS方法更加有效、更具有适用性,不仅在小型网络,而且在较大型网络中性能都有所提升。下一步,笔者将进一步研究如何识别网络中具有强连接性的边融合到本方法中,以提出新的研究思路并进一步完善该方法。