一种面向有权重网络的关键节点识别方法及装置

摘要

本发明提供一种面向有权重网络的关键节点识别方法及装置，其中方法包括获取第一目标网络的拓扑结构的边权重；计算第一目标网络中每个节点的权重集体影响值；删除第一目标网络中目标数量个权重集体影响值最大的节点，得到包括有多个最大组件的第二目标网络；删除最大组件中权重集体影响值最大的节点，直至最大组件的总边权重小于目标边权重，得到第三目标网络；计算第三目标网络中每个节点的权重集体影响值；对第三目标网络中每个节点进行排序；将第一目标网络中所有已删除的节点插入至第三目标网络中，得到所有已删除的节点的插入顺序；对第一目标网络中所有节点进行排序，以对第一目标网络中关键节点进行识别。

说明书

技术领域

本发明属于通信技术领域，尤其涉及一种面向有权重网络的关键节点识别方法及装置。

背景技术

随着以互联网为代表的网络信息技术的高速发展，网络化趋势已十分明显，人们的日常生活也越来越多地依赖于各种复杂网络系统的安全可靠运行。网络中通过边连接两个节点，有权重网络是指网络中边与边的权重不一致。如图1和图2所示，有权重网络有大小之分，而无权重网络是有权重网络的一个特例，即每条边的权重均为1。实际复杂网络的无标度特性与小世界特性，使得网络中的一些特殊节点对于网络的结构和功能有着巨大的影响，因此这些节点被称为关键节点。当网络中这部分关键节点失效时，其影响将快速波及到整个网络。有效辨识网络中的关键节点，可以为网络规划和风险管理提供数据支持：可以重点保护这些关键节点来提高整个网络的可靠性。

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

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

发明内容

本发明针对现有技术中的不足，提供一种面向有权重网络的关键节点识别方法及装置。

为实现上述目的，本发明采用以下技术方案：

第一方面，本发明提供一种面向有权重网络的关键节点识别方法，包括：

获取第一目标网络的拓扑结构的边权重；

根据所述第一目标网络的拓扑结构的边权重，计算所述第一目标网络中每个节点的权重集体影响值；

删除所述第一目标网络中目标数量个权重集体影响值最大的节点，得到包括有多个最大组件的第二目标网络；其中，最大组件包括删除所述第一目标网络中目标数量个权重集体影响值最大的节点后，仍保留的边和边连接的节点；

删除最大组件中权重集体影响值最大的节点，直至最大组件的总边权重小于目标边权重，得到第三目标网络；

计算所述第三目标网络中每个节点的权重集体影响值；

根据所述第三目标网络中每个节点的权重集体影响值，对所述第三目标网络中每个节点进行排序；

将所述第一目标网络中所有已删除的节点插入至所述第三目标网络中，得到所有已删除的节点的插入顺序；

根据所述一目标网络中所有已删除的节点的插入顺序和所述第三目标网络中每个节点的排序，对所述第一目标网络中所有节点进行排序，以对所述第一目标网络中关键节点进行识别。

进一步地，所述根据所述第一目标网络的拓扑结构的边权重，计算所述第一目标网络中每个节点的权重集体影响值，包括：

根据以下公式，计算所述第一目标网络中每个节点的权重集体影响值：

其中，WCI

进一步地，所述最大组件的总边权重和所述第一目标网络的总边权重满足：

其中，G

进一步地，所述将所述第一目标网络中所有已删除的节点插入至所述第三目标网络中，得到所有已删除的节点的插入顺序，包括：

计算每次所述第一目标网络中已删除的相同权重集体影响值节点插入所述第三目标网络前，所述第三目标网络中最大组件的总边权重；

计算每次所述第一目标网络中已删除的相同权重集体影响值节点插入所述第三目标网络后，所述第三目标网络中最大组件的总边权重；

计算每次所述第一目标网络中已删除的相同权重集体影响值节点插入所述第三目标网络前后，所述第三目标网络中最大组件的总边权重增加值；

将所述第一目标网络中已删除的相同权重集体影响值节点按照所述第三目标网络中最大组件的总边权重增加值最小，插入至所述第三目标网络中，得到所有已删除的节点的插入顺序。

第二方面，本发明提供一种面向有权重网络的关键节点识别装置，包括：

获取模块，用于获取第一目标网络的拓扑结构的边权重；

第一计算模块，用于根据所述第一目标网络的拓扑结构的边权重，计算所述第一目标网络中每个节点的权重集体影响值；

第一删除模块，用于删除所述第一目标网络中目标数量个权重集体影响值最大的节点，得到包括有多个最大组件的第二目标网络；其中，最大组件包括删除所述第一目标网络中目标数量个权重集体影响值最大的节点后，仍保留的边和边连接的节点；

第二删除模块，用于删除最大组件中权重集体影响值最大的节点，直至最大组件的总边权重小于目标边权重，得到第三目标网络；

第二计算模块，用于计算所述第三目标网络中每个节点的权重集体影响值；

第一排序模块，用于根据所述第三目标网络中每个节点的权重集体影响值，对所述第三目标网络中每个节点进行排序；

插入模块，用于将所述第一目标网络中所有已删除的节点插入至所述第三目标网络中，得到所有已删除的节点的插入顺序；

第二排序模块，用于根据所述一目标网络中所有已删除的节点的插入顺序和所述第三目标网络中每个节点的排序，对所述第一目标网络中所有节点进行排序，以对所述第一目标网络中关键节点进行识别。

进一步地，所述第一计算模块包括：

第一计算单元，用于根据以下公式，计算所述第一目标网络中每个节点的权重集体影响值：

其中，WCI

进一步地，所述插入模块包括：

第二计算单元，用于计算每次所述第一目标网络中已删除的相同权重集体影响值节点插入所述第三目标网络前，所述第三目标网络中最大组件的总边权重；

第三计算单元，用于计算每次所述第一目标网络中已删除的相同权重集体影响值节点插入所述第三目标网络后，所述第三目标网络中最大组件的总边权重；

第四计算单元，用于计算每次所述第一目标网络中已删除的相同权重集体影响值节点插入所述第三目标网络前后，所述第三目标网络中最大组件的总边权重增加值；

插入单元，用于将所述第一目标网络中已删除的相同权重集体影响值节点按照所述第三目标网络中最大组件的总边权重增加值最小，插入至所述第三目标网络中，得到所有已删除的节点的插入顺序。

本发明一种面向有权重网络的关键节点识别方法及装置，其中方法获取第一目标网络的拓扑结构的边权重；根据所述第一目标网络的拓扑结构的边权重，计算所述第一目标网络中每个节点的权重集体影响值；删除所述第一目标网络中目标数量个权重集体影响值最大的节点，得到包括有多个最大组件的第二目标网络；其中，最大组件包括删除所述第一目标网络中目标数量个权重集体影响值最大的节点后，仍保留的边和边连接的节点；删除最大组件中权重集体影响值最大的节点，直至最大组件的总边权重小于目标边权重，得到第三目标网络；计算所述第三目标网络中每个节点的权重集体影响值；根据所述第三目标网络中每个节点的权重集体影响值，对所述第三目标网络中每个节点进行排序；将所述第一目标网络中所有已删除的节点插入至所述第三目标网络中，得到所有已删除的节点的插入顺序；根据所述一目标网络中所有已删除的节点的插入顺序和所述第三目标网络中每个节点的排序，对所述第一目标网络中所有节点进行排序，以对所述第一目标网络中关键节点进行识别。采用上述方案，解决了现有评估节点重要性的方法只应用于无权重网络而无法应用于有权重网络，且是从局部或者全局的单一角度对于网络的结构特点进行刻画，单一角度评估网络节点重要性往往都存在着一定的不足和局限性，采用不同的评估指标也会产生不同的节点重要度排序结果的问题。

附图说明

为了更清楚地说明本申请的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，显而易见地，对于本领域普通技术人员而言，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为有权重网络的结构示意图；

图2为无权重网络的结构示意图；

图3为本发明实施例提供的一种面向有权重网络的关键节点识别方法的流程示意图；

图4为本发明实施例提供的一种面向有权重网络的关键节点识别装置的结构示意图。

具体实施方式

现在结合附图对本发明作进一步详细的说明。

需要注意的是，发明中所引用的如“上”、“下”、“左”、“右”、“前”、“后”等的用语，亦仅为便于叙述的明了，而非用以限定本发明可实施的范围，其相对关系的改变或调整，在无实质变更技术内容下，当亦视为本发明可实施的范畴。

如背景技术中所述，目前主要从系统科学和社会网络两个角度分析网络节点的重要程度。其中，系统科学分析方法的核心思想是节点的重要性等价于该节点或者多个节点被删除后对网络的破坏性：例如，节点删除法通过删除网络中某个节点后，利用网络连通性等指标的变化来确定该节点重要程度；该方法存在一个问题，就是如果多个节点的删除都使得网络不连通，那么这些节点的重要度将是一致的，从而使得评估结果不精确。节点收缩法是通过分析网络中相关节点收缩前后网络凝聚度的变化，对节点的重要性进行评估；该方法求网络凝聚度时会计算整个网络的平均最短路径，与节点删除法相同都仅从全局角度考虑，计算网络节点的全局信息，忽略了节点在局部连接的重要性。另一类社会网络分析方法，从节点对网络的贡献度出发，其核心思想是重要性等价于显著性；这类方法利用节点的度数中心性、介数、特征向量等特征属性作为区分节点重要性的评价指标；这些评价指标大都从网络的局部属性和全局属性两个角度出发刻画单个节点在网络中的重要程度：例如，基于度数中心性的重要性评估方法是一种简单有效的局部算法，它只强调节点与邻接节点连边的数量；基于介数的方法需要用到网络全局信息，介数刻画了节点或边对网络中信息或流的控制能力；特征向量充分考虑与目标节点建立连接节点的重要性，并通过邻接节点的重要性来确定目标节点的地位。然而，以上评估节点重要性的方法只应用于无权重网络而无法应用于有权重网络，且是从局部或者全局的单一角度对于网络的结构特点进行刻画。如果目标网络的结构在该方面特征显著，即可得到较好的效果，但是单一角度评估网络节点重要性往往都存在着一定的不足和局限性，采用不同的评估指标也会产生不同的节点重要度排序结果。

因此，为了解决上述问题，本发明实施例部分提供了一种面向有权重网络的关键节点识别方法，具体的，参见图3，所述关键节点识别方法包括以下步骤：

步骤S101，获取第一目标网络的拓扑结构的边权重。

步骤S102，根据所述第一目标网络的拓扑结构的边权重，计算所述第一目标网络中每个节点的权重集体影响值。

其中，节点的权重集体影响值表示在考虑边权重的前提下，该节点发出的信息在网络中的传播能力。

本步骤中，根据以下公式，计算所述第一目标网络中每个节点的权重集体影响值：

其中，WCI

所述第一目标网络中以节点i为中心，以l为半径的球面上所有节点的确定：选中节点i，初始化球形第一目标网络的半径Ball＝0，并对节点i作已访问标记；访问节点i的所有邻居节点，将节点i的所有邻居节点作已访问标记，并将节点i和节点i的所有邻居节点加入队列Q，同时Ball＝Ball+1；寻找队列Q中每个节点的所有邻居节点，将所有节点的邻居节点作已访问标记，并将所有节点的邻居节点重新加入队列Q，同时Ball＝Ball+1，直至Ball＝l，此时在队列Q中的所有节点均为以节点i为中心，半径为l的球面上的节点。

步骤S103，删除所述第一目标网络中目标数量个权重集体影响值最大的节点，得到包括有多个最大组件的第二目标网络；其中，最大组件包括删除所述第一目标网络中目标数量个权重集体影响值最大的节点后，仍保留的边和边连接的节点。

本步骤中，目标数量指示权重集体影响值最大的全部节点的数量。所述最大组件的总边权重和所述第一目标网络的总边权重满足：

其中，G

步骤S104，删除最大组件中权重集体影响值最大的节点，直至最大组件的总边权重小于目标边权重，得到第三目标网络。

步骤S105，计算所述第三目标网络中每个节点的权重集体影响值。

步骤S106，根据所述第三目标网络中每个节点的权重集体影响值，对所述第三目标网络中每个节点进行排序。

步骤S107，将所述第一目标网络中所有已删除的节点插入至所述第三目标网络中，得到所有已删除的节点的插入顺序。

本步骤中，首先计算每次所述第一目标网络中已删除的相同权重集体影响值节点插入所述第三目标网络前，所述第三目标网络中最大组件的总边权重；然后计算每次所述第一目标网络中已删除的相同权重集体影响值节点插入所述第三目标网络后，所述第三目标网络中最大组件的总边权重；最后计算每次所述第一目标网络中已删除的相同权重集体影响值节点插入所述第三目标网络前后，所述第三目标网络中最大组件的总边权重增加值；将所述第一目标网络中已删除的相同权重集体影响值节点按照所述第三目标网络中最大组件的总边权重增加值最小，插入至所述第三目标网络中，得到所有已删除的节点的插入顺序。例如，第一次将所述第一目标网络中已删除的相同权重集体影响值节点插入所述第三目标网络前，所述第三目标网络中最大组件的总边权重为G

步骤S108，根据所述一目标网络中所有已删除的节点的插入顺序和所述第三目标网络中每个节点的排序，对所述第一目标网络中所有节点进行排序，以对所述第一目标网络中关键节点进行识别。

步骤S106-S108中，所述第一目标网络中已删除的节点对应的权重集体影响值均大于所述第三目标网络中每个节点对应的权重集体影响值。

如图4所示，本发明实施例还提供一种面向有权重网络的关键节点识别装置，包括：

获取模块100，用于获取第一目标网络的拓扑结构的边权重。

第一计算模块200，用于根据所述第一目标网络的拓扑结构的边权重，计算所述第一目标网络中每个节点的权重集体影响值。

第一删除模块300，用于删除所述第一目标网络中目标数量个权重集体影响值最大的节点，得到包括有多个最大组件的第二目标网络；其中，最大组件包括删除所述第一目标网络中目标数量个权重集体影响值最大的节点后，仍保留的边和边连接的节点。

第二删除模块400，用于删除最大组件中权重集体影响值最大的节点，直至最大组件的总边权重小于目标边权重，得到第三目标网络。

第二计算模块500，用于计算所述第三目标网络中每个节点的权重集体影响值。

第一排序模块600，用于根据所述第三目标网络中每个节点的权重集体影响值，对所述第三目标网络中每个节点进行排序。

插入模块700，用于将所述第一目标网络中所有已删除的节点插入至所述第三目标网络中，得到所有已删除的节点的插入顺序。

第二排序模块800，用于根据所述一目标网络中所有已删除的节点的插入顺序和所述第三目标网络中每个节点的排序，对所述第一目标网络中所有节点进行排序，以对所述第一目标网络中关键节点进行识别。

可选的，所述第一计算模块包括：

第一计算单元，用于根据以下公式，计算所述第一目标网络中每个节点的权重集体影响值：

其中，WCI

可选的，所述插入模块包括：

第二计算单元，用于计算每次所述第一目标网络中已删除的相同权重集体影响值节点插入所述第三目标网络前，所述第三目标网络中最大组件的总边权重；

第三计算单元，用于计算每次所述第一目标网络中已删除的相同权重集体影响值节点插入所述第三目标网络后，所述第三目标网络中最大组件的总边权重；

第四计算单元，用于计算每次所述第一目标网络中已删除的相同权重集体影响值节点插入所述第三目标网络前后，所述第三目标网络中最大组件的总边权重增加值；

插入单元，用于将所述第一目标网络中已删除的相同权重集体影响值节点按照所述第三目标网络中最大组件的总边权重增加值最小，插入至所述第三目标网络中，得到所有已删除的节点的插入顺序。

本领域的技术人员可以清楚地了解到本发明实施例中的技术可借助软件加必需的通用硬件平台的方式来实现。基于这样的理解，本发明实施例中的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在存储介质中，如ROM/RAM、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例或者实施例的某些部分所述的方法。

本说明书中各个实施例之间相同相似的部分互相参见即可。尤其，对于装置实施例而言，由于其基本相似于方法实施例，所以描述的比较简单，相关之处参见方法实施例中的说明即可。

以上仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理前提下的若干改进和润饰，应视为本发明的保护范围。