融合接近度和度的网络节点重要性评估方法及其应用

摘要

本申请公开了一种融合接近度和度的网络节点重要性评估方法及其应用。该方法包括：获取待评估网络模型；根据预设的接近度计算公式计算所述待评估网络模型中所有节点的接近度，根据接近度大小按序排列所有节点的接近度，获得接近度序列；按照预设的度计算公式计算所述待评估网络所有节点的度；将所述接近度序列分区，对每个区间内接近度对应的节点按照预设的基于度的重要度计算公式计算重要度，对每个区间内接近度对应的节点根据重要度大小重新排序，输出排序后的节点序列。本发明在重要性评估时，基于度对区间内网络节点进行二次重排序，可以提升节点排序的稳定性。

说明书

技术领域

本申请涉及网络技术领域，更具体地，涉及一种融合接近度和度的网络节点重要性评估方法及其应用。

背景技术

接近度是评估复杂网络节点重要性的一种经典方法，是指节点到其它节点的平均最短距离，可刻画节点对网络中其它节点的影响能力，在社会网络、信息网络中有着广泛的应用。但是在大部分网络中，节点间的平均最短距离都较小，导致接近度值过于密集，网络结构的微小变化会引起排序的显著变化。排序的不稳定性降低了接近度方法的适用范围。

发明内容

针对现有技术的至少一个缺陷或改进需求，本发明提供了一种融合接近度和度的网络节点重要性评估方法及其应用，基于度对区间内网络节点进行二次重排序，可以提升节点排序的稳定性。

为实现上述目的，按照本发明的第一个方面，提供了一种融合接近度和度的网络节点重要性评估方法，包括：

获取待评估网络模型；

根据预设的接近度计算公式计算所述待评估网络模型中所有节点的接近度，根据接近度大小按序排列所有节点的接近度，获得接近度序列；

按照预设的度计算公式计算所述待评估网络所有节点的度；

将所述接近度序列分区，对每个区间内接近度对应的节点按照预设的基于度的重要度计算公式计算重要度，根据重要度大小对每个区间内接近度对应的节点重新排序，输出重新排序后的节点序列。

进一步地，将所述接近度序列分区包括：设置区间长度，根据所述区间长度对所述接近度序列进行分区。

进一步地，所述设置区间长度满足：

其中w表示区间长度，C

进一步地，所述重要度计算公式为：

其中，η

进一步地，所述接近度计算公式为：

其中，c

进一步地，融合接近度和度的网络节点重要性评估方法，还包括步骤：预先定义用于度量网络节点重要性评估准确性和稳定性的准确性计算方法和稳定性计算方法，根据预先定义的计算方法计算网络节点重要性评估准确性和稳定性。

按照本发明的第二个方面，还提供了一种融合接近度和度的网络节点重要性评估系统，包括：

获取模块，用于获取待评估网络模型；

接近度计算模块，用于根据预设的接近度计算公式计算所述待评估网络模型中所有节点的接近度，根据接近度大小按序排列所有节点的接近度，获得接近度序列；

度计算模块，用于按照预设的度计算公式计算所述待评估网络所有节点的度；

重要度计算模块，用于将所述接近度序列分区，对每个区间内接近度对应的节点按照预设的基于度的重要度计算公式计算重要度，根据重要度大小对每个区间内接近度对应的节点重新排序，输出重新排序后的节点序列。

按照本发明的第三个方面，还提供了一种电子设备，其包括至少一个处理单元、以及至少一个存储单元，其中，所述存储单元存储有计算机程序，当所述计算机程序被所述处理单元执行时，使得所述处理单元执行任一项所述方法的步骤。

按照本发明的第四个方面，还提供了一种存储介质，其存储有计算机程序，当所述计算机程序在访问认证设备上运行时，使得所述访问认证设备执行任一项所述方法的步骤。

总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够取得下列有益效果：针对接近度存在的稳定性不足问题，将接近度值区间进行分段，基于度对子区间内网络节点进行二次重排序，设计了一种基于度和接近度的融合方法，提升了节点排序的稳定性，比接近度方法的应用范围更广，可信性更高。

附图说明

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

图1为本申请实施例提供的一种融合接近度和度的网络节点重要性评估方法的流程示意图；

图2为本申请实施例提供的一个BA无标度网络中节点的度分布与接近度分布；

图3为本申请实施例提供的SI模型的传染过程示意图；

图4为本申请实施例提供的融合方法准确性与接近度分段数的关系；

图5为本申请实施例提供的不同生成参数BA无标度网络下融合方法的准确性；

图6为本申请实施例提供的不同生成参数ER随机网络下融合方法的准确性；

图7为本申请实施例提供的不同生成参数BA无标度网络下融合方法的稳定性；

图8为本申请实施例提供的不同生成参数ER随机网络下融合方法的稳定性。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

如图1所示，本申请实施例的一种融合接近度和度的网络节点重要性评估方法，包括：

S101，获取待评估网络模型。

待评估网络模型用于表示网络中的节点以及节点之间的关系。

网络模型可用图G＝(V,E)表示，表示该网络是一个无向无自环的简单网络，其中V＝{v

S102，根据预设的接近度计算公式计算待评估网络模型中所有节点的接近度，根据接近度大小按序排列所有节点的接近度，获得接近度序列。

接近度定义为节点到网络中其它节点的平均最短距离，平均距离越短，该节点越重要。

为保持与其它度量方法的一致性，接近度通常表示为平均最短距离的倒数：

其中，c

d

为应对这种情况，本申请优选将式(1)改进为节点间最短距离的倒数的平均值：

接近度依赖于网络的全局属性，可以准确发现网络的中心节点。现有技术中通常用接近度来评估网络节点重要度。但是由于大多数网络节点间的平均最短距离跨度较小，导致接近度值分布较为密集。当网络结构稍有变化时，如新的节点加入或删除已有节点，会引起排序结果的显著变化。因此，为改进接近度的稳定性，本申请实施例中对于接近度值相近的节点引入新的方法，利用节点的邻居信息进行网络节点重要度评估。

S103，按照预设的度计算公式计算待评估网络所有节点的度。

度定义为该节点相连的边的数量。

在一个实施例中，度计算公式为：

一个BA无标度网络中节点的度分布与接近度分布如图2所示，横轴的C表达接近度，纵轴的K表示度。

S104，将接近度序列分区，对每个区间内接近度对应的节点按照预设的基于度的重要度计算公式计算重要度，根据重要度大小对每个区间内接近度对应的节点重新排序，输出重新排序后的节点序列。

网络节点重要量评估问题，就是对节点的重要性进行区分和排序。对于节点v

在一些无标度网络中，节点的接近度值差距很小，但是度值差距较大，见图3。因此，可利用度值对这些区间中的节点进行重排序。

进一步地，将接近度序列分区包括：设置区间长度，根据区间长度对接近度序列进行分区。

对于网络G，设接近度集合C＝{c

对V

其中，η

在一个具体实施例中，S104包括步骤：

(1)令c

(2)对接近度值位于区间[c

(3)如果c

(4)输出重新排序后的节点序列{η

这里重新排序是指：对于每个区间，在区间内在区间内重新排序，重新排序会改变区间内的节点顺序，不是所有区间节点一起重新排序。假设节点1、2对应的接近度在区间1内，假设节点3、4对应的接近度在区间2内，区间1的接近度均小于区间2的接近度，重新排序是按照节点1、2的重要度来确定节点1、2的顺序，按照节点3、4的重要度来确定节点3、4的顺序。

本发明的融合接近度和度的网络节点重要性评估方法，还包括步骤：预先定义用于度量网络节点重要性评估准确性和稳定性的准确性计算方法和稳定性计算方法，根据预先定义的计算方法计算网络节点重要性评估准确性和稳定性。

(1)准确性评价

节点重要性度量方法的准确性一般通过网络节点传播动力学实验来评价，目标节点的传播范围可在一定程度上表征其影响力。网络节点重要性与节点传播影响力的相关性越高，说明度量方法的准确性越高。这里采用SI模型(Susceptible-Infected model)开展网络节点传播仿真实验。在SI模型中，假设节点具有2个状态：①S状态，即易感态(susceptible state)，指尚未感染但与感染者接触后容易受到感染的状态；②I状态，即感染态(infected state)，指已受感染的状态，感染后的节点将一直处于该状态。在SI模型中，初始目标节点设定为I状态，在仿真的每一步以概率p

假设节点v

其中

节点重要性度量值与传播影响力之间的相关性采用Kendall’s Tau系数衡量[200]。Kendall’s Tau系数用来描述两个序列的相关性，表示为：

其中x

(2)稳定性评价

排序稳定性定义为网络拓扑结构变化后，节点的新排序与原排序的相关性。针对网络G，当节点或边增加或删除后得到新的拓扑结构为G'＝(V',E')，排序稳定性可表示为：

其中N'为V'中节点的数量，v

由理论分析可知，w取值对于融合方法的度量准确性有着重要影响，w取值过大时会降低度量的准确性，过小时对稳定性的提升又不足。对于BA无标度网络，取不同的w值计算融合方法度量值η以及准确性指标τ

其中C

设置BA无标度网络的参数m＝{1,2,…,10}和ER随机网络的参数p＝{0.10,0.15，…,0.60}，为消除随机性影响，每个参数下生成100个网络，实验结果取平均值后如图4和图5所示。随着m和p值的增大，节点的度和接近度分布趋于均匀，由于Kendall’s Tau系数中分段函数在排序相同时取0，导致准确性指标值不断下降。图5中，针对不同结构的BA无标度网络，融合方法的准确性τ

为验证融合方法在网络结构发生轻微变化时的排序稳定性，对给定网络随机删除1个节点，观察剩余节点排序的变化。设置BA无标度网络的参数m＝{1,2,…,10}和ER随机网络的参数p＝{0.10,0.15，…,0.60}，每个参数下生成100个网络。针对每一个网络，首先利用融合方法、度和接近度对节点进行排序；然后，随机删除网络中的一个节点，重新计算剩余节点的排序；最后，计算两个排序的相关性，即稳定性指标θ

本发明实施例的一种融合接近度和度的网络节点重要性评估系统，包括：

获取模块，用于获取待评估网络模型；

接近度计算模块，用于根据预设的接近度计算公式计算所述待评估网络模型中所有节点的接近度，根据接近度大小按序排列所有节点的接近度，获得接近度序列；

度计算模块，用于按照预设的度计算公式计算所述待评估网络所有节点的度；

重要度计算模块，用于将所述接近度序列分区，对每个区间内接近度对应的节点按照预设的基于度的重要度计算公式计算重要度，根据重要度大小对每个区间内接近度对应的节点重新排序，输出重新排序后的节点序列。

系统的实现原理和上述方法相同，此处不再赘述。

本实施例还提供了一种电子设备，其包括至少一个处理器、以及至少一个存储器，其中，存储器中存储有计算机程序，当计算机程序被处理器执行时，使得处理器执行上述实施例中融合接近度和度的网络节点重要性评估方法的步骤，具体步骤参见实施例一，此处不再赘述；本实施例中，处理器和存储器的类型不作具体限制，例如：处理器可以是微处理器、数字信息处理器、片上可编程逻辑系统等；存储器可以是易失性存储器、非易失性存储器或者它们的组合等。

本申请还提供一种存储介质，其上存储有计算机程序，该程序被处理器执行时实现上述方法的步骤。其中，计算机可读存储介质可以包括但不限于任何类型的盘，包括软盘、光盘、DVD、CD-ROM、微型驱动器以及磁光盘、ROM、RAM、EPROM、EEPROM、DRAM、VRAM、闪速存储器设备、磁卡或光卡、纳米系统(包括分子存储器IC)，或适合于存储指令和/或数据的任何类型的媒介或设备。

需要说明的是，对于前述的各方法实施例，为了简单描述，故将其都表述为一系列的动作组合，但是本领域技术人员应该知悉，本申请并不受所描述的动作顺序的限制，因为依据本申请，某些步骤可以采用其他顺序或者同时进行。其次，本领域技术人员也应该知悉，说明书中所描述的实施例均属于优选实施例，所涉及的动作和模块并不一定是本申请所必须的。

在上述实施例中，对各个实施例的描述都各有侧重，某个实施例中没有详述的部分，可以参见其他实施例的相关描述。

在本申请所提供的几个实施例中，应该理解到，所揭露的装置，可通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的，例如所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些服务接口，装置或单元的间接耦合或通信连接，可以是电性或其它的形式。

所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。

另外，在本申请各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。

所述集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储器中。基于这样的理解，本申请的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储器中，包括若干指令用以使得一台计算机设备(可为个人计算机、服务器或者网络设备等)执行本申请各个实施例所述方法的全部或部分步骤。而前述的存储器包括：U盘、只读存储器(Read-Only Memory，ROM)、随机存取存储器(Random Access Memory，RAM)、移动硬盘、磁碟或者光盘等各种可以存储程序代码的介质。

本领域普通技术人员可以理解上述实施例的各种方法中的全部或部分步骤是可以通进程序来指令相关的硬件来完成，该程序可以存储于一计算机可读存储器中，存储器可以包括：闪存盘、只读存储器(Read-Only Memory，ROM)、随机存取器(Random AccessMemory，RAM)、磁盘或光盘等。

以上所述者，仅为本公开的示例性实施例，不能以此限定本公开的范围。即但凡依本公开教导所作的等效变化与修饰，皆仍属本公开涵盖的范围内。本领域技术人员在考虑说明书及实践这里的公开后，将容易想到本公开的其实施方案。本申请旨在涵盖本公开的任何变型、用途或者适应性变化，这些变型、用途或者适应性变化遵循本公开的一般性原理并包括本公开未记载的本技术领域中的公知常识或惯用技术手段。说明书和实施例仅被视为示例性的，本公开的范围和精神由权利要求限定。

以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。