一种图节点的中心度计算方法及系统

摘要

本发明公开了一种图节点的中心度计算方法及系统，方法包括：对目标图形的节点信息和边信息进行筛选，得到筛选后的目标图形的节点信息和边信息；基于筛选后的目标图形的节点信息和边信息构成多个子图；选择K种图中心度算法；分别确定K种图中心度算法的权重；基于K种中心度算法，分别计算得到每个子图的中心度得分集合；基于每个子图的中心度得分集合以及K种图中心度算法的权重，计算得到每个子图的中心度总分；分别确定每个子图的中心度总分的权重；基于每个子图的中心度总分以及每个子图的中心度总分的权重，计算得到目标图形节点的中心度得分。本发明相对于现有技术能够有效提高图节点的中心度计算的准确性。

说明书

技术领域

本发明涉及数据处理技术领域，尤其涉及一种图节点的中心度计算方法及系统。

背景技术

目前，在确定图中心节点时，已有如度中心性、紧密中心性、中介中心性、网页中心度等多种图中心性算法。其中，度中心性作为连通性的基线度量，对于一个拥有g个节点的无向图，节点i的度中心性是i与其它g-1个节点的直接联系总数。紧密中心性用于测量节点对群体的意义，包括对断开连接群体的两个变体；其核心思想是如果节点到图中其他节点的最短距离都很小，那么它的接近中心性就很高。中介中心性用于查找控制点，包括一个近似的估计算法；其核心思想是计算网络中任意两个节点的所有最短路径，如果这些最短路径中很多条都经过了某个节点，那么就认为这个节点的中介中心性高。网页中心度用来了解整体性的影响，包括一个个性化的网页排名变体；网页中心度核心思想是，其认为指标最好还需要考虑到指向你的那些节点。也就是说，来自受欢迎的节点的跳转应该重于不太受欢迎的节点的跳转。

上述算法都存在自己的局限性，如网页中心度算法无法区别不同属性的连接、且存在偏好老节点的偏好。

因此，如何更加有效准确的确定图节点的中心度，是一项亟待解决的问题。

发明内容

有鉴于此，本发明提供了一种图节点的中心度计算方法，能够综合不同的中心度量化算法，属性和边的信息，结合用户在不同场景的需求，综合计算节点的中心度，相对于现有技术能够更加准确的确定出图节点的中心度。

本发明提供了一种图节点的中心度计算方法，包括：

对目标图形的节点信息和边信息进行筛选，得到筛选后的目标图形的节点信息和边信息；

基于所述筛选后的目标图形的节点信息和边信息构成多个子图；

选择K种图中心度算法，其中，K≥2；

分别确定所述K种图中心度算法的权重；

基于所述K种中心度算法，分别计算得到每个子图的中心度得分集合；

基于所述每个子图的中心度得分集合以及所述K种图中心度算法的权重，计算得到每个子图的中心度总分；

分别确定每个子图的中心度总分的权重；

基于所述每个子图的中心度总分以及所述每个子图的中心度总分的权重，计算得到所述目标图形节点的中心度得分。

优选地，所述分别确定所述K种图中心度算法的权重，包括：

采用优序图法分别确定所述K种图中心度算法的权重。

优选地，所述采用优序图法分别确定所述K种图中心度算法的权重，包括：

设置棋盘图，将所述K种图中心度算法分别置于所述棋盘图的第一列和第一行；

将每一行的图中心度算法分别与每一列的图中心度算法进行对比，分别得到两两对比的评分；

对每一行的图中心度算法的评分进行横向求和，得到每一行的图中心度算法的最终得分；

基于每一行的图中心度算法的最终得分确定对应的图中心度算法的权重。

优选地，所述分别确定每个子图的中心度总分的权重，包括：

采用优序图法分别确定每个子图的中心度总分的权重。

一种图节点的中心度计算系统，包括：

筛选模块，用于对目标图形的节点信息和边信息进行筛选，得到筛选后的目标图形的节点信息和边信息；

构成模块，用于基于所述筛选后的目标图形的节点信息和边信息构成多个子图；

选择模块，用于选择K种图中心度算法，其中，K≥2；

第一确定模块，用于分别确定所述K种图中心度算法的权重；

第一计算模块，用于基于所述K种中心度算法，分别计算得到每个子图的中心度得分集合；

第二计算模块，用于基于所述每个子图的中心度得分集合以及所述K种图中心度算法的权重，计算得到每个子图的中心度总分；

第二确定模块，用于分别确定每个子图的中心度总分的权重；

第三计算模块，用于基于所述每个子图的中心度总分以及所述每个子图的中心度总分的权重，计算得到所述目标图形节点的中心度得分。

优选地，所述第一确定模块在执行分别确定所述K种图中心度算法的权重时，具体用于：

采用优序图法分别确定所述K种图中心度算法的权重。

优选地，所述第一确定模块在执行采用优序图法分别确定所述K种图中心度算法的权重时，包括：

设置单元，用于设置棋盘图，将所述K种图中心度算法分别置于所述棋盘图的第一列和第一行；

对比单元，用于将每一行的图中心度算法分别与每一列的图中心度算法进行对比，分别得到两两对比的评分；

求和单元，用于对每一行的图中心度算法的评分进行横向求和，得到每一行的图中心度算法的最终得分；

确定单元，用于基于每一行的图中心度算法的最终得分确定对应的图中心度算法的权重。

优选地，所述第二确定模块在执行分别确定每个子图的中心度总分的权重时，具体用于：

采用优序图法分别确定每个子图的中心度总分的权重。

一种设备，包括：至少一个处理器、以及与所述处理器连接的至少一个存储器、总线；其中，所述处理器、所述存储器通过所述总线完成相互间的通信；所述处理器用于调用所述存储器中的程序指令，以执行如上所述的图节点的中心度计算方法。

一种存储介质，所述存储介质中存储有计算机可执行指令，所述计算机可执行指令被处理器加载并执行时，实现如上所述的图节点的中心度计算方法。

综上所述，本发明公开了一种图节点的中心度计算方法，当需要计算图节点的中心度时，首先对目标图形的节点信息和边信息进行筛选，得到筛选后的目标图形的节点信息和边信息；基于筛选后的目标图形的节点信息和边信息构成多个子图；然后选择K种图中心度算法，其中，K≥2；分别确定K种图中心度算法的权重；基于K种中心度算法，分别计算得到每个子图的中心度得分集合；基于每个子图的中心度得分集合以及K种图中心度算法的权重，计算得到每个子图的中心度总分；分别确定每个子图的中心度总分的权重；基于每个子图的中心度总分以及所述每个子图的中心度总分的权重，计算得到目标图形节点的中心度得分。本发明能够综合不同的中心度量化算法，属性和边的信息，结合用户在不同场景的需求，综合计算节点的中心度，相对于现有技术能够更加准确的确定出图节点的中心度。

附图说明

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

图1为本发明公开的一种图节点的中心度计算方法实施例1的方法流程图；

图2为本发明公开的一种图节点的中心度计算方法实施例2的方法流程图；

图3为本发明公开的一种采用优序图法分别确定K种图中心度算法的权重的方法流程图；

图4为本发明公开的一种图中心度算法对比棋盘图；

图5为本发明公开的一种图中心度算法对比评分结果图；

图6为本发明公开的一种图中心度算法得分示意图；

图7为本发明公开的一种图节点的中心度计算系统实施例1的结构示意图；

图8为本发明公开的一种图节点的中心度计算系统实施例2的结构示意图

图9为本发明公开的第一确定模块的结构示意图；

图10为本发明公开的一种设备的结构示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

如图1所示，为本发明公开的一种图节点的中心度计算方法实施例1的方法流程图，所述方法可以包括以下步骤：

S101、对目标图形的节点信息和边信息进行筛选，得到筛选后的目标图形的节点信息和边信息；

当需要计算图节点的中心度时，首先获取目标图形(即需要进行中心度计算的图形)的所有节点信息和边信息，并从获取到的所有节点信息和边信息中筛选出符合条件的不同的节点信息和边信息。

如表1示所示，为目标图形的节点信息，如表2和表3所示，为目标图形的边信息。

表1目标图形的节点信息

表2目标图形的边信息

表3目标图形的边信息

S102、基于筛选后的目标图形的节点信息和边信息构成多个子图；

在得到筛选后的目标图形的节点信息和边信息后，通过筛选后得到的目标图形的节点信息和边信息构成多个子图。即，多个子图构成多个子图集合。sub_graphs＝{sub_graph[1],sub_graph[2]…}

S103、选择K种图中心度算法，其中，K≥2；

对于多个子图集合中的每个子图sub_graph[i]，选择K种图中心度算法，其中，K≥2。

S104、分别确定K种图中心度算法的权重；

并分别确定出K种图中心度算法的权重。

S105、基于K种中心度算法，分别计算得到每个子图的中心度得分集合；

对于每个子图sub_graph[i]，根据选择的K种图中心度算法，计算得到对应的中心度得分集合sub_scores[i]＝{algo_score[1],algo_score[2]…algo_score[K]}。

S106、基于每个子图的中心度得分集合以及K种图中心度算法的权重，计算得到每个子图的中心度总分；

对于第i个子图的中心度得分集合sub_scores[i]，按照K种图中心度算法的权重加权，得到第i个子图的中心度总分sub_total_score[i]。

S107、分别确定每个子图的中心度总分的权重；

并分别确定每个子图的中心度总分的权重。

S108、基于每个子图的中心度总分以及每个子图的中心度总分的权重，计算得到目标图形节点的中心度得分。

对于所有子图中心度总分，按照每个子图的中心度总分的权重进行加权得到目标图像节点的总体的中心度得分total_score。

综上所述，在上述实施例中，当需要计算图节点的中心度时，首先对目标图形的节点信息和边信息进行筛选，得到筛选后的目标图形的节点信息和边信息；基于筛选后的目标图形的节点信息和边信息构成多个子图；然后选择K种图中心度算法，其中，K≥2；分别确定K种图中心度算法的权重；基于K种中心度算法，分别计算得到每个子图的中心度得分集合；基于每个子图的中心度得分集合以及K种图中心度算法的权重，计算得到每个子图的中心度总分；分别确定每个子图的中心度总分的权重；基于每个子图的中心度总分以及所述每个子图的中心度总分的权重，计算得到目标图形节点的中心度得分。能够综合不同的中心度量化算法，属性和边的信息，结合用户在不同场景的需求，综合计算节点的中心度，相对于现有技术能够更加准确的确定出图节点的中心度。

如图2所示，为本发明公开的一种图节点的中心度计算方法实施例2的方法流程图，所述方法可以包括以下步骤：

S201、对目标图形的节点信息和边信息进行筛选，得到筛选后的目标图形的节点信息和边信息；

当需要计算图节点的中心度时，首先获取目标图形(即需要进行中心度计算的图形)的所有节点信息和边信息，并从获取到的所有节点信息和边信息中筛选出符合条件的不同的节点信息和边信息。

如表1示所示，为目标图形的节点信息，如表2和表3所示，为目标图形的边信息。

S202、基于筛选后的目标图形的节点信息和边信息构成多个子图；

在得到筛选后的目标图形的节点信息和边信息后，通过筛选后得到的目标图形的节点信息和边信息构成多个子图。即，多个子图构成多个子图集合。sub_graphs＝{sub_graph[1],sub_graph[2]…}

S203、选择K种图中心度算法，其中，K≥2；

对于多个子图集合中的每个子图sub_graph[i]，选择K种图中心度算法，其中，K≥2。

S204、采用优序图法分别确定K种图中心度算法的权重；

然后，对于选择的K种图中心度算法，通过采用优序图法确定出K种图中心度算法的权重。优序图法是通过对多个指标或目标进行两两相对比较，最后给出重要性次序或优先次序。

具体的，在采用优序图法分别确定K种图中心度算法的权重的其中一种实现方式可以包括以下步骤：

S301、设置棋盘图，将K种图中心度算法分别置于棋盘图的第一列和第一行；

首先绘制棋盘图，将需要对比的K种图中心度算法分别放入棋盘图的第一列和第一行，如图4所示。

S302、将每一行的图中心度算法分别与每一列的图中心度算法进行对比，分别得到两两对比的评分；

然后将每一行的图中心度算法分别与每一列的图中心度算法进行对比，得到两两对比的评分。例如，若指标X

S303、对每一行的图中心度算法的评分进行横向求和，得到每一行的图中心度算法的最终得分；

然后，将每项图中心度算法的评分进行横向求和，得到每一行的图中心度算法的最终得分。如图6所示，为各图中心度算法得分。

S304、基于每一行的图中心度算法的最终得分确定对应的图中心度算法的权重。

最后，根据每一行的图中心度算法的最终得分确定对应的图中心度算法的权重。例如，可以根据得分进行排序，确定出图中心度算法的权重。

S205、基于K种中心度算法，分别计算得到每个子图的中心度得分集合；

对于每个子图sub_graph[i]，根据选择的K种图中心度算法，计算得到对应的中心度得分集合sub_scores[i]＝{algo_score[1],algo_score[2]…algo_score[K]}。

S206、基于每个子图的中心度得分集合以及K种图中心度算法的权重，计算得到每个子图的中心度总分；

对于第i个子图的中心度得分集合sub_scores[i]，按照K种图中心度算法的权重加权，得到第i个子图的中心度总分sub_total_score[i]。

S207、采用优序图法分别确定每个子图的中心度总分的权重；

并分别确定每个子图的中心度总分的权重。

S208、基于每个子图的中心度总分以及每个子图的中心度总分的权重，计算得到目标图形节点的中心度得分。

对于所有子图中心度总分，按照每个子图的中心度总分的权重进行加权得到目标图像节点的总体的中心度得分total_score。

综上所述，本发明在计算图节点的中心度时，既包含了对各图中心度算法的应用，又可以根据实际计算需求选取合适的图中心度算法以及设置权重，又可以允许多种节点属性和边类型的结合，共同决定中心度，相对于现有技术有效提高了图节点的中心度计算的准确性。

如图7所示，为本发明公开的一种图节点的中心度计算系统实施例1的结构示意图，所述系统可以包括：

筛选模块701，用于对目标图形的节点信息和边信息进行筛选，得到筛选后的目标图形的节点信息和边信息；

构成模块702，用于基于筛选后的目标图形的节点信息和边信息构成多个子图；

选择模块703，用于选择K种图中心度算法，其中，K≥2；

第一确定模块704，用于分别确定K种图中心度算法的权重；

第一计算模块705，用于基于K种中心度算法，分别计算得到每个子图的中心度得分集合；

第二计算模块706，用于基于每个子图的中心度得分集合以及K种图中心度算法的权重，计算得到每个子图的中心度总分；

第二确定模块707，用于分别确定每个子图的中心度总分的权重；

第三计算模块708，用于基于每个子图的中心度总分以及每个子图的中心度总分的权重，计算得到目标图形节点的中心度得分。

综上所述，本实施例公开的图节点的中心度计算系统的工作原理与上述图节点的中心度计算方法实施例1的工作原理相同，在此不再赘述。

如图8所示，为本发明公开的一种图节点的中心度计算系统实施例2的结构示意图，所述系统可以包括：

筛选模块801，用于对目标图形的节点信息和边信息进行筛选，得到筛选后的目标图形的节点信息和边信息；

构成模块802，用于基于筛选后的目标图形的节点信息和边信息构成多个子图；

选择模块803，用于选择K种图中心度算法，其中，K≥2；

第一确定模块804，用于采用优序图法分别确定K种图中心度算法的权重；

具体的，如图9所示，第一确定模块804在采用优序图法分别确定K种图中心度算法的权重的其中一种实现方式可以包括：

设置单元901，用于设置棋盘图，将K种图中心度算法分别置于棋盘图的第一列和第一行；

对比单元902，用于将每一行的图中心度算法分别与每一列的图中心度算法进行对比，分别得到两两对比的评分；

求和单元903，用于对每一行的图中心度算法的评分进行横向求和，得到每一行的图中心度算法的最终得分；

确定单元904，用于基于每一行的图中心度算法的最终得分确定对应的图中心度算法的权重。

第一计算模块805，用于基于K种中心度算法，分别计算得到每个子图的中心度得分集合；

第二计算模块806，用于基于每个子图的中心度得分集合以及K种图中心度算法的权重，计算得到每个子图的中心度总分；

第二确定模块807，用于采用优序图法分别确定每个子图的中心度总分的权重；

第三计算模块808，用于基于每个子图的中心度总分以及每个子图的中心度总分的权重，计算得到目标图形节点的中心度得分。

综上所述，本实施例公开的图节点的中心度计算系统的工作原理与上述图节点的中心度计算方法实施例2的工作原理相同，在此不再赘述。

如图10所示，本发明实施例提供了一种设备100，设备100包括至少一个处理器1001、以及与处理器1001连接的至少一个存储器1002、总线1003；其中，处理器1001、存储器1002通过总线1003完成相互间的通信；处理器1001用于调用存储器1002中的程序指令，以执行上述实施例1或实施例2所述的图节点的中心度计算方法。

本申请还提供了一种计算机程序产品，当在数据处理设备上执行时，适于执行初始化有如下方法步骤的程序：

对目标图形的节点信息和边信息进行筛选，得到筛选后的目标图形的节点信息和边信息；

基于所述筛选后的目标图形的节点信息和边信息构成多个子图；

选择K种图中心度算法，其中，K≥2；

分别确定所述K种图中心度算法的权重；

基于所述K种中心度算法，分别计算得到每个子图的中心度得分集合；

基于所述每个子图的中心度得分集合以及所述K种图中心度算法的权重，计算得到每个子图的中心度总分；

分别确定每个子图的中心度总分的权重；

基于所述每个子图的中心度总分以及所述每个子图的中心度总分的权重，计算得到所述目标图形节点的中心度得分。

可选地，所述分别确定所述K种图中心度算法的权重，包括：

采用优序图法分别确定所述K种图中心度算法的权重。

可选地，

所述采用优序图法分别确定所述K种图中心度算法的权重，包括：

设置棋盘图，将所述K种图中心度算法分别置于所述棋盘图的第一列和第一行；

将每一行的图中心度算法分别与每一列的图中心度算法进行对比，分别得到两两对比的评分；

对每一行的图中心度算法的评分进行横向求和，得到每一行的图中心度算法的最终得分；

基于每一行的图中心度算法的最终得分确定对应的图中心度算法的权重。

可选地，

所述分别确定每个子图的中心度总分的权重，包括：

采用优序图法分别确定每个子图的中心度总分的权重。

本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。对于实施例公开的装置而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。

专业人员还可以进一步意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、计算机软件或者二者的结合来实现，为了清楚地说明硬件和软件的可互换性，在上述说明中已经按照功能一般性地描述了各示例的组成及步骤。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本发明的范围。

结合本文中所公开的实施例描述的方法或算法的步骤可以直接用硬件、处理器执行的软件模块，或者二者的结合来实施。软件模块可以置于随机存储器(RAM)、内存、只读存储器(ROM)、电可编程ROM、电可擦除可编程ROM、寄存器、硬盘、可移动磁盘、CD-ROM、或技术领域内所公知的任意其它形式的存储介质中。

对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。