CN105787143A

CN105787143A - 一种基于骨干网的复杂网络的结构调整方法及系统

Info

Publication number: CN105787143A
Application number: CN201410830282.8A
Authority: CN
Inventors: 赵志龙; 王琪
Original assignee: Beijing Simulation Center
Current assignee: Beijing Simulation Center
Priority date: 2014-12-25
Filing date: 2014-12-25
Publication date: 2016-07-20

Abstract

本发明公开一种基于骨干网的复杂网络的结构调整方法及系统，该方法包括步骤：提取实际应用复杂网络的拓扑结构；对原始复杂网络的拓扑结构进行分形特性分析；基于介数和生成树理论提取复杂网络拓扑结构的骨架树；基于盒子覆盖算法对复杂网络的骨干网进行分形调整；基于捷径修改策略对复杂网络的非骨干网进行分形调整；对复杂网络结构调整方法应用后的分形特性进行分析与验证。本发明所述技术方案，能够对复杂网络的拓扑结构进行调整使之呈现出分形特性，有效地提高复杂网络的鲁棒性和抗攻击能力，成本低廉且具有可操作性。

Description

一种基于骨干网的复杂网络的结构调整方法及系统

技术领域

本发明涉及复杂网络的结构调整方法。更具体地，涉及一种基于骨干网的复杂网络的结构调整方法及系统。

背景技术

着各种新的信息技术的日趋成熟，人类社会也随之进入了网络的海洋。在计算机科学中，有Internet、万维网等；在社会生活中，有电力网络、交通网络等；在生物科学中，有脑神经网络、相互作用网络等；此外，还有商业合作网络以及人力关系网络等等。分形特性作为复杂网络的重要性质，在实际环境中的应用非常广泛。它能够有效地提高复杂网络的鲁棒性和抗攻击能力，研究复杂网络的分形特性具有非常重要的意义。现实中并不是所有的复杂网络都具有分形特性，为了适应某些网络高鲁棒性的需求，有必要设计一种复杂网络分形重构方法来满足要求。

在复杂网络的分形特性研究中，研究人员将介数理论与生成树理论相结合，提出了研究复杂网络的具有最大边介数的生成树的观点，并将这种具有最大边介数的生成树定义为复杂网络的骨干网。利用该方法得到的骨干网能够有效地保留原始网络的全局信息，致使原始复杂网络的性质能够很大程度地保留在骨干网中。这样的研究方法大大简化了复杂网络的研究，同时又不失原始网络的性质。

因此，针对现有技术缺乏复杂网络分形重构方法的问题，需要提供一种基于骨干网的复杂网络的结构调整方法及系统，从而达到改造复杂网络拓扑结构使其表现出分形特性的目的。

发明内容

本发明的一个目的在于提供一种基于骨干网的复杂网络的结构调整方法。

本发明的另一个目的在于提供一种基于骨干网的复杂网络的结构调整系统。

为达到上述目的，本发明采用下述技术方案：

一种基于骨干网的复杂网络的结构调整方法，该方法包括如下步骤：

S110、提取复杂网络的拓扑结构；

S130、根据复杂网络的拓扑结构，基于介数和生成树理论提取复杂网络的骨干网和非骨干网；

S140、基于盒子覆盖算法对复杂网络的骨干网进行分形调整；

S150、基于捷径修改策略对复杂网络的非骨干网进行分形调整。

优选地，步骤S110进一步包括子步骤：

S111、提取复杂网络中的各个独立个体作为节点；

S112、采用边连接的方式表示节点间存在的联系。

优选地，步骤S130进一步包括如下子步骤：

S131、采用介数计算方法计算复杂网络中各条边的边介数，并将边介数作为各条边的权值；

S132、按照复杂网络中各条边的权值降序顺序依次选取每一条边加入一个只有节点的网络，若加入后新的网络不产生回路，则保留该边；若加入后新的网络产生回路，则不保留该边；

S133、将步骤S132生成的新的网络作为复杂网络的骨干网，将不属于步骤S122生成的新的网络的边组成的网络作为复杂网络的非骨干网。

优选地，步骤S140进一步包括如下子步骤：

S141、设定覆盖骨干网的盒子的边长为1；

S142、利用盒子覆盖算法对骨干网进行覆盖，得出覆盖骨干网所需要的最小盒子数并保存各个盒子的中心节点；

S143、若任意两个盒子的中心节点之间存在边连接，则在骨干网中建立这两个中心节点邻接的非中心节点之间的边连接替换原中心节点之间的边连接；

S144、以1为单位逐渐增大盒子的边长，迭代步骤S142和S143，直到覆盖骨干网所需要的盒子数为1。

优选地，该方法进一步包括：迭代2或3次步骤S140之后再转入步骤S150。

优选地，步骤S150进一步包括如下子步骤：

S151、选取复杂网络中离心率最接近复杂网络半径的节点作为骨干网根节点；

S152、计算骨干网中各个节点与根节点的最短路径长度、任意两个节点在骨干网的最短路径长度和骨干网的平均最短路径长度；

S153、将非骨干网中两端节点相对于骨干网根节点的最短路径长度差小于等于1且两端节点在骨干网中的最短路径长度小于骨干网的平均最短路径长度的边作为本地捷径；将非骨干网中两端节点相对于骨干网根节点的最短路径长度差大于1或者两端节点在骨干网中的最短路径长度大于等于骨干网的平均最短路径长度的边作为全局捷径；则非骨干网的边被分为本地捷径和全局捷径两部分；

S154、选取各个全局捷径两端节点中的任意一个节点，根据本地捷径的定义选取能与该节点建立不属于复杂网络的边的本地捷径的节点集合，若节点集合不为空，则从节点集合中选取任意一个节点与该节点建立本地捷径替换原全局捷径；若节点集合为空，则不对原全局捷径作调整。

优选地，步骤S110之后且步骤S130之前还包括如下步骤：

S120、根据复杂网络的拓扑结构，基于盒子覆盖算法分析复杂网络的分形特性，若复杂网络的分形特性未呈现或呈现不明显，则转入步骤S130；若复杂网络的分形特性呈现明显，则结束流程。

优选地，步骤S150之后还包括如下步骤：

S160、基于盒子覆盖算法分析经过分形调整后的复杂网络的分形特性。

优选地，基于盒子覆盖算法分析复杂网络的分形特性进一步包括如下子步骤：

利用边长l_B为1的盒子覆盖具有N₀个节点的复杂网络，统计覆盖整个复杂网络所需要的最少盒子数N_B(l_B)；

根据盒子的边长l_B和覆盖整个复杂网络所需要的最少盒子数N_B(l_B)计算复杂网络的分形维数d_B，计算公式如下：

d_{B} \approx - \frac{\ln N_{B} (l_{B})}{\ln (l_{B})};

以1为单位逐渐增大盒子的边长l_B，直到覆盖整个复杂网络所需要的最少盒子数N_B(l_B)为1，计算并记录每一次增大盒子边长l_B后复杂网络的分形维数；若每一次增大盒子边长l_B后复杂网络的分形维数近似相等，则该复杂网络的分形特性呈现明显；若每一次增大盒子边长l_B后复杂网络的分形维数不近似相等，则该复杂网络的分形特性未呈现或呈现不明显。

一种如前文所述方法的基于骨干网的复杂网络的结构调整系统，该系统包括：

网络结构提取模块，用于提取复杂网络的拓扑结构；

骨干网提取模块，用于根据复杂网络的拓扑结构，基于介数和生成树理论提取复杂网络的骨干网和非骨干网；

骨干网分形调整模块，用于基于盒子覆盖算法对复杂网络的骨干网进行分形调整；

复杂网络分形调整模块，用于基于捷径修改策略对复杂网络的非骨干网进行分形调整；

复杂网络分形验证模块，用于根据复杂网络的分形维数分析复杂网络的分形特性。

本发明的有益效果如下：

本发明所述技术方案，在骨干网理论基础之上，提出了一种有效的复杂网络拓扑结构分形调整方法。该方法适用于现实生活中Internet、万维网、电力网络、交通网络等复杂网络，能够对其拓扑结构进行调整使之呈现出分形特性，有效地提高复杂网络的鲁棒性和抗攻击能力。同时，本发明所述技术方案同样适用于脑神经网络、相互作用网络、社交网络等自然科学中的复杂网络，对于这些领域的复杂网络拓扑结构调整的研究具有重要的意义。本发明所述技术方案通过对复杂网络的现有结构进行调整，达到优化现有复杂网络的目的，成本低廉且具有可操作性。

附图说明

下面结合附图对本发明的具体实施方式作进一步详细的说明。

图1示出基于骨干网的复杂网络的结构调整方法的流程图。

图2示出提取复杂网络的骨干网的示意图。

图3示出对骨干网进行分形调整的示意图。

图4示出基于骨干网的复杂网络的结构调整系统的示意图。

具体实施方式

为了更清楚地说明本发明，下面结合优选实施例和附图对本发明做进一步的说明。附图中相似的部件以相同的附图标记进行表示。本领域技术人员应当理解，下面所具体描述的内容是说明性的而非限制性的，不应以此限制本发明的保护范围。

如图1所示，本实施例提供的基于骨干网的复杂网络的结构调整方法的具体步骤为：

S110、提取实际应用复杂网络的拓扑结构。

为了实现对于实际复杂网络拓扑结构特性的理解和分析，需要使用数学建模的思想将其转化为抽象的、易于研究的模型。

在具体提取过程中，先将实际应用复杂网络中的每个独立个体提取为一个节点。当个体与个体之间存在联系时，使用一条边进行连接表示两者之间存在联系。如果个体与个体之间的联系存在强弱区别，采用为边附权值的方式表示强弱。经过上述网络结构提取，将会得到实际应用复杂网络的数学模型。该模型完整地保存了实际网络的拓扑特性，为分形特性研究以及结构调整方法的验证提供真实的数据支撑。

S120、采用复杂网络分形特性分析方法对原始复杂网络的拓扑结构进行分形特性分析。

如果已经满足分形特性的条件，呈现出明显的分形特性，满足高鲁棒性的要求，则无需再进行结构调整；如果尚未满足分形特性的条件，分型特性未呈现或呈现不明显，不能达到高鲁棒性要求，则进行下述步骤的拓扑结构调整和改造。

具体的分析方法参见步骤S160中的盒子覆盖法，此步骤与步骤S160的分析方法相同。

S130、提取复杂网络拓扑结构的骨架树。

基于介数和生成树的理论提取复杂网络的骨干网络。

在复杂网络骨干网的提取过程中，采用介数计算方法对复杂网络的边介数进行计算，使用每条边的边介数值作为权值，将原始网络转化成一个无向有权网络。边介数是指网络中经过该边的最短路径的数目占所有最短路径总数的比例。其中的最短路径是一个完整的概念，它是复杂网络理论中一个基本概念，对于无权网络，将边权值设为一个单位长度，计算节点间最短路径；对于有权网络，基于网络中各边的权值，计算节点间最短路径。

如图2所示，对于一个给定的复杂网络G，它的骨干网提取过程具体描述如下：

131)针对给定的复杂网络G使用边介数算法计算每条边的介数值；

132)构造新的复杂网络G¹。G¹与G网络拓扑结构相同，每条边的权值为步骤131)中计算出来的边介数值；

133)对G¹中的所有的边根据权值大小进行降序排列，得到一个降序排列的边集合S；

134)定义一个空的网络T，依次从S中选取一条边e。若加入边e后，T中不产生回路，则将e添加到T中；否则，不将e添加到T中；

135)重复步骤134)直到T为G的一棵生成树。

经过上述步骤，从给定的复杂网络G中构建了具有最大边介数之和的生成树T，也就是G的骨干网。骨干网提取模块使用上述方法完成复杂网络的骨干网提取。

S140、对复杂网络的骨干网进行分形调整。

对提取出的复杂网络骨干网进行分形调整，在复杂网络的中心支撑网上完成分形调整。

分形产生的根源是复杂网络中覆盖所用盒子的中心节点的互斥性。根据这一特点对骨干网进行调整，将原来骨干网中存在边相连的中心节点调整为其邻接的非中心节点相连，从而使骨干网呈现分形特性。骨干网分形调整原理如图3所示。其中的盒子的中心节点的定义如下：一个盒子所覆盖的网络部分可以看成一个子网络，中心节点是指节点离心率最近似于盒子半径的节点，在几何学上就是最近似于中心的节点。

具体的调整过程如下：

141)从盒子直径大小为1开始，使用盒子覆盖算法对骨干网进行盒子覆盖，求出对应的覆盖盒子数并保存对应的盒子中心节点，其中的盒子直径是盒子中任意两个节点的最大距离；

142)对于每一对中心节点，若两者之间存在边相连，则转而由原始网络中两个中心节点的邻接非中心节点进行替换；否则，保持现有的网络结构；

143)以1为单位逐渐增大盒子的直径，重复步骤141)和142)，直到覆盖整个网络所需的盒子个数为1；

在每次进行完上述调整过程后，骨干网的拓扑结构会发生变化，中心节点可能会发生变化。为了保证效果，我们迭代执行上述调整过程，使网络结构趋向稳定。实验表明，迭代次数2-3次能够达到较为理想的效果。至此，完成了复杂网络的骨干网呈现分形特性的调整。

S150、对非骨干网路径进行分形调整。

在完成上面的复杂网络分形骨干网的构建以后，需要设计有效的捷径修改策略来完成拓扑结构的调整，其中的捷径为原复杂网络模型中不属于骨干网的边的集合。为了尽可能少地改变原始网络的结构，采用仅调整复杂网络的边而不添加或删除其中的边的策略来完成调整过程。为了方便对捷径分布进行调整，本技术方案中定义：

本地捷径为两个节点相对于骨架树根节点的最短路径长度差小于等于1同时满足两个节点的在骨干网中的最短路径长度小于骨干网的平均最短路径长度的边；

全局捷径为两个节点相对于骨干网根节点的最短路径长度差大于1或者两个节点在骨干网中的最短路径长度大于等于平均最短路径长度的边。

具体的调整过程如下：

151)确定上述调整完成后的骨干网的根节点，方法是：使用离心率最接近复杂网络半径的节点作为骨干网的根节点，这样的节点在几何学上最接近复杂网络的中心，其中的复杂网络半径是复杂网络中的概念，此处指整个复杂网络中距离最远的两个节点间距离的一半取整，而节点的离心率是复杂网络中的概念，定义为一个节点到其他节点路径的最大值；

152)计算复杂网络的骨干网中每个节点与根节点的最短路径长度、任意两个节点在骨干网中的最短路径长度以及骨干网的平均最短路径长度；

153)对于复杂网络的捷径，根据上述本地捷径和全局捷径的定义判断其捷径类型并进行标记；

154)对于全局捷径，随机选取该边的两个节点中的一个，计算能与该节点构成不属于复杂网络的边的本地捷径的节点集合，如果此节点集合不为空，则从构成本地捷径的节点集合中随机选取一个构成本地捷径，删除原来的全局捷径，达到全局捷径向本地捷径调整的目的。但此节点集合可能为空，比如一个节点，他连接两条边：一个全局捷径，一个是本地捷径。那对应的节点集合中只有一个与它连接的节点。但是因为要保证整个复杂网络的边连接数保持不变，所以不能把原有全局捷径调整成本地捷径，这样会减少网络中的边连接数。

155)重复步骤154)直到所有的全局捷径都被进行了调整。

通过上述过程达到复杂网络中本地捷径比例增大、全局捷径比例减小，使整个复杂网络呈现分形特性。

S160、对复杂网络结构调整方法应用后分形特性的分析与验证。

在一般情况下，仅仅通过局部缩放一定程度后简单地和整体保持完全重合并不能完全体现复杂网络的分形特性，它具有更加复杂的呈现形式。在复杂网络分形特性的定量分析中，分形维数作为最主要的特性度量不会因为缩放操作而变化。理论研究中均从分形维数不变性的角度对复杂网络的分形特性进行验证。通常计算复杂网络的分形特性的分形维数方法是盒子覆盖法。复杂网络研究者通过将盒子覆盖算法应用于复杂网络的分形特性研究，证明了许多复杂网络存在近似固定的分形维数从而具有某种内在的分形特性这一事实。

分形维数计算的基本思想是：用边长为l_B的盒子来覆盖具有N₀个节点的复杂网络，盒子中任意两个节点之间的距离都小于l_B，计算覆盖整个复杂网络所需要的最少盒子数目N_B(l_B)，其中的距离为两个节点间的最短路径长度。盒子数目满足：

N_{B} (l_{B}) \approx {l_{B}}^{{- d}_{B}}

公式(1)；

等价地，复杂网络的分形维数计算公式为：

d_{B} \approx - \frac{\ln N_{B} (l_{B})}{\ln (l_{B})}

公式(2)；

在理论上来说，当盒子尺寸l_B趋近于零时，公式(2)才能得到分形维数的精确计算结果。对数坐标系中画出N_B(l_B)和l_B之间的关系，并使用曲线拟合的方法对数据进行拟合操作，拟合出来的直线的斜率的负值即为d_B。

在复杂网络拓扑结构调整前后，采用盒子覆盖法计算复杂网络的分形维数，进行N_B(l_B)和l_B之间的对数关系的曲线拟合，分析复杂网络拓扑结构的分形特性，验证复杂网络结构调整方法的有效性。此处的边长等价于盒子覆盖方法里的直径，在分析过程中，从1开始逐渐增大盒子的边长，直到覆盖网络所用盒子数为1。每一次覆盖完成，记录一组数据，对应一个分形维数的值。若在不同l_B下通过使用盒子覆盖算法统计覆盖盒子数，进一步计算出来的分形维数近似相等的话，则该复杂网络具备分形特性。在几何学表现出来，就是N_B(l_B)和l_B之间对数关系的曲线拟合后成为一条直线。换句话说，如果该对数关系如果拟合成为一条直线，则证明满足公式(2)，该复杂网络具有分形特性。

如图4所示，本实施例提供的基于骨干网的复杂网络的结构调整系统是在骨架树理论基础上通过数学建模的方法来实现，该系统包括：网络结构提取模块、骨干网提取模块、骨干网分形调整模块、复杂网络分形调整模块和复杂网络分形验证模块。骨干网提取模块用于基于介数和生成树理论提取复杂网络的骨架树，作为原始复杂网络的骨干网；骨干网分形调整模块用于完成基于盒子覆盖方法的复杂网络结构的分形调整，得到具备高鲁棒性的骨干网；复杂网络分形调整模块用于在骨干网分形调整模块结果的基础上，进一步完成对不属于骨干网的边结构的分形调整；复杂网络分形验证模块用于对分形前后结果进行分析，从而验证方法有效性。

以下是对基于骨干网的复杂网络的结构调整系统中各模块的具体说明：

网络结构提取模块，用于构建复杂网络的拓扑结构模型：

计算机科学中Internet、万维网等；社会生活中电力网络、交通网络等；生物科学中脑神经网络、相互作用网络等；还有商业合作网络以及人力关系网络等等，这些都是实际生活中存在的复杂网络。为了实现将实际复杂网络拓扑结构为抽象的、易于研究的模型，先将实际应用复杂网络中的每个独立个体提取为一个节点。当个体与个体之间存在联系时，使用一条边进行连接表示两者之间存在联系。如果个体与个体之间的联系存在强弱区别，采用为边附权值的方式表示强弱。经过上述网络结构提取步骤，将会得到实际应用复杂网络的数学模型。该模型完整地保存了实际网络的拓扑特性，为分形特性研究以及结构调整方法的验证提供真实的数据支撑。

复杂网络分形验证模块，用于分析原始复杂网络的分形特性：

针对网络结构提取模块构建的实际应用复杂网络模型，需要采用复杂网络分形特性分析方法对原始复杂网络的拓扑结构进行分形特性分析。如果已经满足分形特性的条件，呈现出明显的分形特性，满足高鲁棒性的要求，则无需再进行结构调整；如果尚未满足分形特性的条件，分型特性未呈现或呈现不明显，不能达到高鲁棒性要求，则进行下述步骤的拓扑结构调整和改造。

分形调整方法的模块组合，用于对复杂网络进行调整：

在原始复杂网络的拓扑结构进行分形特性分析的基础之上，对于需要进行复杂网络结构调整的网络，使用本发明中提出的基于骨干网的复杂网络结构调整方法进行重构。首先，使用骨干网提取模块提取复杂网络的骨干网络；然后，使用骨干网分形调整模块对提取出来的骨干网进行分形结构调整；最后，使用复杂网络分形调整模块对原始网络中不属于其骨干网的路径进行分形调整。经过上述重构步骤，将会得到新的与原始复杂网络具有相同数量的节点和边，但具有不同拓扑结构的新的复杂网络。记录整个调整过程中原始复杂网络的边连接的节点以及调整后的边连接的节点，作为后续实际应用中复杂网络结构调整的依据。

复杂网络分形验证模块，还用于分析重构后复杂网络的分形特性

上述系统理论上能够实现非分形网络向分形网络的有效转化，仍需要使用复杂网络分形验证模块对调整产生的新复杂网络进行分形特性分析。对比分析调整前后的验证结果，验证该方法的有效性和实用性，保证调整后的网络结构呈现稳定的分形特性。

在经过分形调整方法的模块组合对复杂网络的结构调整和复杂网络分形验证模块对调整前后复杂网络的分形特性对比分析验证之后，得到了具有高鲁棒性的复杂网络模型。该复杂网络模型与原始实际应用网络具有相同的节点数，不同的拓扑结构。明确调整前后的复杂网络模型与实际应用的复杂网络拓扑结构的对应关系，按照调整的情况，对实际应用的复杂网络拓扑结构进行实际的调整，达到实际应用复杂网络的高鲁棒性要求。从实际生活中的复杂网络，例如：计算机网络、电力网络、生物网络等，提取出理论模型，然后应用该系统进行分形调整增强鲁棒性，记录该方法调整过程中发生变化的边，并根据这个改变的记录对实际复杂网络进行边调整，其中的边为实际网络中的连接。

本发明所述技术方案，通过对复杂网络拓扑结构的优化调整，使经过调整后的复杂网络模型与原始实际应用网络具有相同的节点数、不同的拓扑结构，使整个复杂网络呈现出分形特性，提高了复杂网络的鲁棒性和抗攻击能力。

显然，本发明的上述实施例仅仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定，对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动，这里无法对所有的实施方式予以穷举，凡是属于本发明的技术方案所引伸出的显而易见的变化或变动仍处于本发明的保护范围之列。

Claims

1.一种基于骨干网的复杂网络的结构调整方法，其特征在于，该方法包括如下步骤：

S110、提取复杂网络的拓扑结构；

S140、基于盒子覆盖算法对复杂网络的骨干网进行分形调整；

2.根据权利要求1所述的基于骨干网的复杂网络的结构调整方法，其特征在于，所述步骤S110进一步包括如下子步骤：

S111、提取复杂网络中的各个独立个体作为节点；

S112、采用边连接的方式表示节点间存在的联系。

3.根据权利要求1所述的基于骨干网的复杂网络的结构调整方法，其特征在于，所述步骤S130进一步包括如下子步骤：

4.根据权利要求1至3任一项权利要求所述的基于骨干网的复杂网络的结构调整方法，其特征在于，步骤S140进一步包括如下子步骤：

S141、设定覆盖骨干网的盒子的边长为1；

5.根据权利要求1所述的基于骨干网的复杂网络的结构调整方法，其特征在于，该方法进一步包括：迭代2或3次步骤S140之后再转入步骤S150。

6.根据权利要求1至3任一权利要求所述的基于骨干网的复杂网络的结构调整方法，其特征在于，步骤S150进一步包括如下子步骤：

S154、选取各个全局捷径两端节点中的任意一个节点，根据本地捷径的定义选取能与该节点建立不属于复杂网络的边的本地捷径的节点集合，若所述节点集合不为空，则从所述节点集合中选取任意一个节点与该节点建立本地捷径替换原全局捷径；若所述节点集合为空，则不对原全局捷径作调整。

7.根据权利要求1所述的基于骨干网的复杂网络的结构调整方法，其特征在于，所述步骤S110之后且所述步骤S130之前还包括如下步骤：

8.根据权利要求1所述的基于骨干网的复杂网络的结构调整方法，其特征在于，所述步骤S150之后还包括如下步骤：

9.根据权利要求7或8所述的基于骨干网的复杂网络的结构调整方法，其特征在于，基于盒子覆盖算法分析复杂网络的分形特性进一步包括如下子步骤：

d_{B} \approx - \frac{1 n N_{B} (l_{B})}{1 n (l_{B})};

10.一种如权利要求7或8所述方法的基于骨干网的复杂网络的结构调整系统，其特征在于，该系统包括：

网络结构提取模块，用于提取复杂网络的拓扑结构；