计算机工程 ›› 2012, Vol. 38 ›› Issue (3): 265-266,269.doi: 10.3969/j.issn.1000-3428.2012.03.087

• 开发研究与设计技术 • 上一篇    下一篇

基于二部图的公共交通网络模型

卢鹏丽,贾春旭,沈万里   

  1. (兰州理工大学计算机与通信学院,兰州 730050)
  • 收稿日期:2011-08-19 出版日期:2012-02-05 发布日期:2012-02-05
  • 作者简介:卢鹏丽(1973-),女,副教授、博士,主研方向:算法设计与分析,图论,复杂网络;贾春旭、沈万里,硕士研究生
  • 基金项目:
    甘肃省自然科学基金资助项目(0809RJZA017);兰州理工大学校基金资助项目(0914ZX136)

Public Transport Network Model Based on Bipartite Graph

LU Peng-li, JIA Chun-xu, SHEN Wan-li   

  1. (School of Computer and Communication, Lanzhou University of Technology, Lanzhou 730050, China)
  • Received:2011-08-19 Online:2012-02-05 Published:2012-02-05

摘要: 利用现有方法对兰州市公共交通网络进行建模时,不能得到真实网络参数,或复杂度过高。为此,以二部图作为基本模型,将车次作为“上集”,站点作为“下集”,建立兰州市公共交通网络模型。计算并分析数据,验证其符合小世界特性和无标度网络,并利用 Laplacian特征值和最大连通子图相对值来分析网络的性能和连通情况。分析结果证明,该模型在减少网络存储空间的同时能保证计算结果的准确,且对其优化也较简单直观。

关键词: 复杂网络, 二部图, 公共交通网络, 无标度网络, 小世界, 网络故障

Abstract: Some of the modeling methods are not very suitable to establish the model of public transport network of Lanzhou for the reason that the real parameters of the network cannot be got or the method is with high self-complexity. A model based on bipartite graph is proposed, in which, the bus number as the “top set”, the station as the “bottom set”, public transport network model of Lanzhou is built. A lot of data are computed and analyzed, which indicates that this network fits with small-world and scale-free network, and analyzes the performance and connectivity with the maximum value of connected subgraph and Laplacian spectrum. Result proves that the use of bipartite graph to express, analyze and calculate the complex network not only guarantees the calculation result when the storage space drops relatively, but also seems direct-viewing and simple when optimizing the complex network on the bipartite graph.

Key words: complex network, bipartite graph, public transport network, scale-free network, small-world, network fault

中图分类号: