文摘

识别重要的节点在复杂网络在疾病传播控制至关重要,网络攻击的保护,和有价值的信息检测。许多评价指标,如学位中心、介数中心,和亲密感中心,提出了识别重要的节点。一些研究人员分配不同的权重不同的指标,结合在一起来获得最终的评价结果。然而,体重通常是主观分配基于研究者的经验,这可能会导致不准确的结果。在本文中,我们提出一个entropy-based自适应节点重要性评估方法来评估节点客观的重要性。首先,基于复杂网络理论,我们选择四个指标来反映网络结构的不同特征。其次,我们计算基于信息熵理论的不同指标的权重。最后,基于上述的步骤,获得了节点重要性的加权平均法。实验结果表明,我们的方法优于现有方法。

1。介绍

复杂网络在我们的日常生活中发挥着重要的作用。人们相互沟通和与老朋友保持联系通过在线社交网络。互联网连接整个世界,所以现在比以前更快、更广泛的传播信息。电力公司建立自己的网络,为生产和生活提供电力。警察抓捕罪犯通过内部网络合作。然而,识别重要节点在复杂网络在各种情况下是一个至关重要的问题。例如,如果重要节点孤立在疾病传播,疫情将会有效地控制。在交通网络中,我们可以通过采取相应的措施缓解交通拥堵将交通流在某些重要的节点。然而,如何评估节点的重要性不是一项容易的任务,特别是如果存在分层,但复杂的关系,而不是一个扁平的层次结构。一个典型的例子就是移动边缘计算网络,小边云相互连接,但同时遵循安排从云大的优势。 While mobile users may connect to and accept service from both of them [1]。

为了解决这个问题,许多研究者提出了不同的方法来识别复杂网络中重要节点(2]。考虑到节点的本地信息和他们的邻居,学位中心(3),半局部中心(4),和k层分解5)提出了描述节点的重要性。但它没有考虑到移动计算边缘的层节点之间的信息网络。因为这些指标只考虑节点的本地信息,计算复杂度低。然而,他们不能准确地反映整个网络的特点。考虑更多的全球整个网络的特点,亲密中心(6)、介数中心(7)等。这些指标考虑路径和信息流动。因此,这些指标可以反映出更多关于整个网络结构的特征。然而,计算复杂度高。降低时间复杂度,一些研究者提出的方法,将网络划分为若干部分,如以社区为基础的方法(8)和基于集群的方法(9]。除了上述方法外,研究人员还提出了考虑方法不仅邻居的数量,而且邻居的重要性(10- - - - - -13]。这些方法通常迭代一步一步获得每个节点的稳定结果。

从上面的讨论,我们可以发现,大部分的上述指标只能反映一个网络的特征,不能产生一个综合评价。来弥补它,我们可以结合多个指标和分配不同的权重不同的指标来获得更好的评价结果。然而,选择权重赋值通常是基于研究者的主观经验而不是足够的科学依据,这很有可能导致不准确的评价结果。

在本文中,我们提出一个信息熵基于理论的自适应节点重要性评估方法(EBSAM),能客观地评估节点重要性的权重自适应地分配到不同的指标。首先,我们选择四项指标来评估节点分别基于复杂网络理论的重要性。其次,不同指标的权重计算基于信息熵理论。最后,四个指标组合在一起表示节点的重要性。所以提出EBSAM可以结合其他节点重要性的最好的指标和计算它们的权重来创建一个更全面的指标。研究了我们的方法的有效性,我们进行了三种不同的网络和实验结果与其他方法相比。结果表明,该方法执行比现有的方法和提高评估准确性。

剩下的纸是组织如下。部分2简要概述的相关工作。部分3说明了问题定义和其他基本的预赛。节4,我们建议entropy-based自适应评价方法和解释它的技术细节。比较仿真实验结果分析给出了部分紧随其后5。部分6本文总结并指出了未来的工作。

2。相关工作

研究人员已经提出了很多方法来从不同的角度评估节点的重要性。在本节中,我们研究的一些最新的和重要的研究工作在复杂网络节点重要性评估完成。

刘等人。14节点排序法)提出了一种基于线的重要性。首先,该方法计算节点的拓扑属性之间的重要性。此外,每个节点的贡献记录的重要性。排名最后的结果是一个组合节点的度及其贡献的重要性。重要桥梁节点可以确定计算复杂度较低。该方法执行比当前单一的地方中心措施,但仍然没有考虑足够的全球信息更准确的评价。胡锦涛et al。(15应用局部线性嵌入(米歇尔)算法(16)在评估节点的重要性。米歇尔,这通常是用于机器学习,是一个非线性降维技术。为了确定一个复杂网络中的重要节点,提出了几个中心措施。算法的输入是一个矩阵构造通过计算网络中节点的中心地位的措施。然而,由于米歇尔的限制,该算法有一些输入数据的分布要求。徐et al。17)提出了一个综合节点重要性评估方法分类节点到网络中几种类型根据他们的功能。应用不同的衡量指标来评估不同类型的网络节点的重要性。本文以输电电网为例,将节点分为三种类型:电源节点,连接节点和终端负载节点。对于每种类型的节点,获得的排名结果是基于不同的中心措施根据他们的功能网络。虽然这个方法可以精确的评估节点的重要性,只有适用当网络中的节点可以分为几种不同的类型。对于网络节点的功能很难区分,方法表现糟糕。Zhang et al。18)提出了节点重要性评估方法,结合介数中心和中心的亲密接触。他们认为,两种类型的因素决定了节点的重要性。第一个因素是网络中的位置,第二个因素是周边节点的贡献。中间性中心对一个节点的位置有重要影响,和亲密中心可以确定相邻节点的贡献。最后的节点优先两个因素的重要性。Pinget艾尔。19]相信来自相邻的贡献的重要性和不相邻节点对节点重要性有重要影响。他们把节点划分为不同的层根据评估节点的距离。此外,定义了两个参数来表示两个节点之间的依赖强度。概率的贡献从一个节点到另一个用相关参数的重要性。层依赖强度的影响反映在强度相关参数。最终结果结合的重要性评估节点和网络中其他节点的贡献。上面的方法主要是利用本地信息或全球信息来评估节点的重要性。

Yu et al。20.)评估节点的节点重要性考虑两因素接近中心度和节点度。全球节点由亲密表示中心的重要性。当地的节点重要性的特征是相邻节点之间的重要贡献。因此,本地和全局属性节点重要性评估过程中被认为是。胡锦涛et al。(21)提出了一个方法,该方法结合了k层分解算法与社区中心。方法认为不仅节点的本地信息,而且它属于社区的结构。最后的结果是这两个指标的结合。不同的权重分配给这两个指标。然而,重量是基于人们对网络结构的个人经历。因此,评价结果是非常主观的。Zhang et al。22)提出了一种新的算法结合了介数中心和卡茨中心。该方法综合考虑全球本地节点的重要性和节点的重要性。它克服了中间性中心仅考虑最短路径的局限性。此外,它克服了局部最优的Katz中心的局限性。然而,选择这两个指标的权重进行大量的实验数据集有不同的重量值。显然这不是一个好方法来确定权重值进行大量的实验。杨和谢23)提出了节点重要性评估方法通过使用多目标决策方法。他们选择不同的代表性指标。指标权重的计算基于层次分析法。网络中的每个节点都被认为是一个解决方案,每个节点的不同指标被视为解决方案属性。评价结果是通过计算网络中的每个节点的亲密程度的理想解决方案。在这种方法中,不同指标的权重计算使用层次分析法。因此,准确性是高度依赖于研究者的个人经历。同样,刘等人。24)提出了一种多属性排序法在复杂网络节点重要性评估。他们也选择四个代表性指标,利用层次分析法权重分配。最终结果是使用技术获得的顺序偏好相似的理想对象(TOPSIS)。该方法类似于方法在23]。这两种方法的区别在于代表指标选择。上述方法的准确性的问题是高度依赖于研究者的个人经历。

因此,如何分配适当的客观权重不同的指标在不同网络和自适应仍然是一个需要解决的问题。我们将解决这个问题。

3所示。系统模型和节点重要性指标

3.1。复杂网络的拓扑结构

可以将复杂网络建模为无向和未加权的网络。我们定义一个无向和未加权的网络 。 表示组节点在复杂网络 表示复杂网络中边的集合。是网络中节点的总数。

3.2。节点重要性指标的定义

有两种不同的方法在网络节点重要性评估。第一种方法只考虑本地节点的信息,这意味着只有节点本身和其邻居的数量被认为是。第二种类型的方法考虑网络的层次结构的基础设施和网络的每个节点的位置,这意味着全球的信息被认为是一个节点。吸收各自优势和有效的评估节点的重要性,我们采用两个local-information-related归因和两个global-information-related归因。学位中心和改进k层分解可以反映一个节点的局部信息。此外,亲密中心和中间性中心可以反映一个节点的全局信息。

3.2.1之上。学位中心

学位中心(3),即 ,被定义为边数的比值,直接连接到一个节点: 在哪里连接节点的边的数量吗直接。是网络中节点的总数。更大的价值表明节点有更多的邻居。因此,会影响网络中多个节点,是更重要的。

3.2.2。亲密关系中心

亲密关系中心(CC) [6),定义来表示节点的平均距离网络中所有其他节点。假设表示的长度最短路径从源节点到目标节点 。从节点的平均最短的距离所有其他节点在复杂网络可以计算

较小的是,更重要的是多少。亲密的中心的节点被定义为的倒数吗 :

如果没有路径之间和 , 设置为0。更大的价值表明节点接近网络的中心。换句话说,节点的位置网络中是非常重要的。

3.2.3。中间性中心

中间性中心(BC) (7)定义来表示一个节点在数据传输的重要性。假设和网络中两个节点。中间性中心定义如下: 在哪里表示的最短路径的数量来 。 表示最短路径(从节点的数量到节点 )通过节点 。一个更大的表明有更多的最短路径穿过节点 。因此,更重要的是在数据传输的过程。

3.2.4。改进的k层分解

k层分解(5)被用来确认一个节点的位置。k层分解的示意图如图1(一)。首先,从网络中删除所有节点的度是1,并设置它们值为1。重复此操作,直到网络中所有节点的程度大于1。然后设置 ,和连续做删除操作,直到所有节点已经从网络中删除。更大的是,网络中的节点是更加重要。

从定义可以看出,k层分解将相同的值分配给所有节点时,网络是一个明星网络或者树网络。为了克服这一挑战,提出的改进的k层分解(IKs次方)是刘等人在24]。的过程改进的k层分解计算如图1 (b)。首先,被初始化为1。然后,所有节点的度至少目前从网络中删除增加了1。重复此操作,直到所有的节点都从网络中删除。改进的k层分解可以克服的局限性k层分解,可以更精确地反映网络结构的特点。

4所示。我们建议的方法

我们说明的技术细节entropy-based自适应节点重要性评估方法在这一节中。

4.1。属性矩阵的节点

复杂网络中的节点可以用 。选择评价的指标被定义为节点重要性 。 指标的总数。在我们的方法中, ,的属性节点可以表示为 。因此,属性矩阵定义如下:

4.2。数据归一化

不同指标的值可以在不同的范围不同。例如,的价值是一个小数时的值比1大。因此,数据应该规范化之前组合在一起,以便统一的测量。常见的归一化方法包括小数缩放、高斯归一化零均值归一化,min-max正常化,等。min-max规范化方法规范化属性矩阵,定义如下:

规范化属性矩阵如下:

4.3。权重的计算

1948年引入的克劳德·e·香农,熵是衡量的不可预测性和不确定性信息25,26]。例如,当我们掷硬币双头熵为零。这是因为有一个100%的机会得到正面。熵有最大值,当我们扔硬币。从反面的概率等于得到正面的机会,没有办法预测接下来会是什么。熵的一个更小的值表明有更少的有用的信息内容(27- - - - - -31日]。在一个多属性决策问题,我们需要更大的重量分配给属性与更多的有用的信息而不是属性更大的不确定性。通过分析原始数据的概率分布,我们可以获得客观的熵。基于熵的计算每个属性的重量比主观设置更合理。

在这篇文章中,节点是由四项指标及其权重决定的重要性得到基于熵理论。假设每一个指标的权重表示为 。根据香农熵理论,每一个指标的熵可以计算如下: 在哪里是归一化th指标节点的价值 。和 的熵指标。

正如上面提到的,熵越大,越中包含的有用信息的指标。因此,体重应该较小。每一个指标的权重计算如下:

我们现在说明熵和体重之间的关系通过北京邮电大学的校园网(BUPT)作为一个例子。北京大学的校园网络的拓扑结构如图2。这些点在图2表示BUPT校园网的主要节点。熵和体重之间的关系见图3。我们可以看到,熵越大,重量越小。熵值越小,更有用的信息可以提供的指标。因此,熵较小的指标有一个更大的重量。

4.4。节点重要性排名

计算出的节点重要性如下:

更大的 是,节点越重要。

一般在复杂网络中节点重要性计算和节点排序的步骤所示算法1。首先,确定指标 和计算值的四个指标对复杂网络中的所有节点。然后我们构造属性矩阵基于方程(5)。第三,我们计算归一化属性矩阵基于方程(6)和(7)。第四,我们计算熵每一个指标的基于方程(8)和(9)(1 - 11行)。然后,所有指标的权重可以获得基于方程(10)(14 - 16行),节点重要性计算基于方程(11)(17 - 19行)。排名最后,所有节点都基于节点重要性(第20 - 21行)。头节点列表中是最重要的节点。我们的算法的时间复杂度 ,在哪里n表示网络中节点的数量。

5。实验

我们进行了三个实验真正的网络,将我们的方法的结果与随机选择的方法(随机)和TOPSIS-RE方法(24]。实验结果证明我们的方法执行得更好。

5.1。实验设置

所选择的网络是北京邮电大学的校园网(BUPT),山西水网络,山西铁路网络。首先,我们证明了我们的方法的有效性通过实验BUPT校园网络。然后我们山西水网络上说明实验结果和山西铁路网络在更复杂的情况下该方法是如何工作的。是在电脑上进行实验与英特尔酷睿i5 - 3470 3.2 GHz CPU、4 GB RAM。

来说TOPSIS-RE广泛采用的技术相似的理想对象(TOPSIS)评估节点的重要性。TOPSIS-RE的核心思想是建立一个积极的理想对象和一个消极的理想对象从原始数据。积极的理想对象是基于计算的最大价值指标,计算和负理想对象基于最小价值的指标。实现所有方法使用网络分析软件Cytoscape与Java编程语言。

在实验中,所有节点都基于节点重要性排名。然后,节点一个接一个地从网络中移除根据排名结果。连接组件的数量(NCC)是用来评估方法的有效性。连接组件的无向网络子图中,任何两个节点相互连接的边缘。之后我们删除一个或多个节点的网络,该网络将被分成多个不连通子图。任何节点在子图是可以从其他节点在同一子图。没有任何两个节点之间的路径属于不同的子图。NCC是这些断开连接的子图的数量。NCC反映了网络的连通性。网络的鲁棒性可以通过计算测量最大连接组件的大小后删除节点的一小部分(32- - - - - -34]。网络连接组件的数量可以反映其连通性。有更大价值的NCC反映网络分为更多的断开连接的子图,这表明你删除的节点是网络连接方面更重要。因此,一个更大的NCC的值表明更好的性能。一个节点被认为是更重要的是如果更多的连接组件的增加后删除。

5.2。实验结果

5.2.1。实验结果BUPT校园网络

BUPT校园网的拓扑结构如图2。每个节点的数量只是一个节点的身份。它没有任何意义,除了来识别不同的节点。节点数量可以确定的图。

TOPSIS-RE EBSAM的节点重要性排名结果,和一个随机选择算法(随机)见表1。我们只列出了前16节点的排名结果,因为其余节点的排序结果EBSAM和TOPSIS-RE相同。

根据排序的结果,我们删除节点从网络一个接一个,直到所有节点已经从网络中删除。我们计算网络中连接组件的数量后删除一个节点。的去除过程EBSAM图所示4。我们列出网络的拓扑结构后每四节点删除。的NCC EBSAM TOPSIS-RE和随机方法如图5。我们可以看到,随机方法的连接组件的数量远低于其他两种方法。因此,随机有效破坏网络攻击的重要节点。我们还可以看到,连接组件的数量EBSAM TOPSIS-RE以上。因此,网络的连通性与EBSAM更糟。攻击网络基于排名的结果比TOPSIS-RE EBSAM更有效。因为我们获得四项指标客观的重量和自适应除了主观分配一个固定的值。

5.2.2。山西水网络上的实验结果

如图6、山西水网络起着至关重要的作用在正常生产和生活活动。绿线在图6表示供水网络。山西华北的水网络提供了保障需求,及其拓扑结构如图7。如图7水、山西82个节点组成的网络。实验结果显示在图8。我们可以看到,网络的连接已被摧毁后,前50名节点受到攻击。然而,NCC相比,我们的方法比其他两个方法。因此,相比EBSAM性能优于其它方法。

5.2.3。实验结果在山西铁路网络

最后,我们对山西铁路网络进行实验。如图9、山西铁路网络是一个在山西交通网络的一部分。它提供了极大的方便人们的外向和大宗商品交易。山西水网络的拓扑结构如图10。实验结果显示在图11。网络是来分解后60节点受到攻击。山西水网络的NCC得到最大的提升方法。因此,EBSAM执行比其他方法更好。

6。结论和未来的工作

在本文中,我们提出了一个熵基于理论的复杂网络的自适应节点重要性评估方法。首先,我们选择四个中心措施可以反映不同的特征节点的节点重要性评估指标。然后,我们把它们连同适当的权重计算的熵理论基础的算法。该算法显示了一个适应性强,因此允许被被广泛应用于不同的网络。在传统的方法中,选择权重主观经验的基础上,研究人员而不是足够的科学依据,这将导致评价结果不准确。该方法是更好的,因为它利用熵理论来计算各指标的权重。熵的一个更小的值表明,相应的归因含有更少的有用的信息。在一个多属性决策问题,我们需要更大的重量分配给属性与更多的有用的信息而不是属性更大的不确定性。这种算法,我们可以更好地分配适当的重量不同的归因。实验结果对三种类型的真实世界的复杂网络方法相比表明,我们的方法执行得更好。 Our ongoing research will focus on investigating the effectiveness of our method in more complex environments.

数据可用性

使用的数据来支持本研究的发现可以从相应的作者。

的利益冲突

作者宣称没有利益冲突。

确认

本研究由中国国家重点研发项目(资金2018号yfb1402800)和中国自然科学基金(61571066)。