October 6, 2004 14:55 WSPC/147-MPLB
00758
Modern Physics Letters B, Vol. 18, Nos. 19 & 20 (2004) 1043–1049 c World Scientific Publishing Company
URBAN TRANSIT SYSTEM AS A SCALE-FREE NETWORK
JIANJUN WU∗ , ZIYOU GAO and HUIJUN SUN School of Traffic and Transportation, Beijing Jiaotong University, Beijing, 100044, China ∗
[email protected] HAIJUN HUANG School of Economics and Management, Beijing University of Aeronautics and Astronautics, Beijing, 100083, China
Received 13 August 2004 Many systems can be represented by networks as a set of nodes joined together by links indicating interaction. Recently studies have suggested that a lot of real networks are scale-free, such as the WWW, social networks, etc. In this paper, discoveries of scale-free characteristics are reported on the network constructed from the real urban transit system data in Beijing. It is shown that the connectivity distribution of the transit network decays as a power-law, and the exponent λ is about equal to 2.24 from the simulation graph. Based on the scale-free network topology structure of the transit network, if only transit “hub nodes” are controlled well, the transit network can resist random failures (such as traffic congestion, traffic accidents, etc.) successfully. Keywords: Urban transit network; scale-free network; degree distribution.
1. Introduction Complex networks such as the World Wide Web or social networks often do not have an engineered architecture but instead are self-organized by the actions of a large number of individuals. From these local interactions, nontrivial global phenomena can emerge as, for example, small world properties1 or a scale-free distribution of the degree.2 In small world networks, short paths between almost any two sites exist even though nodes are highly clustered like in a regular lattice. Scale-free networks are characterized by a power-law distribution of a node’s degree, defined as the number of its next neighbors, meaning that structure and dynamics of the network are strongly affected by nodes with a great number of connections. Barab´ asi and Albert2 demonstrated that the probability [p(k)] that a vertex in the network is connected to k other vertices decays as a power-law (or the fraction of nodes in the ∗ Corresponding
author. 1043
October 6, 2004 14:55 WSPC/147-MPLB
1044
00758
J. Wu et al.
network that have degree k), following p(k) ∼ k −λ . The exponent λ is scattered between the range of 2.1 and 3. These global properties have considerable implications on the behavior of the scale-free network under error or attack,3 when random or highly connected nodes are destroyed, as well as on the spreading of information or epidemics.4 – 6 The highly connected “hub” nodes of a scale-free network and the short paths in a strongly clustered small world greatly facilitate the propagation of an infection over the whole network, which has to be taken into account for designing effective vaccination strategies.7– 9 Scale-free networks are remarkably resistant to accidental failures, a property that is rooted in their inhomogeneous topology. The random removal of nodes result in the removal of mainly small ones since they are much more plentiful than hubs. The elimination of these small nodes will not disrupt the network topology significantly since they contain few links, unlike hubs which connect to nearly everything. However, the reliance on hubs has a serious drawback, new method to study the real networks. Here, we report that networks composed of sites connected by that is, vulnerability to attacks. new method to study real networks. Here, we reportnetworks. that networks composed of sites connected Urban transit system’s scale-free by features transit routes showofthe the of scale-free Because its characteristics remarkable resistance to random failure, the scale-free network Urban transit system’s scale-free features transit routes show the characteristics of scale-free networks. theory new method study real networks. Here, we report networks help find andprovides control atransit hubs. Ittoalso indicates that urban transit systemthat is difficult to be destroyed composed of sites connected by transit routes show the characteristics of scale-free help find and control transit hubs. It also indicates that urban transit system is difficult to be destroyedFirstly, for the non-hubs’ congestions or accidents, even breakdown. This paper is organized as follows. networks. The scale-free features of the urban transit system help find and control forWe thepropose non-hubs’ accidents, evenofbreakdown. paper is organized Firstly, thecongestions scale-freeorcharacteristics the urban This transit network basedasonfollows. Barabasi’s theory. transit hubs. They also indicate that the urban transit system is not easily destroyed We propose the scale-free characteristics of the urban transit network based on Barabasi’s theory. Secondly, data analysis and results with real city data are contained in section 2. Finally, the conclusion by non-hub congestions, accidents, or even breakdowns. Secondly, data analysis and results with real city data are contained in section 2. Finally, the conclusion is given. This paper is organized as follows. First, we propose the scale-free characteristics is given. of the urban transit network based on Barab´ 1 Urban transit network’s scale-free property asi’s theory. Next, in Sec. 3 we provide data analysis and results withproperty real city data. Finally, we end this paper with our 1 Urban transit network’s scale-free 1.1conclusions. Describe of the transit network 1.1 Describe of the transit network
Urban transit network is a complex network, in which nodes can be seen as transit sites and edges Urban transit network is a complex network, in which nodes can be seen as transit sites and edges correspond to routes linked between In addition, if a route is designed from node i to node j , 2. Scale-Free Properties of O-D. the Urban Transit correspond to routes linked between O-D. In addition, if a route Network is designed from node i to node j , there must exist a route from node j to node i as shown in Fig.1 (a) (Because the full data is 2.1. Description of the transit network there must exist a route from node j to node i as shown in Fig.1 (a) (Because the full data is difficult to be obtained and the urban transit network is quite complex, we don’t consider effects of urban transit is transit a complex network, in complex, which nodes can be seen as difficultThe to be obtained andnetwork the urban network is quite we don’t consider effects of middle stopssites between the origin node andtothe destination node in O–D. this paper.). In some some transit and edges corresponding routes linked between In addition, if case, middle stops between the origin node and the destination node in this paper.). In some case, some route ispassing designedthrough from node i toi node j, theretomust exist a route from j in to urban transit and going the node loops transitaroutes routespassing node i construct going to nodenode the loops in urban transit transit through node i and i construct node i as shown in Fig. 1(a). (As the full data is difficult to be obtained and the network such as Fig.1 (b). Fig. 2 is a small example of the urban transit network with eight networkurban such as Fig.1 network (b). Fig. 2isisquite a small examplewe of the transit network withof eight transittransit sites, sites, transit complex, do urban not consider the effects middle routes and loop. A transit route represents the interaction of transit two transit tenten routes and oneone loop. A transit route represents the interaction of two sites. sites.
i i
j (a) (a)(a)
j
i
i (b) (b)
(b)
Fig.1 Examples of transit connections (Because the data full data is difficult be the obtained theand urban Fig.1 Examples transit sitesite connections (Because the full is difficult to be to obtained and theand urban transit network is quite is quite Fig. 1. of Examples of transit site connections. (The circle represents transit site thetransit line network represents the transit route.) (a) The connection of two nodes. (b) Single node connection struccomplex, wewe don’t consider effects of middle stopsstops between the origin node node and the node innode this in paper.) (The circle complex, don’t consider effects of middle between the origin anddestination the destination this paper.) (The circle turing a loop with itself. represents thethe transit sitesite andand the the lineline represents the transit route)route) (a) The of twoofnodes. (b) Single node connection represents transit represents the transit (a) connection The connection two nodes. (b) Single node connection with itself structuring a loop. with itself structuring a loop.
Transit site site Transit Transit route route Transit
October 6, 2004 14:55 WSPC/147-MPLB
i
j
(a)
00758i
(b)
Fig.1 Examples of transit site connections (Because the full data is difficult to be obtained and the urban transit network is quite complex, we don’t consider effects of middle stops between the origin node and the destination node in this paper.) (The circle Urban Transit System asnodes. a Scale-Free Network 1045 represents the transit site and the line represents the transit route) (a) The connection of two (b) Single node connection
with itself structuring a loop.
Transit site Transit route
Fig.2 Fig. A small of urbanoftransit network withnetwork eight transit routessites, and one 2. Aexample small example an urban transit withsites, eightten transit ten loop. routes and one
1.2 Properties ofloop. the transit network Barabasi and Bonabeau (2003)thehad usednode computer to show that a stops between origin and thesimulations destinationand nodecalculations in this paper.) In some growing network with attachment will indeed become its distribution cases,preferential some transit routes passing through node i scale-free, and going with to node i construct of loops in Although urban transit as Fig. 1(b). Figure is a small nodes following a the power law. this networks theoreticalsuch model is simplistic and2needs to beexample adapted to of the urban transit network with eight transit sites, ten routes and one loop. A
specific situations,transit it does appear to confirm our explanation forwhy scale-free networks are so route represents the interaction of two transit sites. ubiquitous in the real world. The key elements in previous scale-free network growth models, such as 2.2.ofProperties of the transit network models of the growth the World-Wide Web, are (1) continual addition of both vertices and edges to 10 the network as time passes, andBonabeau (2) preferential attachment, meaningand thatcalculations edges are to more Barab´ asi and used computer simulations showlikely that to
network with preferential willcharacteristics, indeed becomesuch scale-free, with of connect to verticesaofgrowing high degree than to ones of low attachment degree. Other as removal its distribution of nodes following a power-law. Although this theoretical model is
vertices or edges, or movement of edges to new positions in the network, can also be incorporated, but simplistic and needs to be adapted to specific situations, it does appear to confirm the crucial featuresourofexplanation power-lawfor degree distributions and are correlations between degrees why scale-free networks so ubiquitous in thevertex real world. The are keythe elements in previous scale-free network growth models, such as models of the reproduced with only elements 1 and 2 above. growth of the World Wide Web, are:
1. The continual addition of both vertices and edges to the network as time passes, 2 and 2. Preferential attachment, meaning that edges are more likely to connect to vertices of high degrees than to ones of low degrees. Other characteristics, such as the removal of vertices or edges, or the movement of edges to new positions in the network can also be incorporated. However, the crucial features of power-law degree distributions and correlations between vertex degrees are reproduced with only elements 1 and 2 above. Through observation and experimental data analysis, urban transit networks are found to possess three characteristics. They are as follows: 1. Growth. The growth characteristics of the urban transit network are similar to what has been mentioned above. New transit routes are added to urban transit networks at various times. For example, new habitation areas are developed in order to meet the demands of increasing traffic flows. City economy and tourist development create the possibility of transit network growth; old transit routes
October 6, 2004 14:55 WSPC/147-MPLB
1046
00758
J. Wu et al.
are removed from current urban transit networks. According to data from the website of BJSTATS (see Ref. 11), there were 11 urban transit routes in 1949; By observation and experiment data analysis, urban transit networks possess three characteristics as by 2002, the number had arrived at 776. follows: 2. Preferential attachment. In the urban transit network, there must exist a few Growth. Growth characteristic of the urban transit network are similar as mentioned above. New transit large transit sites. We name these sites “Transit Hubs” in this paper. Because routes are of course added into urban transit networks at times. For example, new habitation areas are “Transit Hubs” play a key role in urban transit networks, they are more attracborn in order to meet the increasing of traffic flows. City economy and tourist development bring the tive than general transit sites. When transit sites are chosen to connect to a new chance of transit network growth. Additionally, an old transit route is removed from the current urban transit site, there is a higher probability that these older transit sites are “Trantransit network. According to the data come from the web page of BJSTATS (See reference 11), urban sit Hubs”. In the urban transit network system, there are a few nodes which transit routes were 11 items in 1949. Compared with 2002, it had arrived 776. possesss a large number of routes. This accords with the real condition. Preferential attachment. In the urban transit network, there must exist a few large transit sites named 3. Clustering. most characteristic of urban transit is per“Transit Hubs”The in this paper.important Because of “Transit Hubs” playing a key role in urbannetworks transit networks, haps “clustering”, which is also known as “transitivity” in sociological literature. their attractiveness is larger than general transit sites. When choosing the transit sites to which the new Clustering is a measure of the to which the neighbors of a transit siteInare transit site connects, the probability thatextent a new transit site connects to “Transit Hubs” is also larger. linked totransit eachnetwork other,system, and it veryhave common in social networks. the urban fewisnodes a large number of routes, which also accords with the real condition. According to Barab´ asi’s theory, we know that an urban transit network with the Clustering. Perhaps most importantly, urban transit networks show “clustering”, also called above characteristics will eventually develop into a scale-free network. This result “transitivity” in the sociological literature. Clustering is a measure of the extent to which the neighbors can be proved by experiments based on real data of Beijing in the following section. of a transit site is also linked each other, and it is very common in social networks.
According to Barabasi’s theory, we can know that an urban transit network with above
3. Data Analysis andinto Results characteristics will develop a scale-free network finally. This result can be proved by experiments on the real data of Beijing in next section. Let based us consider the example of the urban transit network of Beijing as shown in 2 Data analysis and results Fig. 3. Figure 3(a) shows the transit network of Beijing while Fig. 3(b) shows the Let us consider the example of urban transit network of Beijing as shown in Fig.3. To the left of the corresponding connectivity graph. (Although the loops are not drawn in the graph, figure is the transit network of Beijing; while to the right is the corresponding connectivity graph we have calculated these data.) In our statistical data, although there are always (Although the loops are not drawn in the graph, we have calculated these data). In our statistic data, two routes in a pair of O–D, only one route is considered in our paper, since two although there are always two routes in a pair of O-D, only one route is considered in our paper, transit routes always overlap in real transit networks, as in Fig. 1(a), while Fig. 1(b) because two transit routes are always over-lap in real transit networks for Fig.1 (a). While for Fig.1 (b), is comprised of only one node and one route. it includes one node and one route.
Fig. 3. (a) Beijing(a) urban transit network. (b) Connectivity graph of (b) Beijing urban transit net3 (a) Beijing includes urban transit about network. 441 (b) Connectivity graph 776 of Beijing urban transitthick network. The graph includes about work. Fig. The graph nodes and links. The nodes possessing a 441 large number represent the transit nodesof andlinks 776 links. The thick nodes that have ahubs. large number of links represent the transit hubs. The derivation of the connectivity graph is based on the following transformation rule: named transit
3
Dong Zhi Men
32
BeiJing Zhan
October 6, 2004 14:55 Xi Zhi WSPC/147-MPLB Men 13
36
00758 YiHe Yuan
19
Dong Wu Yuan
15
Qian Men
15
BeiJing XiZhan
34
Si hui
15
The analysis is oriented to the study of the scale-free property. Fig.4 (a) shows a linear scale plot, where x and y axes represent the transit route connectivity and cumulative probability respectively. Urban Transit System as a Scale-Free Network 1047 We can observe that most transit nodes have a small connectivity (about 90% nodes of total 441 with Table 1. Main transit of Beijing. connectivity ranging from 1 to 5), while a few nodessites have a big connectivity (10% nodes with
connectivity ranging from 6hub to 36, in particular only one node hub with connectivity of 36). The log-log Transit Route number Transit Route number scale plot of urban transit network connectivity versus cumulative probability for the case of Beijing is Dong Zhi Men 32 Beijing Zhan 36 occurrences per19 cumulated connectivity shown in Fig.4 (b), where Xi Zhi Meny be the cumulative 13 probability Yihe of Yuan Wu Yuan 15 urban transit Qian network Men 15 power-law, and the the graph, we can see that follows the x . From Dong Beijing Xizhan 34 Si Hui 15 exponent λ is about equal to 2.24.
1.0 0.8 0.6 0.4 0.2 0
10
20
30
40
Log 10 (Cumulative probability)
Cumulative probability
rank
0.00
1.50
-0.5
-1.0
-1.5
Connectivity
(a)
1.00
0.50
Log 10 (Connectivity)
(a)
(b)
(b)
Fig. Linear 4. Linear scale plot and scaletransit plotnetwork of urban transit (a) network linear Fig.4 scale plot and log-log scalelog–log plot of urban connectivity. A linearconnectivity. scale plot, where(a)x Aand y
scale plot, where x and y axes represent transit route connectivity and cumulative probability for
axes routerespectively. connectivity and(b) cumulative probability for the Beijing,transit respectively. (b) The log-log scale the represent case of transit Beijing, The log–log scale plotcase of ofurban network connectivity
versus cumulative probability thecumulative case of probability Beijing. for the case of Beijing. plot of urban transit network connectivityfor versus
According to the scale-free topology structure analysis of the transit network, if only the “Transit
The of the is based the following transformation Hubs” arederivation controlled well, theconnectivity transit networkgraph can resist randomonfailures (such as traffic congestion, rule: named transit sites and their interactions give the transit nodes and links of the connectivity graph respectively. Eight4 main transit nodes form the main transit network structure of Beijing. [See Table 1. The data used is based on the website of BJBUS and other related websites-pages of Beijing (see Ref. 11).] We define the cumulative probability Pk as follows: Pk =
∞ X
Pk 0 ,
k0 =k
where k is defined as in Sec. 1. The analysis is oriented towards the study of the scale-free property. Figure 4(a) shows a linear scale plot, where the x and y axes represent the transit route connectivity and cumulative probability, respectively. We can observe that most transit nodes have a small connectivity (about 90% nodes of the total 441 with connectivity ranging from 1 to 5), while a few nodes have a great connectivity (10% nodes with connectivity ranging from 6 to 36, in particular one node with connectivity of 36). The log–log scale plot of urban transit network connectivity versus cumulative probability for the case of Beijing is shown in Fig. 4(b), where y is the cumulative probability of occurrences per cumulated connectivity rank x. From the graph, we can see that urban transit network follows the power-law, and that the exponent λ is approximately equal to 2.24.
October 6, 2004 14:55 WSPC/147-MPLB
1048
00758
J. Wu et al.
According to the scale-free topology structure analysis of the transit network, if only “Transit Hubs” are controlled well, the transit network can resist random failures (such as traffic congestion, traffic accidents, etc.) successfully. However, urban transit network is a very complex system. It is of worth noting that other network properties may exist in the urban transit network, and this will be our further research in the future. 4. Conclusion Scale-free networks have been studied recently. But there have been no attempts to solve the urban transit network problem using scale-free theory. In this paper, we study topology characteristics of the urban transit network for the first time. Growth and preferential attachment help the urban transit system to develop into a scale-free network; experimental data supports this result well for Beijing. Research in the urban transit network is useful for the management of bus companies. In addition, the result of this research helps to explain why the urban transit system is stable for a random route congestion or breakdown. However, the scale-free network has a serious drawback: vulnerability to attacks. The July 11 breakdown of the Beijing traffic system that was induced by rainstorm is a typical example. The transit network halted several hours because of the precipitate rainstorm. Therefore, the scale-free characteristics of the urban transit network should be considered in designing the transit routes. In this paper, we consider only non-stop urban transit networks and neglect the effects of middle stops between node of origin and the destination node. Additionally, all data used in this paper reflect the developed city transit networks. We cannot provide assurance that this theory is fit for undeveloped networks; other characteristics may exist in them and research in these networks will be our followup work. Acknowledgments The work described in this paper was partly supported by National Outstanding Young Investigator Grant (70225005) of National Natural Science Foundation of China, Teaching and Research Award Program for Outstanding Young Teachers (2001) in Higher Education Institutions of Ministry of Education, Social Science Foundation of China (02BJY094), Natural Science Foundation of Beijing (9042006), and School Foundation of Beijing Jiaotong University (2003SM32, 2003SM31). References 1. D. J. Watts and S. H. Strogatz, Collective dynamics of small-world networks, Nature (London) 393 (1998) 440–442. 2. A.-L. Barab´ asi and R. Albert, Emergence of scaling in random networks, Science 286 (1999) 509–512.
October 6, 2004 14:55 WSPC/147-MPLB
00758
Urban Transit System as a Scale-Free Network
1049
3. R. Albert, H. Jeong and A.-L. Barab´ asi, Error and attack tolerance of complex networks, Nature (London) 406 (2000) 378–382. 4. R. Pastor-Satorras and A. Vespignani, Epidemic spreading in scale-free networks, Phys. Rev. Lett. 86 (2001) 3200–3203. 5. R. Pastor-Satorras and A. Vespignani, Epidemic dynamics and endemic states in complex networks, Phys. Rev. E63 (2001) 066117. 6. S. Mossa, M. Barthelemy, H. E. Stanley and L. A. N. Amaral, Truncation of power law behavior in scale-free network models due to information filtering, Phys. Rev. Lett. 88 (2002) 138701. 7. M. E. J. Newman, Exact solutions of epidemic models on networks (2002), eprint arXiv:cond-mat/0201433. 8. R. Pastor-Satorras and A. Vespignani, Immunization of complex networks, Phys. Rev. E65 (2002) 036104. 9. Z. Dezso and A.-L. Barab´ asi, Halting viruses in scale-free networks, Phys. Rev. E65 (2002) 055103. 10. A.-L. Barab´ asi and E. Bonabeau, Scale-free networks, Scientific American 5 (2003) 60–69. 11. Data from http://www.cei.gov.cn and http://www.bjbus.com.
