复杂网络关键节点辨识方法及其电网关键节点辨识方法

摘要

本发明公开了一种复杂网络关键节点辨识方法，包括获取待分析的复杂网络的节点连接关系数据并建模；计算节点的局部特征参数得到局部拓扑重要度指标；计算节点的全局特征参数得到全局拓扑重要度指标；计算节点的综合拓扑重要性度量值并对复杂网络的关键节点进行辨识。本发明还公开了一种包括所述复杂网络关键节点辨识方法的电网关键节点辨识方法。本发明方法利用多属性决策理论，能依据指标的内部信息量以及指标之间的关联性客观确定节点局部特征与全局特征的权重，使融合后的重要度辨识指标更加合理，而且可靠性高、实用性好且准确率较高。

说明书

技术领域

本发明属于通信技术领域，具体涉及一种复杂网络关键节点辨识方法及其电网关键节点辨识方法。

背景技术

在现实生活中，几乎所有的复杂系统都可以通过网络的形式加以描述，如电力网络、互联网络等。随着以互联网为代表的网络信息技术的高速发展，网络化趋势已十分明显，人们的日常生活也越来越多地依赖于各种复杂网络系统的安全可靠运行。实际复杂网络的无标度特性与小世界特性，使得网络中的一些特殊节点对于网络的结构和功能有着巨大的影响，因此这些节点被称为关键节点。当网络中这部分关键节点失效时，其影响将快速波及到整个网络。有效辨识网络中的关键节点，可以为网络规划和风险管理提供数据支持：可以重点保护这些关键节点来提高整个网络的可靠性。因此，如何准确量化网络节点的重要性，挖掘出其中的关键节点，意义重大。

近年来，节点重要性度量的研究引起了国内外学者的广泛关注，复杂网络中关键节点的辨识已经取得了较大进展。目前主要从系统科学和社会网络两个角度分析网络节点的重要程度。其中，系统科学分析方法的核心思想是节点的重要性等价于该节点或者多个节点被删除后对网络的破坏性：例如，节点删除法通过删除网络中某个节点后，利用网络连通性等指标的变化来确定该节点重要程度；该方法存在一个问题，就是如果多个节点的删除都使得网络不连通，那么这些节点的重要度将是一致的，从而使得评估结果不精确。节点收缩法是通过分析网络中相关节点收缩前后网络凝聚度的变化，对节点的重要性进行评估；该方法求网络凝聚度时会计算整个网络的平均最短路径，与节点删除法相同都仅从全局角度考虑，计算网络节点的全局信息，忽略了节点在局部连接的重要性。另一类社会网络分析方法，从节点对网络的贡献度出发，其核心思想是重要性等价于显著性；这类方法利用节点的度数中心性、介数、特征向量等特征属性作为区分节点重要性的评价指标；这些评价指标大都从网络的局部属性和全局属性两个角度出发刻画单个节点在网络中的重要程度：例如，基于度数中心性的重要性评估方法是一种简单有效的局部算法，它只强调节点与邻接节点连边的数量；基于介数的方法需要用到网络全局信息，介数刻画了节点或边对网络中信息或流的控制能力；特征向量充分考虑与目标节点建立连接节点的重要性，并通过邻接节点的重要性来确定目标节点的地位。除此之外，有研究者认为节点的重要性由节点自身及其邻居节点的度数相关，提出基于节点度和邻居度的评估指标，即节点及其邻居的度越大，节点重要性越高；还有研究者考虑节点度以及邻居节点拓扑重合度，认为节点的度越大，而邻居节点拓扑重合度越小越重要，并以此提出了一种基于邻域相似度的节点重要性评估算法。

综上所述，以上评估节点重要度的指标，都是从局部或者全局的单一角度对于网络的结构特点进行刻画，如果目标网络的结构在该方面特征显著，即可得到较好的效果，但是单角度评估网络节点重要性往往都存在着一定的不足和局限性，采用不同的评估指标也会产生不同的节点重要度排序结果。

发明内容

本发明的目的之一在于提供一种可靠性高、实用性好且准确率较高的复杂网络关键节点辨识方法。

本发明的目的之二在于提供一种包括了所述复杂网络关键节点辨识方法的电网关键节点辨识方法。

本发明提供的这种复杂网络关键节点辨识方法，包括如下步骤：

S1.获取待分析的复杂网络的节点连接关系数据，并对网络拓扑进行建模；

S2.根据步骤S1建立的网络拓扑模型，计算节点的局部特征参数，得到局部拓扑重要度指标；

S3.根据步骤S1建立的网络拓扑模型，计算节点的全局特征参数，得到全局拓扑重要度指标；

S4.根据步骤S3得到的局部拓扑重要度指标和步骤S4得到的全局拓扑重要度指标，计算节点的综合拓扑重要性度量值；

S5.根据步骤S4得到的节点的综合拓扑重要性度量值，对复杂网络的关键节点进行辨识。

步骤S1所述的获取待分析的复杂网络的节点连接关系数据，并对网络拓扑进行建模，具体为采用如下步骤进行建模：

A.获取待分析的复杂网络的节点连接关系数据，根据节点和边的数目将网络构建为含有N个节点，M条边的无向无权网络G(V,E)；其中V为网络节点集，E为网络的边集；

B.根据节点间连接关系，构造网络邻接矩阵A＝{a

步骤S2所述的根据步骤S1建立的网络拓扑模型，计算节点的局部特征参数，得到局部拓扑重要度指标，具体为采用如下步骤得到局部拓扑重要度指标：

a.采用如下算式计算节点i的度数中心性指标DC

式中D

b.采用如下算式计算节点i的集聚系数C

式中P

c.对步骤a得到的度数中心性指标DC

式中

步骤S3所述的根据步骤S1建立的网络拓扑模型，计算节点的全局特征参数，得到全局拓扑重要度指标，具体为采用如下步骤计算全局拓扑重要度指标：

(1)采用如下算式计算节点i的介数B

式中σ

(2)对步骤(1)得到的介数B

式中

步骤S4所述的根据步骤S3得到的局部拓扑重要度指标和步骤S4得到的全局拓扑重要度指标，计算节点的综合拓扑重要性度量值，具体为采用如下步骤计算得到节点的综合拓扑重要性度量值：

1)采用如下算式计算第j个指标的信息熵权重we

式中m为指标的总数；en

2)采用如下算式计算第j个指标与其他指标的整体肯德尔相关系数γ

式中m为指标的总数；τ

3)采用如下算式计算第j个指标的肯德尔系数权重wk

4)采用如下算式计算第j个指标的客观权重w

5)采用如下算式计算加权节点指标矩阵S为

6)根据步骤5)得到的加权节点指标矩阵S，采用如下算式计算正理想解F

7)采用如下算式计算第i个节点到正理想解F

8)采用如下算式计算第i个节点的综合拓扑重要性度量值T

步骤2)所述的肯德尔相关系数，具体为采用如下步骤计算肯德尔相关系数：

对于都具有N个元素的两种节点重要度指标，设定X＝(x

式中N

步骤S5所述的根据步骤S4得到的节点的综合拓扑重要性度量值，对复杂网络的关键节点进行辨识，具体为根据步骤S4得到的节点的综合拓扑重要性度量值，节点的综合拓扑重要性度量值越大，则认定该节点对复杂网络越关键。

本发明还提供了一种包括了所述复杂网络关键节点辨识方法的电网关键节点辨识方法，具体包括如下步骤：

Ⅰ.确定待分析的电网；

Ⅱ.将步骤Ⅰ确定的待分析的电网作为待分析的复杂网络，采用上述步骤S1～步骤5，对待分析的电网的关键节点进行辨识。

本发明提供的这种复杂网络关键节点辨识方法及其电网关键节点辨识方法，从复杂网络共有的拓扑结构特性出发，消除了不同网络中特定业务对节点的影响，提出了一种通用的复杂网络关键节点辨识方法；本发明综合考虑节点的局部特征与全局特征，提出一种反映节点局部与全局重要度的综合方法，能够更加合理有效辨识复杂网络中关键节点；本发明方法利用多属性决策理论，能依据指标的内部信息量以及指标之间的关联性客观确定节点局部特征与全局特征的权重，使融合后的重要度辨识指标更加合理，而且可靠性高、实用性好且准确率较高。

附图说明

图1为本发明的复杂网络关键节点辨识方法的方法流程示意图。

图2为本发明的电网关键节点辨识方法的方法流程示意图。

图3为本发明的实施例的网络拓扑结构示意图。

具体实施方式

如图1所示为本发明的复杂网络关键节点辨识方法的方法流程示意图：本发明提供的这种复杂网络关键节点辨识方法，包括如下步骤：

S1.获取待分析的复杂网络的节点连接关系数据，并对网络拓扑进行建模；具体为采用如下步骤进行建模：

A.获取待分析的复杂网络的节点连接关系数据，根据节点和边的数目将网络构建为含有N个节点，M条边的无向无权网络G(V,E)；其中V为网络节点集，E为网络的边集；

B.根据节点间连接关系，构造网络邻接矩阵A＝{a

S2.根据步骤S1建立的网络拓扑模型，计算节点的局部特征参数，得到局部拓扑重要度指标；具体为采用如下步骤得到局部拓扑重要度指标：

a.采用如下算式计算节点i的度数中心性指标DC

式中D

b.采用如下算式计算节点i的集聚系数C

式中P

c.对步骤a得到的度数中心性指标DC

式中

S3.根据步骤S1建立的网络拓扑模型，计算节点的全局特征参数，得到全局拓扑重要度指标；具体为采用如下步骤计算全局拓扑重要度指标：

(1)采用如下算式计算节点i的介数B

式中σ

(2)对步骤(1)得到的介数B

式中

S4.根据步骤S3得到的局部拓扑重要度指标和步骤S4得到的全局拓扑重要度指标，计算节点的综合拓扑重要性度量值；具体为采用如下步骤计算得到节点的综合拓扑重要性度量值：

1)利用多属性决策理论综合考虑节点的局部特征与全局特征，通过熵权法计算各指标的信息熵权重；采用如下算式计算第j个指标的信息熵权重we

式中m为指标的总数；en

2)肯德尔系数通常用于衡量指标与指标之间的关联性；采用如下算式计算第j个指标与其他指标的整体肯德尔相关系数γ

式中m为指标的总数；τ

对于都具有N个元素的两种节点重要度指标，设定X＝(x

式中N

3)采用如下算式计算第j个指标的肯德尔系数权重wk

4)信息熵权重和肯德尔系数权重能够客观量化出指标内部信息量以及指标之间的关联性，因此采用如下算式计算第j个指标的客观权重w

5)采用如下算式计算加权节点指标矩阵S为

6)根据步骤5)得到的加权节点指标矩阵S，采用如下算式计算正理想解F

7)采用如下算式计算第i个节点到正理想解F

8)采用如下算式计算第i个节点的综合拓扑重要性度量值T

S5.根据步骤S4得到的节点的综合拓扑重要性度量值，对复杂网络的关键节点进行辨识；具体为根据步骤S4得到的节点的综合拓扑重要性度量值，节点的综合拓扑重要性度量值越大，则认定该节点对复杂网络越关键。

如图2所示为本发明的电网关键节点辨识方法的方法流程示意图：本发明提供的这种包括了所述复杂网络关键节点辨识方法的电网关键节点辨识方法，具体包括如下步骤：

Ⅰ.确定待分析的电网；

Ⅱ.将步骤Ⅰ确定的待分析的电网作为待分析的复杂网络，获取待分析的复杂网络的节点连接关系数据，并对网络拓扑进行建模；具体为采用如下步骤进行建模：

A.获取待分析的复杂网络的节点连接关系数据，根据节点和边的数目将网络构建为含有N个节点，M条边的无向无权网络G(V,E)；其中V为网络节点集，E为网络的边集；

B.根据节点间连接关系，构造网络邻接矩阵A＝{a

Ⅲ.根据步骤Ⅱ建立的网络拓扑模型，计算节点的局部特征参数，得到局部拓扑重要度指标；具体为采用如下步骤得到局部拓扑重要度指标：

a.采用如下算式计算节点i的度数中心性指标DC

式中D

b.采用如下算式计算节点i的集聚系数C

式中P

c.对步骤a得到的度数中心性指标DC

式中

Ⅳ.根据步骤Ⅱ建立的网络拓扑模型，计算节点的全局特征参数，得到全局拓扑重要度指标；具体为采用如下步骤计算全局拓扑重要度指标：

(1)采用如下算式计算节点i的介数B

式中σ

(2)对步骤(1)得到的介数B

式中

Ⅴ.根据步骤Ⅲ得到的局部拓扑重要度指标和步骤Ⅳ得到的全局拓扑重要度指标，计算节点的综合拓扑重要性度量值；具体为采用如下步骤计算得到节点的综合拓扑重要性度量值：

1)利用多属性决策理论综合考虑节点的局部特征与全局特征，通过熵权法计算各指标的信息熵权重；采用如下算式计算第j个指标的信息熵权重we

式中m为指标的总数；en

2)肯德尔系数通常用于衡量指标与指标之间的关联性；采用如下算式计算第j个指标与其他指标的整体肯德尔相关系数γ

式中m为指标的总数；τ

对于都具有N个元素的两种节点重要度指标，设定X＝(x

式中N

3)采用如下算式计算第j个指标的肯德尔系数权重wk

4)信息熵权重和肯德尔系数权重能够客观量化出指标内部信息量以及指标之间的关联性，因此采用如下算式计算第j个指标的客观权重w

5)采用如下算式计算加权节点指标矩阵S为

6)根据步骤5)得到的加权节点指标矩阵S，采用如下算式计算正理想解F

7)采用如下算式计算第i个节点到正理想解F

8)采用如下算式计算第i个节点的综合拓扑重要性度量值T

Ⅵ.根据步骤Ⅴ得到的节点的综合拓扑重要性度量值，对复杂网络的关键节点进行辨识；具体为根据步骤Ⅴ得到的节点的综合拓扑重要性度量值，节点的综合拓扑重要性度量值越大，则认定该节点对复杂网络越关键。

以下结合一个具体实施例，对本发明方法进行进一步说明：

图3为本发明的实施例的网络结构拓扑示意图。图中各节点的属性值如表1所示；度数中心性、聚类系数、介数三种指标的属性值如表2所示

表1 10个节点的属性值示意表

表2三种指标的属性值示意表

由表1计算结果可知，8号节点的三种指标都排首位，因此综合拓扑重要度最高；4号节点三种指标次于8号节点，而聚类系数与介数指标高于3号节点，故排在第二位，3号节点排在第三位；2号与6号节点位置相同，三种指标都弱于3号节点，排在第四位；5、7、9、10号节点位置完全相同，与排名靠前的节点相比，只有聚类系数指标较高，度数中心性与介数中心性指标均为0，因此重要度相较低；1号节点由于聚类系数与介数中心性指标为0，度数中心性指标也较低，因此重要度低。