货运复杂网络拓扑结构优化原理、方法及工程实践

1相关研究及必要性

1.1复杂网络相关研究

1.1.1复杂网络的定义和分类

在数学上通常用图来表示一个网络，18世纪瑞士著名数学家Euler的哥尼斯堡七桥问题是最早开始对关于图的问题进行研究的。网络由节点和边组成，边表示不同节点之间的关系，网络T是节点集V和边集E的集合，即T={V，E〉。

复杂网络的定义有很多种，但一直没有一个精确、严格的科学定义。根据国内外的研究，复杂网络应包含以下三层意思：

（1）复杂网络由许多实际的复杂网络系统进行拓扑结构抽象转化而来；

（2）就表面来看复杂网络要比规则网络和随机网络复杂，同时由其生成具有真实系统统计特征的网络远远比生成规则网络和随机网络复杂；

（3）国内外学者认为复杂网络的研究有利于理解“复杂系统之所以复杂”的问题。

我国著名科学家钱学森给出了一种普遍应用的定义：具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络。复杂网络是一种特殊的网络，由大量节点和边组成。

方锦清科研小组经过深入研究对复杂网络进行了分类：

（1）现实网络大致分为社会网络、信息网络、技术网络和生物网络四种。

（2）根据网络的边有无权值，可将复杂网络划分为无权网络和加权网络。无权网络可以反映节点之间简单的连接方式和相互作用的最主要信息，但是不能描述节点之间相互作用强度的差异情形。加权网络则能够提供更加细致的刻画，不仅能够反映实际网络的拓扑结构，而且可以反映真实网络的动力学特征。

（3）根据节点度的分布特点，将复杂网络划分为指数网络和无尺度网络两大类。指数网络中的节点是同质的，它们的度大致相同，绝大部分节点的度都位于网络节点平均度附近，网络节点度分布随度数的增加呈指数衰减，因此网络中不存在度数特别大的节点。在无尺度网络中，大部分节点只与少数几个节点连接，但网络中存在少量度数特别大的节点，称为中心节点（或hub节点），它对无尺度网络的特性起着主导和支配作用。

（4）根据节点之间连边的方向性，将复杂网络分为无向网络和有向网络。无向网络的边不存在方向性，有向网络的边具有方向性，并且有所谓“出去”和“进来”的区别。有向网络中一个节点的度分布分为出度和入度。出度是指从该节点指向其他节点的边的数目，入度则是从其他节点指向该节点的边的数目。

（5）根据网络生成方式，将复杂网络分成随机性网络、确定性网络和混合网络。

随机性网络是按照随机方式生成的；确定性网络是按照确定方式生成的，其拓扑特性易于精确求解。然而，我们生活在确定性与随机性并存的和谐统一的真实世界，从文个基本非文出发，除了前面两种极端的生成方式，真实世界应该介于两者之间，是两者的和谐统一，由此便形成了混合网络。

1.1.2复杂网络的统计特征

复杂网络的统计特征是一种静态的统计指标，它是通过实际的拓扑网络结构抽象、实证研究后再经过统计计算而得到的统计指标。本书借鉴吴建军对复杂网络统计特征的研究，对度分布、平均路径长度、聚类系数和拥堵因子的定义进行介绍，之后对系统总费用和有效性的定义进行讨论。

1.度分布

节点的度k；表示节点i拥有边的数量，是衡量节点特性的重要的概念之一。一个节点的度越大，它在网络中的重要性越高。网络中所有节点的度的平均值称为网络的平均度，即为〈k〉。度分布即是所有节点的度的概率分布。累积度分布是指网络中节点的度大于k值的概率之和。

研究表明，复杂网络的拓扑结构性质以及复杂网络上的动力学行为等均紧密依赖于复杂网络的度分布。进一步说，由于复杂网络的无标度特性，复杂网络的度分布服从幂律分布，因而度分布完全由其幂指数[度分布指数（degree exponent）A]确定。

2.平均路径长度

平均路径长度L也称为网络的平均距离，指网络中所有节点对之间的平均最短距离。网络中两个节点和之间的距离d，定义为连接这两个节点的最短路径上的边数。对所有节点对的距离求平均值，可以得到网路的平均路径长度。该特征值描述了网络中节点的分离程度，体现的是网络的全局性质。

需要说明的是，网络中任意两个节点之间的最长距离称为网络的直径。

……