文摘

优化平均路径长度(APL)通过添加快捷方式边缘被广泛讨论与社交网络,但网络直径之间的关系和APL通常忽略在APL的动态优化。在本文中,我们分析这种关系和优化APL的问题转化为减少直径为2的问题。我们提出一个基于一个迷因算法的数学模型。实验结果表明,我们的算法可以有效地解决这一问题以及优化APL。

1。介绍

后小世界模型和无标度网络的引入,许多研究已经致力于分析网络特性(1- - - - - -5]。特别是,有重点发现网络结构等指标量化的特性结构熵、健壮性、或模块化6- - - - - -8]。这些指标发挥重要作用在测量特定网络的性能方面,并优化可以帮助改善网络性能。

平均路径长度(APL),平均网络中所有节点之间最短的距离,不仅是一种测量等静态特征的连通性和健壮性也是一个重要的控制变量在动态过程中,如疾病的传播或目标搜索(9- - - - - -11]。优化APL也吸引了结构优化领域的关注。减少APL通过调整节点或边缘可以有效地提高传输效率和同步能力(12- - - - - -17]。此外,优化APL也被广泛应用于城市规划和选址14,18,19]。宣et al。20.)提出了一种模拟退火模型优化APL为了加速收敛。克伦(21)采用光谱技术来减少APL二元决策图。

为了优化APL,许多学者关注添加一个给定数量的边缘产生APL最大的减少。这些添加的边缘被称为“快捷方式”边缘和发现的问题的最佳设置快捷方式边缘被定义为“shortcut-selection”问题[22]。提出了一系列的方法来解决这个问题。安德森和Tagiku提出一个近似方法,该方法涉及寻找源节点,然后连接其他节点,这个节点减少APL (22]。Parotsidis等人分析的一个边缘插入对APL的影响并提出了EdgeEffect算法最大化边缘插入的效果(23]。贪婪算法,增加了边缘,这使得APL的最大减少为每个添加边缘,已经证明是有效的(24,25]。这些方法在一定程度上解决了shortcut-selection问题。然而,一种普遍现象在添加边缘的过程被忽视了。在实验中优化APL通过添加边缘,我们发现无论哪种方法用于添加边缘,总是存在一个转折点,APL开始减少线性边缘被添加。这种现象可以与网络直径有关。

在本文中,我们定义了网络直径在转折点“临界直径,并分析这个临界直径和APL的过程中添加边缘。我们将优化APL的问题转化为优化问题的临界直径。具体来说,我们关注添加快捷边缘的最小数量的网络直径减少到2。研究预测缺失链接近年来引起了人们广泛的关注,它的算法可以提取信息缺失或识别虚假的交互26- - - - - -29日]。高等人分析了预测网络的特性,他们发现网络直径和APL显示负线性关系的所有测试预测方法(29日]。因此,我们的研究也可以提供一些先验知识在设计链路预测的方法。在下一节中,我们介绍了临界直径和探索临界直径和APL之间的特殊关系;提出了临界直径的优化算法3;部分4给我们的测试方法结果生成的网络;我们的结论和进一步研究提出了部分5。

2。临界直径和APL

网络直径、最大路径长度为所有成对的节点,APL密切相关;他们都包含连接和信息传输效率(30.,31日]。Imase和伊藤给的不平等来描述网络直径之间的静态关系,,APL (32]。在边缘添加快捷方式的动态过程,存在一个转折点,如图1。APL非线性下降的边缘直到一个转折点然后减少线性进一步增加。我们计算每一对节点之间的路径长度,发现网络的最长路径长度大于2(即达到了转折点。、网络直径);当到达转折点,直径= 2 ()。这是因为如果一对节点之间,一个新添加的边缘只能改变这两个节点之间的路径长度从2比1,但不能改变其他的路径长度对节点,可以减少和APL而已为每个添加边缘,构成一个线性下降。

事实上,APL时可以计算网络直径下降2。对于一个网络与节点和边直径等于2时,每一对节点的路径长度等于或小于2。如果我们增加到网络边缘,对节点的路径长度等于1和的数量对节点的路径长度等于2。因此,APL通过增加的价值边的网络直径是

的过程中添加边缘,APL最终将减少线性和将成为等于右边的项(1)。图2显示了20添加边随机模拟的结果减少APL;最大的,意思是,和最小APL的20所示。三条曲线成为重叠和线性时添加边缘变得足够大的数量。最低APL的曲线变得线性最早,而最大的曲线APL是最后成为线性的。

在这种情况下,如果我们试图最小化APL通过添加大量快捷键的边缘,我们可以找到一个解决方案,添加少量的边缘已经减少直径2和随机加入剩下的边缘。因此,优化APL的问题可以转化为问题找到捷径的边缘,迅速降低直径2。

在这里,我们提出一个正式定义为直径当APL开始直线下降。

定义1。将边缘添加到网络中,网络直径下降2。网络直径在这种情况下的定义是“临界直径,”表示。

如果我们增加快捷边缘使网络直径,这些集快捷的边缘必须最小化APL通过添加最优的解决方案边缘。如果存在一个解决方案,可以使APL通过添加另一组低边缘,对节点的路径长度必须大于等于1通过添加唯一,无法意识到边缘。这种APL和之间的关系表明,如果我们可以减少添加边的数量减少直径APL,可以有效地降低到最低水平。

在本文中,我们专注于如何减少直径2通过添加最小数量的边缘;这个问题被定义为“优化临界直径。“目标函数可以作为制定 在哪里代表数量的边缘和补充道代表节点之间的路径长度和节点。

应该注意的是,临界直径的优化问题是一个np难问题。给定一个连接网络与节点和边缘,可以有添加的方法快捷的边缘。自从计算机网络直径至少成本,找到最佳的捷径边缘需要,这是高甚至对一个小型网络。

一种有效的方式来优化是建立最高学位节点和其他节点之间的连接,增加了边(节点和数量吗是网络的最高学位)。然后网络肯定会成为最高学位的星形网络节点的中心。我们调用这个方法“淬火”(连接到最高学位节点)。

然而,淬火未能生成全局最优的解决方案。如图36、节点的最高学位节点网络。减少淬火的直径为2,我们应该添加两条边连接节点3和6和节点4和6;但是如果我们之间建立一个连接节点3和4,网络直径也可以成为。因此我们需要设计一个更有效的方法来减少网络直径2。

3所示。该算法优化临界直径

迷因长途和短途搜索算法结合技术已被证明是有效地解决np难问题(33,34]。在本节中,我们介绍一个迷因算法结合遗传算法和启发式局部搜索优化临界直径。我们所说的方法“MA-CD。”

3.1。框架

MA-CD算法所示的框架1。我们第一次输入一些必要的参数,如最大迭代数量和人口规模以及网络的邻接矩阵。我们生成一个人口的函数。接下来,我们重复的过程优化直到迭代的数量,或者50个迭代的目标函数保持不变。在重复这一过程,我们首先使用选择亲本种群遗传操作;然后我们采用两点交叉和一点突变产生后代的染色体;我们应用一些先验知识进行本地搜索在后代的染色体;是用来构造一个新的人口与性能更好的染色体。最后,我们输出结果。

3.2。表示和初始化

我们的目标是找到那些我们应该添加在边缘优化。为此,我们发现所有这些不存在的边缘的位置和编码基因在染色体。是添加一个新的边缘到相应的位置,代表不添加一条边。图4显示了一个例子的表示。我们确定节点之间不存在边缘1 - 3、1 - 4、2 - 4、2 - 5、3 - 5。分配初始网络,所有的基因都是0,因为没有添加边缘。如果我们分配1到第一和第二基因染色体2所示,节点之间的边1 - 3和1 - 4将被添加。同样的,当我们分配1第一和第四基因之间的边缘1 - 3和2 - 5将被添加。

在初始化,我们生成一个人口的染色体和随机分配0或1每一个基因的染色体。

3.3。遗传操作

遗传操作由两点交叉和点突变。在附录中描述的交叉操作。给定两个父染色体和我们随机选择两个点,然后父染色体由两个选择的点分为三个部分。接下来,我们随机选择一部分,这一部分的基因之间的交换和的概率(交叉概率),生成两个后代染色体。突变也被描述在附录中,我们选择基因一些概率和重新分配到它。

3.4。本地搜索

通过加入一些先验知识,本地搜索可以有效地减少无用的探索,加快算法的收敛35]。我们找到最优网络似乎非选型实验优化APL,我们提出一个“disassortativeness-learning”技术应用这些知识到本地搜索。然后,我们使用“Edge-Adding学习”和“Edge-Dropping学习”找到的当地最低的解决方案。

3.4.1。Disassortativeness学习

在附录中描述的详细算法。我们首先找到的最低金额的添加边两个连接节点的度下降。然后我们发现不存在边缘已断开连接的两个节点之间的最大程度上的差异,并将这种新的边缘添加到网络。

3.4.2。Edge-Adding学习

如附录所述,我们首先判断更新网络的直径下降到2。如果直径超过2,我们随机添加边缘,直到直径= 2。然后我们输出的后代染色体与更新的网络直径等于2。

3.4.3。Edge-Dropping学习

我们选择每增加了边缘和检查是否添加的边缘将离开网络直径不变。如果不能增加直径下降,我们将添加优势;如果增加直径下降,我们不添加边缘下降。因此,一些无用的添加边可能会下降。附录给出了Edge-Dropping学习的具体过程。

3.5。复杂性分析

MA-CD的时间复杂度与网络规模,初始网络的边的数量,增加了边缘可以制定如下。每个迭代都需要次交叉和次突变,交配池的大小的遗传操作。因为计算网络直径成本遗传操作的总时间。本地搜索,当执行Disassortativeness学习,时间更新矩阵;发现添加的学位要求的最低金额;寻找不存在的优势最大程度上的差异需要。Disassortativeness学习的时间。执行Edge-Adding学习和Edge-Dropping学习,我们应该检查每个染色体的基因,它将花费最多计算更新后的一切都改变了基因的直径。因此,总体时间为每个迭代MA-CD的复杂性。

4所示。实验

在本节中,我们测试MA-CD的性能在不同的电脑网络。实验进行了一个2.40 GHz CPU、4.00 GB内存,10和Windows操作系统。我们用MATLAB来执行程序。表1显示了实验所需的参数。

我们的算法是进行十次在两个不同的网络结构:一个随机网络结构和普通的网络结构。两个网络结构的详细信息见附录。我们比较MA-CD的解决方案与其他两个方法:添加最高学位之间的边缘节点和其他节点中描述的部分2,表示为淬火;一种贪婪算法,增加了边缘一个接一个地添加了每个边缘的最小直径,标记成“GA-CD”(贪婪算法优化临界直径)。我们比较最低的最小值和平均值MA-CD淬火和GA-CD(这两个方法的最小值和平均值相等)。

相比于其他两种方法优化临界直径,MA-CD总是可以找到更少的边缘,使网络成为临界直径,直径,如图5。进一步,我们发现的结果MA-CD和淬火似乎成为一样的网络规模变大。换句话说,淬火的大网络优化变得更高效。MA-CD和淬火相比,GA-CD更差的性能优化,特别是对常规网络,即使减少APL的贪婪策略表现良好或直径23- - - - - -25]。

我们还表明,我们提出的方法可以有效地减少APL。计算最优网络的APLMA-CD快捷边缘添加的方法,然后这个APL是获得使用价格相比其他两种方法使用相同的号码边说:EdgeEffect算法,最大化的影响边缘插入优化APL (23),表示“EA-APL”;一个贪婪算法添加边一个接一个,每个增加边缘最小化APL,此前一直被证明是有效的(24),表示为“GA-APL。”

最优网络的APL图所示6。随机网络EA-APL表现更糟,而GA-APL成为常规网络效率较低。MA-CD提供了最佳性能;它可以减少APL的最低水平相比其他两种算法。因此,我们得出这样的结论:MA-CD可以用来优化APL。如果我们可以添加大量的边缘减少APL,我们只需要找到一个优化的解决方案然后随机加入剩下的边缘。

5。结论

在这篇文章中,我们找到一个关键的情况下的网络直径下降到2当一个新的边缘添加到网络解决shortcut-selection问题的过程中。使用APL和网络直径之间的关系,我们将优化APL的问题转换为这个问题寻找捷径的边缘快速减少直径2,我们定义为临界直径的优化问题。此外,我们建议一个方法基于一个迷因的算法来解决这个问题。实验结果表明,我们提出的方法可以有效地优化临界直径,是有效解决shortcut-selection问题减少APL。

附录

看算法2,3,4,5,6和表2。

的利益冲突

作者声明没有利益冲突有关的出版。

确认

这项工作是共同支持中国的国家社会科学基金重点项目(批准号12 azd110)和人文社会科学人才计划,中央大学基础研究基金(批准号2011 jdgz08)。