摘要
城市交通运输系统是一个复杂的巨系统,随着经济的发展、城市规模的扩大,城市交通变得越来越拥堵,不但给城市居民的出行带来了很大的困扰,也影响了城市的发展。复杂网络研究的蓬勃兴起为交通运输的研究提供了新的视角,交通网络作为一种复杂网络,其拓扑结构的好坏直接影响网络的承载能力。人们逐渐认识到,交通网络拓扑结构对网络交通流量分布有重要的影响,网络交通流量的分布依赖于底层网络拓扑。因此,研究不同网络拓扑下的流量分布规律对研究交通运输系统流量分布有重要意义。
本文首先建立了不具有社区结构的相关性网络和具有社区结构的相关性网络,相关性网络包括正相关网络和负相关网络。对所构建的网络进行流量加载,然后按照用户平衡的方式达到平衡,对不具有社区结构的正、负相关性网络与不相关网络的流量分布和拥堵情况作比较,得出不相关网络的阻塞小于相关性网络；对于具有社区结构的网络也进行相同的比较,得出负相关网络的拥堵最小。研究说明网络的相关性对网络流量分布起着重要影响,这为我们规划、设计、改造交通网络提供指导。其次,本文对上述网络进行了级联失效研究。结果表明不具有社区结构的不相关网络能够更好的抵抗级联失效,而具有社区结构的负相关网络能够更好的抵御级联失效的影响。
最后,本文提取了北京市的主要骨架路网,对路网进行了分析,结果表明北京市路网具有明显的负相关结构,具有14个社区。用户平衡配流的结果表明,一些主要路段随着流量的增加容易发生拥堵。这些路段是影响整个路网性能的关键路段,增加这些路段的承载能力可以有效的增加整个网络的性能。
Urban transportation system is a complex giant system. With economic development, the expansion of the city, urban transport has become increasingly congested, which not only perplex urban residents to travel but also affect the development of city. The booming of the complex network research provides a new perspective for the study of transportation. As a complex network, urban road network topology directly impact on the carrying capacity of the network. People gradually realize that, the traffic network topology has important influence on the traffic flow distribution in the network and the traffic flow distribution depends on the underlying network topology. Therefore, studying the traffic flow distribution in different network topology is very meaningful.
Firstly, we established two types of correlated network: with community structure and without community structure. Correlated network consists of the assortative network and disassortative network. Through the comparison between assortative, disassortative and uncorrelated networks with and without communities, we can obtain the flow distribution on the networks. We found that the uncorrelated network without community is better to resist congestion than correlated ones without community, while the disassortative network with community is better than other networks with community. The result can be used in city network evaluation, planning, transformation.
Secondly, we study the cascading failure of the above mentioned network topologies. The studies of cascading failure on correlated networks show that the uncorrelated networks without community structure can be better to resist the cascading failure, however, the disassortative network with communities are better able to resist the cascading failure.
Finally, we extract the main skeleton of Beijing road network, through calculating and analysis, the result shows that the Beijing road network is a disassortative network and has14communities. User equilibrium assignment results show that some of the major road sections are prone to be congested. These sections are keys to impact the whole network property and enhance the capacity of these sections can effectively enhance the capacity of the whole network.
引文
[l]Erdos P, Renyi A. On the evolving of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Science, (1960) 5:17-61.
[2]Watts DJ, Strogatz SH. Collective dynamics of'small-world' networks[J]. Nature, (1998) 393, 440-442.
[3]Barabas AL, Albert R. Emergence of scaling in random networks [J]. Science, (1999) 286:509-512.
[4]Newman MEJ. Assortative mixing in networks [J].Phys Rev Lett, (2002) 89:208701-1-208701-4.
[5]Girvan M and Newman M E J. Community structure in social and biological networks [J]. Proc. Natl. Acad. Sci. USA (2002) 99,7821-7826.
[6]Barrat A, Barthelemy M, Pastor-Satorras R, Vespignani A. The architecture of complex weighted networks. Proceedings of the National Academy of Sciences USA, (2004) 101:3747-3752.
[7]Guimera R, Mossa S, Turtschi A, Amaral L A. The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles [J]. Proc. Natl. Acad. Sci.U S A. (2005) 102(22):7794-9.
[8]Porta S, Crucitti P, Latora V. The network analysis of urban streets: A dual approach [J]. Physica A, (2006) 369,853-866.
[9]Buhl J, Gautrais J, Reeves N, Sole RV, Valverde S, Kuntz P and Theraulaz G. Topological patterns in street networks of self-organized urban settlements [J]. Euro. Phys. J. B, (2006) 49, 513-522.
[10]Jiang B. A topological pattern of urban street networks: Universality and peculiarity. Physica A, (2007) 384,647-655.
[11]Subelj Land Bajec M. Robust network community detection using balanced propagation [J]. Eur. Phys. J. B, (2011) 81,353-362.
[12]Sienkiewicz J, Holyst JA. Public transport systems in Poland: from Bialystok to Zielona Gora by bus and tram using universal statistics of complex networks. Acta Physica Polonica B, (2005) 36, 1771.
[13]Sienkiewicz J, Holyst JA. Statistical analysis of 22 public transport networks in Poland. Phys.Rev.E, (2005) 72, 046127.
[14]王喆,彭其渊.成都市公交复杂网络拓扑特性研究.交通与计算机,(2007)25：39-42.
[15]吴建军,高自友,孙会君,赵晖.城市交通系统复杂性-复杂网络方法及其应用[M].科学出版社,北京,2010.
[16]Arenas A, Danon L,Guilera AD, Gleiser PM,Guimera R. Community analysis in social networks [J]. The European Physical Journal B, (2004) 38:373-380.
[17]赵金山,狄增如,王大辉.北京市公共汽车交通网络几何性质的实证研究[J].复杂系统与复杂性科学,(2005)2(2).
[18]May RM, Lloyd AL. Infection dynamics on scale-free networks [J]. Phys Rev E, (2001) 64:066112-1-066112-4.
[19]Moreno Y, Gomez JB, Pacheco AF. Epidemic incidence in correlated complex networks [J]. Phys Rev E, (2003) 68:035103-1-035103-4.
[20]Kitchovitch S, Lio P. Community Structure in Social Networks: Applications for Epidemiological Modelling [J]. PLOS ONE, (2011) 6(7):e22220.
[21]Liu ZH, Hu B B. Epidemic spreading in community networks [J]. Europhysics Letters, (2005) 72:315-321.
[22]Arenas A, Diaz-Guilera A, Kurths J, Moreno Y. Synchronization in complex networks [J]. Physics Reports, (2008) 469:93-153.
[23]Feng CF, Xu XJ, Wu ZX, Wang YH. Synchronization of coupled logistic maps on random community networks [J]. Chinese Physics B, (2008) 17(6):1951-1956.
[24]Sorrentino F, Di Bernardo M, Cuellar G, and Boccaletti S. Synchronization in weighted scale free networks with degree-degree correlation [J]. Physica D, (2006) 224, 123.
[25]Zhao L, Lai YC, Park K, Ye N. Onset of traffic congestion in complex networks [J]. Physical Review E, (2005) 71:026125.
[26]Shao J, Buldyrev SV, Braunstein LA, Havlin S, Stanley HE. Structure of shells in complex networks [J]. Phys Rev E, (2009) 80:036105-1-036105-13.
[27]Menche J, Valleriani A, Lipowsky R. Asymptotic properties of degree-correlated scale-free networks [J]. Phys Rev E, (2010) 81:046103-1-046103-11.
[28]Macri PA, Piontti ALPY, Braunstein LA. Reducing congestion on complex networks by dynamic relaxation processes [J]. Physica A, (2007) 386:776-779.
[29]Zhao L, Cupertino TH, Park k, Lai YC, Jin XG. Optimal structure of complex networks for minimizing traffic congestion [J]. CHAOS, (2007) 17,043103.
[30]Lacasa L, Cea M, Zanin M. Jamming transition in air transportation networks [J]. Physica A, (2009)388:3948-3954.
[31]Sun JT, Wang SJ, Huang ZG, Wang YH. Effect of degree correlations on networked traffic dynamics [J]. Physica A, (2009) 388:3244-3248.
[32]Xue YH, Wang J, Li L, He D, Hu B. Optimizing transport efficiency on scale-free networks through assortative or disassortative topology [J]. Phys Rev E, (2010) 81:037101-1-037101-4.
[33]Wu JJ, Gao ZY, Sun HJ, Huang HJ. Congestion in different topologies of traffic networks [J]. Europhys.Lett, (2006) 74, 560-566.
[34]Wu JJ, Sun HJ, Gao ZY. Dynamic urban traffic flow behavior on scale-free networks [J]. Physica A, (2008) 387:653-660.
[35]何大韧,刘宗华,汪秉宏.复杂系统与复杂网络[M].高等教育出版社,北京,2009.
[36]方建安,唐漾,苗清影,张益军,田恩刚.复杂网络控制系统动力学及其应用[M].科学出版社,2011.
[37]Crucitti P, Latora V, Marchiori M, Rapisarda A. Error and attack tolerance of complex networks. Nature, (2004) 406,378-382.
[38]Moreno Y, Gomez JB, Pacheco AF. Instability of scale free networks under node breaking avalanches [J]. Europhysics Letter, (2002) 58:630-636.
[39]Wu JJ, Gao ZY, Sun HJ. Cascade and breakdown in scale-free networks with community structure [J]. Physical Review E, (2006) 74:066111-066115.
[40]Motter AE, Lai YC. Cascade-based attacks on complex networks. Phys.Rev.E, (2002) 66,065102.
[41]Motter AE. Cascade control and defense in complex networks. Phys.Rev.Lett, (2004) 93, 098701.
[42]Crucitti P, Latora V and Marchiori M. Model for cascading failures in complex networks. Phys.Rev.E, (2004) 69,045104.
[43]Li CG, Maini PK.. An evolving network model with community structure [J]. Journal of Physics A, (2005) 38:9741-9749.
[44]Newman MEJ. Fast algorithm for detecting community structure in networks [J]. Phys.Rev.E, (2004) 69,066133.
[45]Lehmann J, Bernasconi J. Stochastic load-redistribution model for cascading failure propagation [J]. Phys.Rev.E, (2010) 81,031129.
[46]K6nig MD, Tessone CJ, Zenou Y. From assortative to disassortative networks: the role of capacity constraints [J]. ACS (2010) 13:483-499.
[47]史定华.网络度分布理论[M].高等教育出版社,2011,北京.
[48]Huang HJ, Lam WHK. Modeling and solving the dynamic user equilibrium route and departure time choice problem in network with queues [J]. Transportation Research-B, (2002) 36, 253-273.
[49]Wang WX, Wang BH, Hu B, Hu B, Yan G and Ou Q. General Dynamics of Topology and Traffic on Weighted Technological Networks. Phys.Rev.Lett, (2005) 94, 188702.
[50]Latora V. and Marchiori M. Efficient behavior of small-world networks. Phys. Rev.Lett, (2001) 87, 198701.
[51]Newman MEJ. Mixing patterns in networks. Phys Rev E, (2003) 67:026126-1-026126-13.
[52]邵春福.交通规划原理[M].中国铁道出版社(2010)
[53]Sheffi Y. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods [M], Prentice-Hall, Englewood Cliffs, (1985) NJ, USA.
[54]Zheng JF, Gao ZY, Zhao XM. Properties of transportation dynamics on scale-free networks [J]. Physica A, (2007) 373:837-844.
[55]Wu JJ, Sun HJ, Gao ZY. Cascading failures on weighted urban traffic equilibrium networks [J]. Physica A, (2007) 386:407-413.
[56]Capocci A, Caldarelli G,Rios PDL. Quantitative description and modeling of real networks [J]. Phys Rev E, (2003) 68:047101-1-047101-4.
[57]Satorras RP, Vazquez A, Vespignani A. Dynamical and correlation properties of the Internet [J]. Pyhs Rev Lett, (2001) 87:258701-1-258701-4.
[58]Maslov S, Snippen K. Specificity and stability in topology of protein networks [J]. Science, (2002)296:910-913.
[59]Bagler G. Analysis of the Airport Network of India as a complex weighted network [J]. Physica A, (2008)387:2972-2980.
[60]Noh JD. Percolation transition in networks with degree-degree correlation [J]. Phys. Rev. E, (2007)76,026116.
[61]Pastor-Satorras R, Vazquez A, and Vespignani A. Dynamical and Correlation Properties of the Internet [J]. Phys. Rev. Lett, (2001) 87,258701.
[62]苏伟忠,杨桂山,甄峰.基于无尺度结构的苏南乡镇公路网分析[J].地理研究,(2007)第26卷,第5期.
[63]Catanzaro M, Boguna M and Pastor-Satorras R. Generation of uncorrelated random scale-free networks [J]. Phys. Rev. E, (2005) 71, 027103.
[64]Bruner RX, Sokolov IM. Changing correlations in networks:assortativity and disortativity [J]. Acta Physica Polonica B, (2005) 36:1431-1455.
[65]Newman MEJ. Detecting community structure in networks [J]. Eur. phys.J. B, (2004) 38,321-330.
[66]Newman MEJ and Girvan M. Finding and evaluating community structure in networks [J]. Phys. Rev. E, (2003) 69,026113.
[67]Gibson D, Kleinberg J, Raghavan P. Inferring Web communities from link topology. Proceedings of the 9th ACM Conference on Hypertext and Hypermedia, (1998) 225-234.
[68]Flake G W, Lawrence S R, Giles C L, Coetzee F M. Self-organization and identification of Web communities [J]. IEEE Computer, (2002) 35:66-71.
[69]Shen Orr, Milo R, Mangan S, Alon U. Network motifs in the transcriptional regulation network of Escherichia coli [J]. Nature Genetics, (2002) 31:64.
[70]Milo R, Shen Orr, Itzkovitz S, Kashtan N, Chklovskii D, Alon U. Network motifs:Simple building blocks of complex networks [J]. Science, (2002) 298:824.
[71]Holme P, Huss M, Jeong H. Subnetwork hierarchies of biochemical pathways [J]. Bioinformatics, (2003) 19:532-538.
[72]Danon L, Arenas A and Diaz-Guilera A. Impact of community structure on information transfer. Phys.Rev.E, (2008) 77,036103.
[73]Liu ZH and Hu B. Epidemic spreading in community networks. Europhys.Lett., (2005) 72, 315-321.
[74]Zhou MY, Cai SM and Fu ZQ. Traffic dynamics in scale-free networks with tunable strength of community structure. Physica A, (2012) 391,1887-1893.
[75]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].清华大学出版社,(2006)北京.
[76]Kernighan BW, Lin S. A efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, (1970) 49:291~307.
[77]Pastore y piontti AL, Braunstein LA, Macri PA. Jamming in complex networks with degree correlation [J]. Phys Lett A, (2010) 374:4658-4663.
[78]Wang B and Kim BJ. A High Robustness and Low Cost Model for Cascading Failures [J]. Europhys.lett. (2007) 78 48001.
[79]Xu J and Wang X F. Cascading failures in scale-free coupled map lattices [J].Physica A, (2005) 349,685-692.
[80]Watts DJ. A simple model of global cascades on random networks [J].Proc.Natl.Acad. Sci.U.S.A. (2002)99,5766-5771.
[81]Bak P, Tang C, Wiesenfeld K. Self-organized criticality: An explanation of the 1/f noise [J]. Phys. Rev. Lett., (1987) 59:381-384.
[82]邵春福.北京市交通存在的问题分析[J].投资北京,(2002),9.