英语原文共 4 页，剩余内容已隐藏，支付完成后下载完整资料
译文：
最优交通网络
马克·巴泰勒米1,2和亚历山德罗·弗拉米尼1
1.信息学和生物复杂性中心学校，印第安那大学，艾根曼
大厅，1900东第十街，布卢明顿，47406
2.CEA研究中心，物理理论与运用部，91680，法国
(日期：2008年2月2日）
受到机场网络和物理网络的研究的启发，我们提出了一个一般加权网络模型的优化原理。最优网络拓扑原来是一个最大限度地减少了拓扑和度量数量的组合的生成树。它的特点是一个强烈的异构交通，是距离，交通和一个广泛分布的中心之间不平凡的相关性。在较小区域内分布的本地交通枢纽，优化的结果是一个清晰的空间分层组织。变参数的成本函数，不同类别的树木被回收，包括特定的最小生成树和最短路径树。这些结果表明，变化途径表示一个可选择的和可能是非常有意义的研究复杂的结构加权网络的路径。
PACS号码：89.75.-k, 89.75.Hc, 05.40 -a, 89.75.Fb, 87.23.Ge
交通和通信基础设施例如机场网络和物理互联网其特点是广泛分布的流量[ 1，2 ]，中介中心性[ 3 ]，并在某些情况下也是度[ 4 ]。强非线性的交通距离和交通连通性关系也有报道[ 1，2 ]。模块化的尝试，如随机成分权重，动态规则或权重拓扑耦合动力学（见例[ 2 ]）主要集中生长过程而变化途径主要是在实际问题中由道路交通工程师[ 5 ]使用。最优交通[ 6 ]网络问题和最佳网络[ 7 ]问题在数学和物理方面有悠久的传统。它是众所周知的，例如，在一个电阻网络中的电流的流动[ 8 ]规律可以由通过最小化的能量耗散网络[ 9 ]推导出来。另一方面，最佳网络已经被证明与哺乳动物的循环系统[ 10 ]，食品网[ 11 ]，一般运输网络[ 12 ]，代谢率[ 13 ]，河流网络[ 14 ]，和天然气管道或火车轨道[ 15 ]的研究有关。所有这些研究都得到一个事实，即网络节点的嵌入式在一个d维欧氏空间里，这意味着这个度几乎一直是有限的并且连接仅限于“邻居”之间。没有被空间约束的第二广的最优网络类最近也被调查了。它一直表明了，例如，优化的平均最短路径和总长度可以导致小世界网络[ 16 ]，并且更普遍的是，度的关联性[ 17 ]或者无标度特征[ 18 ]也源自一个优化的过程。坎乔和索尔[ 19 ]表示，平均最短路径和链接密度的最小化导致了多种网络，包括类指数图和无标度网络。吉梅拉等人[ 20 ]通过研究搜索成本最小的网络，发现了2类网络：星形网络和同构网络。最后，科利扎等人[ 21 ]通过研究路径最短，拥塞最小的网络，发现当每个节点的链接的数目被改变时，这种相互作用会导致多种网络。
本文的主要灵感来自于机场的网络[ 1,4 ]，我们调查的最重要的情况是节点被潜入在一个2维平面内，但连线并没有被限制（如空中航线）去连接“邻居”。
我们提出了一个同时取决于长度和链接带来的交通量的成本函数，并显示得到的最优网络在空间上是一个分层组织，并且显示出一个复杂的交通结构。我们考虑一组n个点（“飞机场”）随机分布在整块面积的正方形上，并且想建立一个网络（航线），连接所有的点。与连接线(i,j)相关的旅游费用或者负担wij是由连接线的长度dij和交通带来的tij共同作用的。在飞机网络的类比中，数量tij代表连线线（i,j)上的乘客数量并且具有对称性，tij=tji。从一个通用的节点i0沿一条特定的路径{i0,i1,i2,...,ip-1,ip}移动到另一个通用节点ip，其要付的成本是组成这条路径的所有连接线相关的权值wk,wk 1之和。当有多条路径可供选择的时候，我们认为，最经济的一种选择是所有属于从io到ip的路径组P(i0,ip)的路径p的最小值（we是边e的权重)。如果一对节点之间没有路径，相应的成本将被视为等于无限。这个选择确保最佳网络被连接。我们希望最小化的全球量ε0是从一个普通节点移动到另一个节点的平均成本。我们的目的是找到连接线的移动｛tij｝并且把只有唯一约束及对所有tij ge;0，总流量T=sum;ilt;j tij固定这样的移动进行最小化。在本文中，我们选择一条连接线e的权重为它的长度与运输量的比值：we=de/te
(在这个选择情况下，T的值固定了流量的规模并且不会影响最优网络的拓扑结构，因为一个常数因子的总能量的尺度改变不会影响最小化[ 22 ]。虽然这个选择不是最普遍的，但它自然地验证了预期，及权重随dij增加而增加，随tij的增加而减少。这最后一个条件在交通网络上可以很容易地被理解，这意味着在有大流量的连接线上移动更加经济，减少了连接线的有效距离或边际成本。我们寻找使用零度的大都市算法的最小实现流量。基本的移动包括移动一个随机分数的从一条连接线到另一条连接线产生的流量（总流量是固定的）。我们从随机两条连接线（i，j）和（irsquo;,jrsquo;）中选择并根据下式转化它们的权重，alpha;是0和1之间的一个均匀随机数。alpha;的符号有p的概率是正的，有1-p的概率是负的（如果其中一个连接的权重为零，转化只能在一个方向上进行，在其他情况下，p=0.5保证了快速会聚）。如果转化后一条连接线的权重为0，这条对应的连接线被删除了。两点之间的最小成本路径在Djikstra算法的每一步重新计算[ 7 ]。我们计算能量差∆ = ε0rsquo;- ε0，只有在这个值为负的情况下转化才能被接受。我们测试了一些次序的O(N2),即那些能收敛为最小能量为ε0的最优网络的。初始拓扑是一个在连接上有着随机权重的完整图形。正如我们下面显示的最佳解决方法，其特点是一个非平凡的拓扑结构和空间组织，其结果是两个对立力量的妥协：对短路径的需求和尽可能少的路径上的流量集中。拓扑和流量之间的相互作用，自然地引起了观测到度，距离和流量本身的相关性。
数值模拟表明，最优网络是一棵树。一个简单的支持这个发现的例子是从考虑一个等腰三角形ABC得出的，三角形的d(A, C) = d(B, C) = d 且 d(A, B) = drsquo;,最优化后得到当d＞＞drsquo;时值tAC=tBCasymp;T/2且tABasymp;0。最小能量是这样（在d为优先次序时），ε0asymp;d/tAC d/tBCasymp;4d/T 。当我们移除连接线BC，这样消灭了循环，AC上的流量大约变成了两倍高，即，tACasymp;T(tBCasymp;tABasymp;0)，但优先次序的最小能量是ε0rsquo;asymp;2d/tACasymp;2d/T且比ε小。这个例子表明，优化减少了在同一区域上连接节点的连接线的数量，并增加了剩余的连接线上的流量。在同一邻域上的节点间的循环便成了多余的。
优化网络是一棵极大地简化了能量的计算的树。由于一棵树上的两个节点只有唯一的一条路径存在，能量（2）可以被重写成ε0=sum;eisin;Tbe*de/te，这里的be是个边界数[ 23 ]并且记录了e属于两个节点间的最短路径的次数。最佳流量（与上述相同的约束）是由te=Tradic;bede/sum;eradic;bede给出的，最优交通树（OTT）的拓扑结构可以通过最小化获得。最小结构现在可以通过重新接线连接来找到。用连接线（i，jrsquo;）替换（i，j）只会改变j与jrsquo;之间路径的集中性，这说明我们的计算的复杂度为O(N)并且允许在非常大的网络上计算（同样的算法被使用在河流网络的背景下[ 24 ]）。我们希望得到一些与经典（欧几里德）最小生成树（MST）[ 7 ]非常不同的东西，因为ε包括度量（距离）与拓扑（中间性）数量。表达公式（5）通过优化给出了一个非常有趣的规律，mu;和upsilon;控制距离对拓扑结构的相对重要性作为衡量的中心。图一显示了不同的(mu;,upsilon;)的值会产生的生成树的例子。
图一：在<em 剩余内容已隐藏，支付完成后下载完整资料</em
资料编号：[147703]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
