# The Analysis of the Properties of Bus Network Topology in Beijing Basing on Complex Networks

Authors: Hui Zhang; Peng Zhao; Jian Gao; Xiang-ming Yao
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

The transport network structure plays a crucial role in transport dynamics. To better understand the property of the bus network in big city and reasonably configure the bus lines and transfers, this paper seeks to take the bus network of Beijing as an example and mainly use space L and space P to analyze the network topology properties. The approach is applied to all the bus lines in Beijing which includes 722 lines and 5421 bus station. In the first phase of the approach, space L is used. The results show that the bus network of Beijing is a scale-free network and the degree of more than 99 percent of nodes is lower than 10. The results also show that the network is an assortative network with 46 communities. In a second phase, space P is used to analyze the property of transfer. The results show that the average transfer time of Beijing bus network which is 1.88 and 99.8 percent of arbitrary two pair nodes is reachable within 4 transfers.


---

## Body

## 1. Introduction

Complex networks have been successfully used in many real complex systems since the researches of small-world networks and scale-free networks [1, 2]. Many real complex systems have been well studied which include the actor network [1–3], WWW [2, 4], protein networks [5], and power grid [1, 3]. During the last few years, transport networks, such as subway network [6], airport network [7–9], and street network [10], have been studied by the complex approach.As an important part of urban transport systems and a trip mode to alleviate the traffic congestion, bus network has been studied by an increasingly large number of researchers. Sienkiewicz and Holyst studied the public transport in 22 Polish cities and found that the degree distribution of these network topologies followed a power law or an exponential function [11]. Xu et al. analyzed the three major cities of China, and they found that there is a linear behavior between strength and degree [12]. Soh et al. contribute a complex weighted network analysis of travel routes on the Singapore rail and bus transportation systems [13].In this paper, we investigate the Beijing bus network (BBN) with 722 lines and 5421 nodes. The data can be achieved from the Internet (http://www.mapbar.com/search/). In the network, the nodes stand for bus stations and edges (links) are the bus line connecting them along the route. In order to analyze the static properties of BBN, we use the so-called space L and space P to represent the BBN. The space L is mainly used to analyze the properties of degree distribution, cluster, the average shortest path, degree correlation, and community structure. The space P is mainly used to analyze the average transfer time.This paper is organized as follows. In Section2, we give the description of the construction of the network. Section 3 analyzes the main properties of the BBN with space L. In Section 4, we analyze the average transfer time of the BBN and use space P to calculate the smallest transfer times between any nodes in the network. Discussion and conclusions are given in Section 5.


## 2. The Construction of the Network

For easy calculation, there are some assumptions followed.(1)
The station name is the unique identification in the network. Do not account for the condition that some stations have identical names but different parking place.(2)
The stations have slight difference between upstream line and downstream line. In this paper, the construction of the undirected network is based on the stations of the upstream lines.(3)
This paper does not consider the number of links between two stations and the frequency of bus; that is, it does not consider the weight of the network.The bus network is usually represented by space L, space P [11], space B [14], space C [15]. This paper will study and the Beijing bus network based on space L and space P. Space L consists of nodes which stand for the bus stations and a link between two nodes exists if they are consecutive stops on the route. Space P is a link formed between any two nodes of a line. Figure 1 gives a schematic representation of space L and space P.Illustration of space L (a) and space P (b).
(a)
(b)


## 3. The Main Properties of the Beijing Bus Network under Space L

Here we represent network as a graphG=(V,E), where V is the set of nodes and E is the set of edges (links). G is described by the N×N adjacency matrix {eij}. If there exists an edge between nodes i andj, eij=1; otherwise eij=0. N is the number of nodes in the network. Figure 2 gives the Beijing bus network topology graph with 5421 nodes and 16986 links.Figure 2
The graph of Beijing bus network topology.


### 3.1. Degree

The degreeki of node i is defined as the number of nodes that connected with the node i, which reflects the importance of the node i. In this paper, it refers to the number of bus stations with direct bus connecting with the current bus station. After calculation, the largest degree of the BBN is 21, the smallest is 1, and the average degree of all nodes is 3.13 which means one station averagely connects 3-4 stations in Beijing bus network. Table 1 shows partly the bus stations of larger degree of BBN.Table 1
The stations of Beijing bus network with larger degree and the value of degree.
Serial number
Bus station
degree
1
Sanyuanqiao
21
2
Liu Li Qiao Dong
20
3
Beijing Xi station
19
4
Liu Li Qiao Bei Li
18
5
Beijing Zhangdong
16
6
Madian Qiao Xi
16
7
Xi Dao Kou
16
8
Chong Wen Men Xi
15
9
Guang An Men Nei
14
10
Zuo Jia Zhuang
14
11
Qianmen
14
12
Dabei Yao Nan
14
13
Tianqiao
13
14
Ma Dian Qiao Nan
13
15
Bei Tai Ping Qiao Xi
13
16
Si Hui station
13
17
Deshengmen
13
18
Xi Bei Wang
13
19
Xiyuan
13
20
Xin Fa Di Qiao Bei
13Here, we studied the proportion of the stations with the degree from 1 to 21. Figure3 shows the degree distribution of the stations in the BBN, and we found that it follows a shifted power law distributionf(k)=1.914*Γ(k)/Γ(k+2.47), k>2, k is the degree, and the number of stations with degree 1 accounts for 4.48%. It also shows that the degree of 99% of all station is smaller than 10.Figure 3
The degree distribution of Beijing bus network.


### 3.2. The Average Shortest Path

The average shortest path is the property to reflect the efficiency of information circulating on the network. It is defined asl=2*∑i>jdij/(N*(N-1)),  l is the average minimum shortest number of steps between all pairs of nodes, and dij is the shortest path between nodei and nodej.


### 3.3. Cluster Coefficient

Cluster coefficient is an important property of characterizing the local cohesiveness of the current node or the extent to which the nodes in the network are clustered together. In the BBN, clustering coefficient reflects the ease of the bus transport among the neighboring bus stations of the current one. It is defined asCi=Ai/(ki(ki-1)/2), where Ci is the cluster coefficient of nodei, Aiis the actual number of links between the neighbor nodes of the current node, and ki is the degree of node i. The cluster coefficient of the network isC=∑i∈GCi/N.


### 3.4. Efficiency

The efficiency is the property to characterize the capacity of traffic, and it can be calculated with the formulaE=2*∑i>j(1/dij)/(N*(N-1)), where dijis the shortest path between nodeiand nodej [16].


### 3.5. Degree Correlation

Degree correlation reflects the relationship between the degrees of nodes. Nodes with high degree tending to be connected with nodes with high degree are called assortativity. In contrast, nodes with high degree which have the tendency to be connected with low degree are called disassortativity. It can be calculated with the formula [17]
(1)r=M-1∑ijiki-[M-1∑i(1/2)(ji+ki)]2M-1∑i(1/2)(ji2+ki2)-[M-1∑i(1/2)(ji+ki)]2,
whereris correlation coefficient and jiandkiare the degrees of the nodes at the ends of theith links, with i=1,…,M.


### 3.6. The Community Structure

It is usually found that there are many communities in one complex network; within the community, there are many links, but between the communities, there are fewer links [18]. Newman and Girvan [19] gave a measure Qcalled modularity. For a division with g communities, then define a g×gmatrix e whose component eijis the fraction of edges in the original network that connects nodes in community ito those in communityj. The modularity is defined to beQ=∑ieii-∑ijkeijeki=Tre-∥e2∥, where ∥x∥indicates the sum of all elements of x. It can be achieved that0≤Q≤1. Q=0 indicates the community structure is not stronger than it would be expected by random chance. The larger the modularity is, the stronger the community structure is.Table2 shows the main properties of BBN. We can see that the average shortest path is 20.03, which means people can reach destination by averagely taking 20 stops, and it is obvious that the BBN exhibits a small-world property. The cluster coefficient of BBN is 0.142, which means the BBN is a sparse network. Furthermore, the correlated coefficient is 0.185, which validates the result in the paper [m6] that when the number of nodes is larger than 500, the network is usually assortative. In addition, the community structure of BBN is so obvious and the modularity is 0.905 with 46 communities.Table 2
The value of the main properties of Beijing bus network.
Network parameters
Value
Number of nodes (N)
5421
Number of links (A)
16986
Number of lines (L)
722
Average degree (Ak)
3.13
Average shortest path (l)
20.03
Cluster coefficient (C)
0.142
Efficiency (E)
0.066
Correlation coefficient (r)
0.185
Number of communities (Z)
46
Modularity (Q)
0.905


## 3.1. Degree

The degreeki of node i is defined as the number of nodes that connected with the node i, which reflects the importance of the node i. In this paper, it refers to the number of bus stations with direct bus connecting with the current bus station. After calculation, the largest degree of the BBN is 21, the smallest is 1, and the average degree of all nodes is 3.13 which means one station averagely connects 3-4 stations in Beijing bus network. Table 1 shows partly the bus stations of larger degree of BBN.Table 1
The stations of Beijing bus network with larger degree and the value of degree.
Serial number
Bus station
degree
1
Sanyuanqiao
21
2
Liu Li Qiao Dong
20
3
Beijing Xi station
19
4
Liu Li Qiao Bei Li
18
5
Beijing Zhangdong
16
6
Madian Qiao Xi
16
7
Xi Dao Kou
16
8
Chong Wen Men Xi
15
9
Guang An Men Nei
14
10
Zuo Jia Zhuang
14
11
Qianmen
14
12
Dabei Yao Nan
14
13
Tianqiao
13
14
Ma Dian Qiao Nan
13
15
Bei Tai Ping Qiao Xi
13
16
Si Hui station
13
17
Deshengmen
13
18
Xi Bei Wang
13
19
Xiyuan
13
20
Xin Fa Di Qiao Bei
13Here, we studied the proportion of the stations with the degree from 1 to 21. Figure3 shows the degree distribution of the stations in the BBN, and we found that it follows a shifted power law distributionf(k)=1.914*Γ(k)/Γ(k+2.47), k>2, k is the degree, and the number of stations with degree 1 accounts for 4.48%. It also shows that the degree of 99% of all station is smaller than 10.Figure 3
The degree distribution of Beijing bus network.


## 3.2. The Average Shortest Path

The average shortest path is the property to reflect the efficiency of information circulating on the network. It is defined asl=2*∑i>jdij/(N*(N-1)),  l is the average minimum shortest number of steps between all pairs of nodes, and dij is the shortest path between nodei and nodej.


## 3.3. Cluster Coefficient

Cluster coefficient is an important property of characterizing the local cohesiveness of the current node or the extent to which the nodes in the network are clustered together. In the BBN, clustering coefficient reflects the ease of the bus transport among the neighboring bus stations of the current one. It is defined asCi=Ai/(ki(ki-1)/2), where Ci is the cluster coefficient of nodei, Aiis the actual number of links between the neighbor nodes of the current node, and ki is the degree of node i. The cluster coefficient of the network isC=∑i∈GCi/N.


## 3.4. Efficiency

The efficiency is the property to characterize the capacity of traffic, and it can be calculated with the formulaE=2*∑i>j(1/dij)/(N*(N-1)), where dijis the shortest path between nodeiand nodej [16].


## 3.5. Degree Correlation

Degree correlation reflects the relationship between the degrees of nodes. Nodes with high degree tending to be connected with nodes with high degree are called assortativity. In contrast, nodes with high degree which have the tendency to be connected with low degree are called disassortativity. It can be calculated with the formula [17]
(1)r=M-1∑ijiki-[M-1∑i(1/2)(ji+ki)]2M-1∑i(1/2)(ji2+ki2)-[M-1∑i(1/2)(ji+ki)]2,
whereris correlation coefficient and jiandkiare the degrees of the nodes at the ends of theith links, with i=1,…,M.


## 3.6. The Community Structure

It is usually found that there are many communities in one complex network; within the community, there are many links, but between the communities, there are fewer links [18]. Newman and Girvan [19] gave a measure Qcalled modularity. For a division with g communities, then define a g×gmatrix e whose component eijis the fraction of edges in the original network that connects nodes in community ito those in communityj. The modularity is defined to beQ=∑ieii-∑ijkeijeki=Tre-∥e2∥, where ∥x∥indicates the sum of all elements of x. It can be achieved that0≤Q≤1. Q=0 indicates the community structure is not stronger than it would be expected by random chance. The larger the modularity is, the stronger the community structure is.Table2 shows the main properties of BBN. We can see that the average shortest path is 20.03, which means people can reach destination by averagely taking 20 stops, and it is obvious that the BBN exhibits a small-world property. The cluster coefficient of BBN is 0.142, which means the BBN is a sparse network. Furthermore, the correlated coefficient is 0.185, which validates the result in the paper [m6] that when the number of nodes is larger than 500, the network is usually assortative. In addition, the community structure of BBN is so obvious and the modularity is 0.905 with 46 communities.Table 2
The value of the main properties of Beijing bus network.
Network parameters
Value
Number of nodes (N)
5421
Number of links (A)
16986
Number of lines (L)
722
Average degree (Ak)
3.13
Average shortest path (l)
20.03
Cluster coefficient (C)
0.142
Efficiency (E)
0.066
Correlation coefficient (r)
0.185
Number of communities (Z)
46
Modularity (Q)
0.905


## 4. The Transfer Property of Beijing Bus Network under Space P

The transfer capacity is an important index to evaluate the performance of a bus network, and travelers always expect that they can reach the destination through the least number of transfers. In this paper, the average minimum transfer time is used to evaluate the performance of the transfer capacity. Usually, travelers cannot reach the destination without transfer for a long distance trip, and the minimum transfer time between any two nodes is specific. The average minimum transfer time is the average among all pair nodes.G
′
=
(
L
,
V
) is used to represent the specific bus network, whereL is the line,Vis the bus station, and G′is a L*N matrix{bij},bij=1if lineistops at stationj; otherwisebij=0.Table3 shows the specific network given in Figure 1. We can achieve the minimum transfer time using Table 3. For example, (1) searchV6→V7. Because there is no directed line between the node V6 andV6, it needs transfer. From Table 3, we can see that b16=b13=1 throughL1, and b23=b27=1 throughL2, so we can achieveV6→L1V3→L2V7; that is, travelers need transfer at V3from L1toL2. (2)SearchV10→V13. We can get the path V10→L2V3→L1V5→L3V13through two transfers.Table 3
The specific network of Figure1.
V
1
V
2
V
3
V
4
V
5
V
6
V
7
V
8
V
9
V
10
V
11
V
12
V
13
L
1
1
1
1
1
1
1
0
0
0
0
0
0
0
L
2
0
0
1
0
0
0
1
1
1
1
0
0
0
L
3
0
0
0
0
1
0
0
0
0
0
1
1
1Using the aforementioned method, we can get the minimum transfer time between any two nodes and calculate the average minimum transfer time. But it becomes very hard when the scale of network is becoming huge. In this paper, we use the space P to solve the problem. Firstly, we need to construct the network under space P, where the weight of the network is 1. Secondly, the Floyd algorithm is used to achieve the shortest path between any two nodes. The shortest path value is the minimum line number that needs to use and the transfer time is the needed line number minus 1. Figure4 gives the illustration of the aforementioned example. Figure 4(a) shows V6can reach V7by using the two dotted lines. Figure 4(b) shows V6can reach V7by using the three dotted lines.The illustration of transfer network under space P.
(a)
(b)Here, we study the BBN. Table4 shows the stations that have most lines. It is found that the station that owns most lines is San yuan qiao which has 47 lines.Table 4
The stations that have most line and the line numbers.
Serial number
Station
Line numbers
1
Sanyuanqiao
47
2
Liu Li Qiao Bei Li
40
3
Beijing Xi Zhan
39
4
Zuo Jia Zhuang
38
5
Liu Li Qiao Dong
34
6
Liu Li Qiao Nan
33
7
Dongzhimen Wai
31
8
Gong Zhu Fen Nan
31
9
Bei Da Di
30
10
Bei Tai Ping Qiao Xi
29
11
Jing An Zhuang
29
12
Xiajia Hutong
29
13
Qing He
29
14
Xiyuan
29
15
Beijing Zhangdong
28
16
Xi Bei He
28
17
Xiju
28
18
Si Hui Zhan
28
19
Liangmaqiao
28
20
Mu xi yuan qiao dong
27
21
Yan Huang yishu Guan
26
22
Yuquanying Qiao Xi
26
23
Dongwu Yuan
25
24
Guang An Men Nei
25
25
Qianmen
25
26
Wanshou si
25
27
Mu Xi Yuan Qiao Xi
25
28
Kandan Qiao
25Figure5 shows the distribution of the proportion of the stations and the amount of line number; the result shows that it follow the exponent distributionf(x)=0.79*e-0.67x, where xis the number of lines. It is found that most stations of BBN own less than 10 lines and only 9 stations own more than 30 lines.Figure 5
The distribution of a station’s amount of lines.In this paper, the transfer time of BBN is studied by using space P. From Table5, we can see that the most pair nodes are reachable through one or two transfers, and 99.85 percent of the pair nodes is reachable within four transfers and the average minimum transfer timeatr=1.88. Usually, the larger the atr is, the worse the performance of the bus network is. In general, atrcannot be more than 2; otherwise, we can consider that the performance of the bus network is bad and travelers’ trip is inconvenient. The transfer time of BBN is a little large and there is a room for improvement.Table 5
The proportion of the transfer time of Beijing bus network.
atr
0
1
2
3
4
4 more
unreachable
Proportion
0.0168
0.283
0.553
0.141
0.0047
0.00013
0.00137


## 5. Conclusion

In this paper, space L and space P are used to analyze the static properties of Beijing bus network. Space L is used to research the main topology properties of the Beijing bus network. The results show the Beijing bus network has small cluster coefficient, scale-free feature, and assortative correlation and the community structure is obvious. Moreover, we research the transfer property using space P. The result shows that the accessibility of the Beijing bus network is good and the average minimum transfer time is 1.88, which is a little large. A convenient bus network needs less transfers and high performance, and how to reduce transfer time and enhance the bus network dynamical performance is a valuable research.



---

*Source: 694956-2013-03-26.xml*