基于随机重叠派系的可控网络直径的公交网络模型的建立方法及公交网络模型

摘要

一种基于随机重叠派系的可控网络直径的公交网络模型的建立方法，将公交网络表示成站点和线路(即派系，网络中的最大完全子图)的关系，在数值表述时采用邻接矩阵表示网络关系图，包括以下步骤：设定网络直径为N；网络将从逻辑上表现为(N+1)层结构，其中第(m-1)层的派系映射为m层的一点(1≤m≤N+1)；原始网络由彼此重叠的派系组成，每次向原始网络中增加一个派系，与此同时保证每层网络都由派系组成，其中第(N-1)层网络将是一个派系，而网络的第N层是一个点；从而生成一个理想N深度派系网络；本发明在几乎零成本的情况下降低公交网络的最大换乘次数和降低平均换乘次数，可以提高公交系统的服务性能。

说明书

技术领域

本发明属于网络科学技术领域，具体涉及基于随机重叠派系的可控网络直径的公交网络模型的建模方法及公交网络模型。

背景技术

城市公共交通是与人们生活息息相关的重要基础设施，其基本任务是为乘客提供安全、方便、迅速、准点、舒适的乘车条件。然而，随着现代化的进程和城市化的发展，城市交通变得十分拥挤，城市公共交通并不能提供迅速、准点、方便的乘车条件。建设部提供的统计数据显示，我国公交出行分担率仅占城市居民总出行量的10％至25％，与发达国家40％到60％的出行比例相比，相差还很大，城市的公交系统没有发挥应有的优势，不利于我国经济的发展和城市文明的进步。因此，我国大力提倡优先发展城市公共交通，是提高交通资源利用效率，缓解交通拥堵的必要手段，是城市发展的根本之路。

目前，应用复杂网络理论对城市公交网络特性研究和网络规划的研究，开始引起人们的研究兴趣，有许多学者利用复杂网络理论对城市公交网络进行了研究，取得了大量的研究成果。Latora和Marchiopi(Latora V，Marchiori M.Is the Bostonsubway a small-world network[J].Physica A，2002，314(1-4)：109-113)研究了波士顿的地铁网络特性；Sienkiewicz(Sienkiewicz J，Holyst J A.Statistical analysis of 22public transport networks in Poland[J].Phys.Rev.E，2005，72(4)：046127)研究了波兰22个城市的公交系统，采用两种网络模型对其进行分析。吴建军、高自友等(WuJ J，Gao Z Y，Sun H J.Urban transit system as scale-free network[J].Modern PhysicsLetters B，2004，18(19-20)：1043-1049.)分析了北京市的公交网络的“无标度”特性及“小世界”特性，并研究了公交网络的效率问题。杨旭华、王波等(Yang XH，Wang B，Wang W L，et al.Research on some bus transport networks with randomoverlapping clique structure[J].Communications in theoretical physics，2008，50(5)：1249-1254.)通过对实际公交网(北京、上海和杭州)的统计特性的研究，提出space P描述下的公交网络是一个高度派系重叠、高度派系聚类、具有指数型度分布的小世界网络。

公交网络的设计和优化方面，很多研究者从网络的局部性能对公交线路进行优化，提出增加线路和站点等方法来改善公交网络的局部性能，提高网络局部效率，以缩短乘客出行时间，改善服务质量。

发明内容

为了克服现有的公交网络的优化效率较低、网络性能较差的不足，本发明提供一种优化运行效率高、网络性能良好、且不必增加成本的基于随机重叠派系的可控网络直径的公交网络模型的建立方法及公交网络模型，该模型可降低网络中乘客的最大和平均换乘次数。

本发明为解决上述技术所提出的技术方案：

一种基于随机重叠派系的网络直径可控的公交网络模型建立方法，将公交网络表示成站点和线路的关系，在数值表述时采用邻接矩阵表示网络关系图，所述公交网络模型建立方法包括以下步骤：

步骤1：设定网络直径为N，N为自然数；网络将从逻辑上表现为(N+1)层结构，其中第(m-1)层的派系映射为m层的一点，1≤m≤N+1，m为自然数；

步骤2：初始化每一层网络：初始的原始网络开始为一个派系c₀，c₀由m个节点构成，即初始有一个具有m个站点的公交线路；第1～N层网络为1个节点；

步骤3：向原始网络中新增一个派系，即增加一个大小为m的派系c_i，c_i中m₁个节点是从原始网络已有的节点中随机选取，m₂个为新增节点，其中，i＝1，2，…；

步骤4：若第k层有新派系出现，其中，0≤k≤N-2，将新增派系映射成第(k+1)层的一个节点，若该节点与某个已有的第(k+1)层派系构成新的最大派系，找出该派系，使它们组成新派系，这时第(k+1)层的派系数不变；否则从第(k+1)层的已有派系中找出一个包含该点的最大完全子图，即包含该点的最大派系，使它们与该节点构成第(k+1)层的一个新派系，这时第(k+1)层的派系数加1；

步骤5：对网络进行(N-1)次映射，若网络的第N-1层由一个派系构成，即得到理想N深度派系网络；

步骤6：若网络的第N-1层不能构成一个派系，在原始网络中，根据派系间的最大相似度选择相应的派系使其相互连接，保证第(N-1)层网络始终能成为一个派系。

步骤7：重复步骤3～步骤6，当所有的派系都加入到网络中，该网络为一个理想N深度派系网络，则结束。

进一步，所述步骤2和步骤3中，m～N(μ，σ²)，m₁～N(μ₁，σ₁²)，m₂～N(μ₁，σ₂²)，且μ＝μ₁+μ₂，m＝m₁+m₂，其中，m、m₁和m₂均为符合正态分布的随机数，m的均值和方差分别为μ和σ²，m₁的均值和方差分别为μ₁和σ₁²，m₂的均值和方差分别为μ₂和σ₂²。

再进一步，所述步骤4中，找出新节点所在派系的方法是，采用二分图描述网络，若一个派系的所有节点与这个新节点都相连，则该派系与新节点构成新派系。

更进一步，所述步骤6中，派系间的相似度是指两条派系间的公共节点数目，数目越多相似度越大。

更进一步，所述步骤7中，理想N深度派系网络从逻辑上表现为(N+1)层结构。原始网络由许多重叠的派系构成，定义原始网络为0深度派系网络；将原始网络中的派系映射成节点，若原始网络中的派系之间有重叠的节点，则认为其相应的映射节点有连边，这样组成一个新的网络，称之为1深度派系网络，按照本发明的设计，1深度派系网络也将由不同的彼此连接的派系组成；重复以上过程，即由m(0≤m≤N-1)层网络生成(m+1)层网络，第(N-1)层网络将是一个派系，而网络的第N层是一个点。这样我们得到一个逻辑上共有(N+1)层的网络。

一种用所述的基于随机重叠派系的网络直径可控的公交网络模型建立方法建立的公交网络模型，所述公交网络模型为：

(1)初始状态：已有一个长度为m的随机派系c₀；

(2)随机重叠派系增长：增加一个大小为m的派系c_i，c_i中m₁个节点是从原始网络中已有的节点中随机选取，m₂个为新增节点；

(3)理想N深度派系网络映射：进行一次理想N深度派系网络构建，若不能成为理想N深度派系网络，根据派系间的相似度，调节新增派系c_i的连接，使原始网络能成为理想N深度派系网络。

进一步，m～N(μ，σ²)，m₁～N(μ₁，σ₁²)，m₂～N(μ₂，σ₂²)并且μ＝μ₁+μ₂，m＝m₁+m₂，其中，m、m₁和m₂均为符合正态分布的随机数，m的均值和方差分别为μ和σ²，m₁的均值和方差分别为μ₁和σ₁²，m₂的均值和方差分别为μ₂和σ₂²。

再进一步，派系间的相似度是指两个派系之间的重叠节点的数目。

本发明的技术构思为：基于派系的复杂网络理论，从网络的拓扑结构和整体网络性能考虑，提出改善公交网络的模型或方法，来提升公交网络的整体服务性能。依据对公交乘客出行心理调查的统计结果，换乘次数最少是乘客出行时考虑的首要因素，其次是行驶距离、时间、费用等。换乘次数被看成公交网络性能的重要指标。所以说，设计出一种有更好网络性能的公交系统，具有更低的最大和平均换乘次数，是目前城市公交发展和优化的必要手段和方法。

基于随机重叠派系的复杂网络理论，提出了可控网络直径的公交网络模型，以降低网络直径和平均最短路径长度，从而降低公交网络中的最大换乘次数和平均换乘次数，提升公交网络的整体服务性能，使得公交系统能够分担更多的出行率，达到改善城市路网运行效率，缓解城市交通压力，并起到节能减排的功效。

本发明的基于随机重叠派系的可控网络直径的公交网络模型，是将理想N深度派系网络构建方法和一种基于加权复杂网络理论的公交网络演化模型结合起来，建立的一种网络直径可控(网络直径可预先假设为N)的基于随机重叠派系增长的公交网络演化模型。

按照Space P的方法，在公交网络模型中，将公交站点映射成公交网络中的点，若某两个站点之间至少有一条公交线路经过，则认为这两个点有连边。网络中的派系定义为网络中最大完全耦合子图，即派系中的所有节点是两两相连的。采用Space P的描述方法，对任意一条公交线路而言，其中任意两个公交站点之间都有连边，而且在整个公交网络中，不存在该条公交线路之外的一个点，可以和该条公交线路的所有站点都有连边，这就说明：每条公交线路是公交网络中的一个最大完全子图，即任一条公交线路可以看成一个派系。

网络中两节点的距离定义为连接这两个节点的最短路径上的边数，网络直径定义为网络中任意两节点之间距离的最大值，平均最短路径长度定义为网络中任意两节点之间的距离的平均值。对于公交网络，最大换乘次数为网络直径减1，平均换乘次数为平均最短路径长度减1。我国大中城市的公交网络的网络直径偏大，换乘次数较多，例如，北京、上海和杭州的网络直径分别为6、6和5。本发明就是基于降低网络直径和换乘次数的目的而设计的公交网络模型，本发明实现了网络直径为3的公交网络模型。

理想N深度派系网络的构建方法，首先给定N值，按照本构建方法，理想N深度派系网络将从逻辑上表现为(N+1)层结构。原始网络由许多重叠的派系构成，定义原始网络为0深度派系网络；将原始网络中的派系映射成节点，若原始网络中的派系之间有重叠的节点，则认为其相应的映射节点有连边，这样组成一个新的网络，称之为1深度派系网络，按照本发明的设计，1深度派系网络也将由不同的彼此连接的派系组成；重复以上过程，即由m(0≤m≤N-1)层网络生成(m+1)层网络，第(N-1)层网络将是一个派系，而网络的第N层是一个点。这样我们得到一个逻辑上共有(N+1)层的网络。

对每层来说，如果所有点都在某个派系中，而该层由若干个派系相互连接组成，则称之理想N深度派系网络。理想N深度派系网络的特点为，且每一深度网络都是派系构成，且对于某一层的网络[假设为k(1≤k≤N)深度]来说，网络任一个节点都对应原始网络中的一组节点，该组节点我们命名为k深度社团，按照我们所发明的模型，k深度社团其网络直径为k，因此，理想N深度派系网络中的原始网络直径为N。即我们可以按照预先设定好的网络直径，构造网络。如图1所示，是一个理想3深度派系网络的构建过程。

本发明的有益效果为：

(1)按照此模型设计的公交网络，不仅与实际的公交网络有非常近似的网络特性，而且还表现出新的特性。在满足公交覆盖率的情况下，此模型实现了网络直径可控(更小)和更小的平均最短路径长度，即在公交网络中实现最大换乘次数更小和平均换乘次数更小。此模型生成的具有更优的网络性能和服务质量的公交网络，可以使公交能够承担更多的出行分担率，最终达到改善城市路网运行效率，起到缓解城市交通压力的作用。

(2)此模型可以直接应用于实际的公交网络，对其进行优化。只需要调整少量的公交线路和站点，而不是增加线路和站点，在几乎零成本的情况下便降低公交网络的最大换乘次数和降低平均换乘次数，达到改善整体交通网络性能的效果，提高公交系统的服务质量。

附图说明

图1为理想3深度派系网络的构建过程示意图。

图2为理想N深度派系网络映射过程中奇异点的处理示意图。

具体实施方式

下面结合附图对本发明做进一步描述。

实施例1

参照图1和图2，一种基于随机重叠派系的可控网络直径的公交网络模型的建立方法，采用二分图表示公交网络，即将公交网络表示成站点和线路的关系，在数值表述时采用邻接矩阵表示网络关系图。具体建模步骤如下：

步骤1：设定网络直径为N，N为自然数；(对公交网络可假设为3)：网络将从逻辑上表现为(N+1)层结构，其中第(m-1)层的派系映射为m层的一点，1≤m≤N+1，m为自然数；

步骤2：初始化每一层网络。原始网络开始为一个派系c₀，c₀是由m个节点构成，即初始有一个具有m个站点的公交线路。第1～(N-1)深度网络为1个节点。

步骤3：向原始网络中新增一个派系(公交线路)，即增加一个大小为m的派系c_i，c_i中m₁个节点是从原始网络已有的节点中随机选取，m₂个为新增节点。(i＝1，2，…)

步骤4：若第k(0≤k≤N-2)层有新派系出现，将新增派系映射成第(k+1)层的一个节点，若该节点可以与某个已有的第(k+1)层派系构成新的最大派系，找出该派系，使它们组成新派系，这时第(k+1)层的派系数不变；如果不存在这样的派系，则从第(k+1)层的已有派系中找出一个包含该点的最大完全子图，即包含该点的最大派系，使它们与该节点构成第(k+1)层的一个新派系，这时第(k+1)层的派系数加1。

步骤5：按照步骤4，对网络进行(N-1)次映射。若网络的第(N-1)层构成一个派系，即可以映射成了理想N深度派系网络，进入步骤5，若不能，进入步骤6。

步骤6：若网络的第(N-1)层不能成为一个派系，如图2所示中黑实点，则在原始网络中，根据派系间的最大相似度选择相应的派系使其相互连接，保证第(N-1)层网络始终能成为一个派系。

步骤7：返回步骤3，若所有的派系都加入到网络中，而该网络是一个理想N深度派系网络，则结束。

上述步骤2和3中，m～N(μ，σ²)，m₁～N(μ₁，σ₁²)，m₂～N(μ₂，σ₂²)且μ＝μ₁+μ₂，m＝m₁+m₂，其中，m、m₁和m₂均为符合正态分布的随机数，m的均值和方差分别为μ和σ²，m₁的均值和方差分别为μ₁和σ₁²，m₂的均值和方差分别为μ₂和σ₂²。

上述步骤4中，找出新节点所在派系的方法是，在采用二分图描述网络的情况下，若一个派系的所有节点与这个新节点都相连，则该派系可与新节点构成新派系。

上述步骤6中，派系间的相似度是指两条派系间的公共节点数目，数目越多相似度越大。在对实际公交网络进行操作时，应考虑站点之间的距离，可以使用经纬度来计算。

所述步骤7中，理想N深度派系网络从逻辑上表现为(N+1)层结构，原始网络由许多重叠的派系构成，定义原始网络为0深度派系网络；将原始网络中的派系映射成节点，若原始网络中的派系之间有重叠的节点，则认为其相应的映射节点有连边，组成一个新的网络，称之为1深度派系网络，1深度派系网络也将由不同的彼此连接的派系组成；重复以上过程，即由m层网络生成(m+1)层网络，0≤m≤N-1，第(N-1)层网络将是一个派系，而网络的第N层是一个点，得到一个逻辑上共有(N+1)层的网络。

实施例2

参照图1和图2，公交网络模型为：

(1)初始状态：已有一个长度为m的派系c₀；

(2)随机重叠派系增长：增加一个长度为m的派系c_i，c_i中m₁个节点是从已有的节点中随机选取，m₂个为新增节点；

(3)理想N深度派系网络映射：进行一次理想N深度派系网络构建，若不能成为理想N深度派系网络，根据派系间的相似度，调节新增派系c_i的连接，使原始网络能成为理想N深度派系网络。

m～N(μ，σ²)，m₁～N(μ₁，σ₁²)，m₂～N(μ₂，σ₂²)并且μ＝μ₁+μ₂，其中，m、m₁和m₂均为符合正态分布的随机数，m的均值和方差分别为μ和σ²，m₁的均值和方差分别为μ₁和σ₁²，m₂的均值和方差分别为μ₂和σ₂²。派系间的相似度是指两个派系之间的重叠节点的数目。在对实际公交网络中操作时，还要考虑站点之间的距离，可用经纬度来计算。