IEEE Circuits and Systems Magazine - Q4 2019 - 44

extensively used representation in the analysis of
PTNs since it signifies the actual physical infrastructure that exists in a real-world network, and
renders useful information on relationship between the nodes.
ii) A graph in B-space, also called a bipartite graph,
is shown in Fig. 1(c), where both the routes and
stops are represented by nodes. A route node is
connected to all the stops it services, and a stop
node is connected to all the routes servicing it.
There is no directed edge between nodes of the
same type, i.e., an edge will not exist between two
route nodes or stop nodes. A graph in the B-space
will be undirected. Although analysis of PTNs using bipartite graphs finds limited application, the
one mode projection of a bipartite graph into the
P-space (node projected) and the C-space (route
projected) has gained significant attention.
iii) A graph in P-space is also called space-of-changes, space-of-transfers, or stop-unipartite graph,
and is shown in Fig. 1(d). In the P-space, the stops
are represented by nodes and every possible pair
of nodes that can be reached without making
any transfers are linked by edges (stops serviced
by a single route). A graph in the P-space can be
undirected or directed depending on the type of
transport networks (BTN or MTN) under study.
The P-space representation renders useful information for studying the transfers between different routes since the neighbors of a node in the
P-space representation are the set of nodes that
can be reached with or without making a transfer. Hence, the node set associated with a specific
route forms a clique or a complete subgraph.
iv) A graph in the C-space is also called route-unipartite graph, as shown in Fig. 1(e). In the C-space,
the nodes are the routes and two nodes are connected by an edge if they service a common set
of stop(s) along their journeys. A graph in the Cspace can be directed or undirected depending on
the type of networks under study (BTN or MTN).
Table II shows the allowed graph types (directed or
undirected) with respect to various spaces of network

representation (L-, B-, P- and C-space) and the type of
transport networks (bus or metro).
IV. Overview of Topological Analysis
of Public Transport Networks
Network Science by itself has no strong association
with any single field of study as its applications can be
found in a great variety of real-world systems. There are
a handful of parameters commonly used for analyzing
complex networks. In this section, some key network parameters that aid the understanding of public transport
networks are discussed. For brevity and convenience of
discussion, a nomenclature list is given in Table III.
The topology of the network under analysis is represented as a graph G, which is an ordered pair comprising a set
of nodes (V) and a set of edges (E), i.e., G = (V, E) such that
V = {n 1, n 2, n 3, ......, n N }; N = V
E = {e 1, e 2, e 3, ......, e L}; e i " (n i, n j) 6n i, n j ! V,
e i ! E; L = E

44

Space

Directed

Undirected

L

Yes

Yes

B

No

Yes

P

No

Yes

C

Yes

Yes

IEEE CIRCUITS AND SYSTEMS MAGAZINE

(2)

where N and L are the cardinality of the node set and
edge set, respectively. Appendix B lists the statistical
details of various PTN structures analyzed in the literature. Tables IV to VI provide an empirical comparison
of a few network parameters employed in the analysis
of PTNs using various spaces of representation, the
details of which will be discussed in the subse quent subsections.
A. Connectivity in Public Transport Networks
In a public transport network, the connectivity pattern of
a node with its neighbors is evaluated by a network parameter termed degree, which is the number of edges incident on a node. Degree is one of the most fundamental,
yet significant parameters in network analysis. Degree is
a local property of a node, and average degree of a network is a global parameter which conveys information on
the average connectivity of nodes in the entire network.
Depending on the graph type, the degree, k, and average
degree, G k H , for undirected networks are defined as
ki =

N

6i, j ! V, i ! j, G k H = 1
N

/ a ij

j=1

Table II.
Allowed graph type under various spaces
of representation.

(1)

N

/ ki

(3)

i=1

For directed networks they are
k in
i =

N

/ a ji,

k out
=
i

j=1

N

/ a ij,

k total
= k iin + k iout
i

i=1

6i, j ! V, i ! j
G k in H = 1
N

N

/ k ini ,

i=1
in

(4)
G k out H =

G k total H = G k H + G k out H

N

/ k iout,

i=1

(5)

All symbols in equations (3)-(5) are defined in Table 3.
FOURTH QUARTER 2019
IEEE Circuits and Systems Magazine - Q4 2019

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q4 2019
