英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

---

基于差分进化计算复杂网络分形维数的盒子覆盖算法

摘 要：通过实施盒子覆盖的重整化步骤，复杂网络的分形性质被发现。盒子覆盖方法中还没解决的问题是找到覆盖整个网络的最小盒子数目。本文中，我们介绍一种基于贪婪图着色方法的差分进化盒子覆盖算法，并将它应用到具有不同结构的基准网络中。比如：有较小聚类系数和较高模块度的E.coli新陈代谢网络，有较大聚类系数和较低模块度的聚类无标度网络，一些有较高聚类系数的社区网络（政治书籍网络，海豚网络和美国足球联赛网络）。实验结果表明，在大多数情况下，我们的算法比现有的算法取得更好的结果，特别是在高聚类的社交网络上有显著提高。

关键词：分形网络 分形维数 差分进化算法 盒子覆盖算法

1 介绍

现在，越来越多的研究者注意到复杂网络的研究，特别是在统计机制和拓扑结构上[1][2][3]。为了揭示基础的拓扑特征，许多研究者已经研究了复杂网络的分形性质。在2005年，Song等人提出了一种重整化过程将网络分割成固定大小的盒子[4]。重整化过程通过盒子覆盖方法来实施，这种做法受到了欧式空间中盒子计数法的启发[5]。通过重整化的过程，他们发现很多实际网络有分形性质，比如：万维网，蛋白质相互网络，细胞网络。分形性质定义为[4]：

,

其中表示用尺寸为的盒子覆盖整个网络所需的最小数量，定义为分形维数。分形的物理意义在过去十年里已经被广泛研究[6][7][8]。

然而，在盒子覆盖方法中有一个未解决的问题：给定盒子的尺寸，如何用最少数量的盒子覆盖网络。找上述问题的最优解是一个NP难问题[9]。很多算法已经被应用到盒子覆盖问题，比如：将盒子覆盖问题转化为图着色问题的贪婪图着色算法[10]；确保盒子中节点联通的最大排除质量燃烧算法[10]；随机选择种子节点，然后不断将邻居节点添加进来的随机燃烧算法[11]；基于模拟退火的边覆盖方法[12]；归并算法[13]。这些算法得到的结果相近。由于时间复杂度低和实现简单，图着色算法被广泛使用。后来，Schneider等人提出了一种优化算法[14]。它用燃烧方法创建所有可能的盒子，然后逐渐减少不必要的盒子，再将网络划分为子网，并将子算法应用到每一个子网中。对许多实际网络，该算法有显著提高，但这种算法不适合聚类社区网络。

本文中，我们提出了一种基于贪婪图着色方法的差分进化盒子覆盖算法（differential evolution box-covering, DEBC）。DEBC算法不受网络结构的影响，能在聚类社区网络中得到稳定的提高。我们将DEBC算法、标准贪婪着色算法、Schneider的算法在5个基准网络中进行比较。结果表明，DEBC算法与贪婪图着色算法相比有显著提高，在大多数情况下与Schneider的算法结果相近。但是在聚类社区网络中，DEBC算法比Schneider的算法有显著提高。

本文结构如下：在第二小节，我们给出盒子覆盖问题转化为图着色问题的详细过程；在第三小节，我们介绍传统差分进化算法的结构；在第四小节，我们将差分进化算法应用到盒子覆盖问题上；在第五小节，我们将3种算法在5个基准网络中的结果进行比较；最后，在第六小节，我们对我们的工作进行总结。

2 盒子覆盖到图着色

盒子覆盖方法被定义为用数量最少的不重叠盒子覆盖网络，所有盒子尺寸相同为，它是盒子中任意一对节点之间最短路径长度的上界。我们只考虑无向无权网络，两个直接相连的节点之间距离为1。Dijkstra算法和Floyd-Warshall算法[15][16]用来求任意一对节点之间的最短路径。

盒子覆盖问题可以转化为对偶网络的图着色问题[10]。图着色问题定义为找网络的色数（对整个网络染色所需的最少颜色数）满足任意两个直接相连的节点颜色不同。对偶网络构造如下：如果两个节点之间的最短距离不小于盒子尺寸，那么这两个节点就直接相连。如图1所示，给定7个节点的图，我们得到盒子尺寸的对偶网络，然后我们用贪婪算法对进行着色，色数。因此，通过从到依次计算对偶网络的色数来计算网络的分形维数。

3 差分进化算法

差分演化（DE）算法是由Storn R和Price K提出的一种新的进化技术[17][18]。由于它的高效性和简单的数学结构，DE已经被广泛地用于复杂函数优化、神经网络训练和数据挖掘。

差分进化算法有三个主要步骤：变异，交叉和选择[17]。一般根据变异策略的不同来区分不同的DE算法。本文中，我们用策略。具体来说，对于一个维空间的搜索问题，一个群体由个参数向量构成，，其中代表进化代数，表示种群中个体的数量。问题的适应度函数由表示。新向量是经过变异和交叉过程产生的。然后，通过选择过程在新向量和原始向量中选择一个更好的。

3.1 变异

差分进化算法和其它进化算法的主要区别是变异过程。新向量根据如下公式产生[17]:

其中从区间中随机选取，是常数控制参数，向量差的放大因子。

3.2 交叉

为了提高群体的多样性，交叉过程根据交叉概率产生新个体。新向量由如下公式产生：

其中，定义如下：

其中，是区间中的随机数。

3.3 选择

在选择过程中，程序用贪婪策略在原始向量和交叉向量中选择更好的向量，并放入下一代的群体中。选择操作定义如下：

其中，是的适应值，是的适应值。

4 差分进化盒子覆盖(DEBC)算法

很多算法已被应用于解决盒子覆盖问题。正如我们在第二小节中介绍的，盒子覆盖问题能转化为对偶网络的图着色问题。确定性的贪婪图着色算法被广泛应用[10]，它是一种有效的方法，但它得到的结果通常和全局最优解相去甚远，而且容易陷入局部最优解中。通过第三小节中的进化策略，差分进化算法可以避免这个缺点，找到近似的全局最优解。在本小节中，我们展示我们基于确定性贪婪图着色算法的差分进化盒子覆盖算法（DEBC）。

4.1 基于贪婪算法的个体编码

如图2所示，图中节点的顺序决定了对图着色的最少颜色数[19]。每一个个体代表一种图的节点顺序。差分进化算法中个体可以表示为，其中表示代数，表示图中节点的数量，是区间中的一个随机数，数值大小决定了第个节点的顺序。贪婪着色算法的伪代码如算法1所示[10]。

算法1 贪婪着色算法

要求：是一个对网络节点顺序进行编码的向量，是网络中节点的数量， 是代表节点的顺序ID的变量

目标：最小化

将的值按升序排列，根据排序从到对所有节点指定唯一的顺序ID

指定颜色给顺序ID的节点，建立一个颜色集，并把添加进去

For

建立一个局部颜色集

For

如果在对偶网络中节点和节点直接相连，就把节点的颜色添加到

End

如果集合非空，就随机从选择一种颜色指定给节点；否则，创建一种新颜色，将颜色指定给节点并添加到

End

集合中的颜色数，就是盒子数

4.2 适应度的定义和DEBC算法的框架

DEBC算法中个体的适应度函数定义如下：

其中是通过贪婪着色算法求得的对个体着色的颜色数。在每一代中，我们首先用交叉和变异操作改变顶点的序列，然后通过贪婪着色算法评价所有个体的适应度，最后通过贪婪选择策略来选择目前最好的序列。DEBC的伪代码如算法2所示。

算法2 EDBC算法

要求：表示代数，表示种群的数量，表示变异步骤中的控制参数，表示交叉步骤中的控制参数，是进化的最大代数

目标：优化

设置参数，并随机初始化

通过计算最短路径长度求出给定的对偶网络

通过贪婪着色算法计算每一个个体的适应值

Do

变异策略：

For

End

交叉策略：

For

End

通过贪婪着色算法计算每一个个体的适应值

选择策略：

Until ()

4.3 DEBC算法的复杂度

在我们应用的三种算法中，最快的是贪婪着色算法，对于节点数为的网络，它的时间复杂度为。Schneider算法的时间复杂度与网络结构有关[14]，对树状网络来说是，但对规则网络是。

对于DEBC算法，最耗费时间的步骤是适应值的计算。适应值的计算分为两步：(1)对个体排序，(2)应用贪婪着色算法。因此，适应值计算的时间复杂度是。所以，DEBC算法总的计算复杂度为

其中，表示进化的最大代数，表示每一代中的个体数目。在进化算法中，每个个体可以独立计算适应度。因此，应用并行计算可以把计算时间减少到。

5 实验和结果

本小节中，为了展示DEBC算法的效果，我们将DEBC算法在5个基准网络上的结果和贪婪着色算法[10]及Schneider的盒子覆盖算法[14]进行比较。虽然我们只应用到无向无权的网络上，但DEBC算法能很容易地扩展到有向加权网络[20]。

5.1 基准网络

我们用5个结构不同的基准网络来展示DEBC算法不依赖网络结构。网络的基本属性如表1所示。首先，我们选择了广泛使用的E.coli生物网络，它有较小的聚类系数和高的模块度。

1. Escherichia coli网络(E.coli)：具有2859个蛋白质和6890个相互作用的蛋白质交互网络[21]。

为了展示DEBC算法在高聚合网络中的提高，我们选择了聚类无标度网络，它有较大的聚类系数和低的模块度。

1. 聚类无标度网络(CSF)：改进的Barabasi-Albert模型有高的聚合度[22]，选择的CSF网络有2003个节点和8000条边。

因为CSF网络有着低的模块度，我们也选择了如下3个聚合社区网络，这些社区网络都有着高模块度和大的聚类系数。

1. 政治书籍网络(polbooks)：关于美国政治的书籍网络有105本书和441条边，边表示两本书频繁的被相同的顾客购买。
2. 海豚网络(dolphin)：62条海豚所在社区的社交网络，边表示海豚之间的交互关系。
3. 美国足球联赛网络(football)：2000年赛季115个大学之间的足球联赛网络，节点代表大学足球队，边表示两个足球队之间进行比赛。

表1也展示了Schneider算法和DEBC算法与贪婪着色算法相比的平均提高。和就是在所有长度尺度上相对于贪婪着色算法的平均提高。结果表明，DEBC算法在所有基准网络的平均结果比Schneider算法好，特别是在聚集社区网络。

三个算法有不同的盒子定义：Schneider算法用半径来定义盒子，但是贪婪算法和DEBC算法用的是最短路径的最大值。虽然两种定义可以相互转换，但是基于半径的盒子比基于尺寸的盒子定义有更加严格的盒子限制。由于这个限制，Schneider算法在高聚类系数和高模块化的网络中容易陷入局部最优解，比如：政治书籍网络、海豚网络和美国足球联赛网络。因此，DEBC算法在不同种类网络中的稳定提高表明它不依赖网络结构。

5.2 结果分析

我们将展示式(1)中不同长度尺度下覆盖网络最少盒子数的结果。我们把DEBC算法的结果与贪婪算法和Schneider算法进行比较。我们关心DEBC算法相比贪婪算法的提高和Schneider算法相比贪婪算法的提高。

(1)E.coli网络和CFS网络的结果：对E.coli网络，如图3(a)所示，当时，Schneider算法和DEBC算法都比贪婪算法有显著提高，除了当时，Schneider算法甚至比贪婪算法更差一点。当时，DEBC算法比Schneider算法有轻微改善。对SCF网络，如图3(b)所示，当时，Schneider算法和DEBC算法都比贪婪算法有显著提高，高达。当时，DEBC算法比Schneider 算法有轻微提高，当时，有的提高。

(2)聚集社区网络的结果：由于不同的盒子定义，我们发现Schneider算法在聚集社区网络中无法得到最优的结果。在这种情况下，DEBC算法比贪婪算法和Schneider算法都有显著的提高。我们选择了3个社区网络检验这三种算法：政治书籍网络、海豚网络和足球联赛网络。对于政治书籍网络，如图4(a)所示，当时，正如图所示，Schneider算法比贪婪算法更差，相反，当时，DEBC算法比贪婪算法有稳定的提高，高达。对于海豚网络，如图4(b)所示，当时，正如图所示，Schneider算法比贪婪算法更差，相反，当时，DEBC算法比贪婪算法有稳定的提高，高达。对于美国足球联赛网络，如图4(c)所示，从到，正如图所示，Schneider算法比贪婪算法更差，然而，当时，DEBC算法比贪婪算法有稳定的提高，高达。

5.3 讨论

有趣的是Schneider算法和DEBC算法的提高没有影响到网络的分形性。分形维数在可容忍的小范围里变化。对E.coli网络，分形维数从(贪婪算法)变到 (Schneider算法)和 (DEBC算法)。

我们的实验表明DEBC算法在很少的代数就收敛了。如图4(d)所示，我们从4个基准网络中挑出一个长度尺度，结果表明DEBC算法在70代以内就收敛了。受搜索空间大小的影响，DEBC算法的收敛速率和成反比，也就意味着越大

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[138413]，资料为PDF文档或Word文档，PDF文档可免费转换为Word