IEEE Circuits and Systems Magazine - Q4 2019 - 40

I. Introduction
ublic transportation systems form a vital part of
our infrastructure that permits massive flow of
commuters within a city and between cities. In
order to meet the rising standards of living of the society, transportation networks have to keep abreast of the
need of commuters with respect to the ever increasing
demand of reducing the traveling time and extending the
area covered. At the same time, transportation networks
are facing series of challenges, including satisfying the
ever increasing passenger volume, achieving long-term
sustainability, and improving the quality of service. Such
challenges are encountered at various levels of operation,
ranging from infrastructure deployment to optimal route
planning, and the problems are addressed from different
angles depending on the discipline of study such as urban planning, regional science, geography, engineering,
etc. The literature abounds with diverse methodologies
adopted in various disciplines to represent, perceive
and analyze the complex dynamics of public transport
systems, among which, Geographic Information System
(GIS), graph theory, mathematical programming, and agentbased modeling are most commonly adopted [1].
Motivated by the notable contributions of network
theory [2], application of graph theoretic concepts in
the analysis of public transport networks (PTN) has attracted significant attention, and today, it is one of the
most widely employed approaches to understand the
nature of connectivity in PTNs. The representation of
a PTN as a complex network, together with the adoption of some concepts from statistical physics, offers
remarkable advantages in the modeling and analysis of
nonlinear and dynamic PTN structures. Specifically, the
analysis of PTNs using network theory permits the use
of a common platform on which to comprehend and decipher the inherent network features that are encoded
in the topological properties. Moreover, to apply the
concepts of complex networks, one should understand
the language of graph theory, as a prerequisite, where a
network is typically represented as a graph consisting of
a set of nodes interconnected by a set of edges.
Graph theory and network theory, despite being rooted historically in mathematics, has found applications
in statistical physics, biology, social sciences, finance,
and engineering. One of the oldest instances of using the
notion of graph theory to analyze a real-world problem
dates back to the 17th Century when Leonhard Euler
used the concept of nodes and edges to solve the problem of seven bridges of Königsberg, a notable problem
in the history of mathematics [3]. However, notable us-

P

age of graph theory was found by Gustav Kirchhoff who
employed nodes and edges to calculate voltages and
currents in electric circuits, nowadays widely known as
Kirchhoff's laws [4]. Subsequently, many real-world networks were analyzed using graph theory with significant
contributions from the fields of social networks (world
wide web) and biological networks, and later from other fields including friendship networks, relationship in
social media, food web, metabolism, professional ties,
author and co-author relations, citation networks, computer virus flow, network router analysis, chemical reactions, neural networks, transportation networks, etc.
From the literature, it was evident that modeling various
large real-world network structures as graphs, and analyzing their behavior from a network perspective, facilitated better understanding of both the global and local
properties of the network. Thus, this domain of study
has attracted a humongous amount of research interest in the past two decades [5]-[7]. Although a lot of
real-world complex systems have been analyzed using
graph theory, little attention has been paid to the field
of transportation networks which is an active research
area among researchers in transportation and logistics.
Although a public transport network can either be
unimodal or multi-modal, we focus on two major types of
public transportation, namely, the bus transport network
(BTN) and metro transport network (MTN), since we believe that these two types of networks are most widely
used by the public to meet their daily commuting needs.
In this article, the recent contributions and the concepts
employed in the topological analysis of public transport
networks are discussed. Our focus is on the understanding of various network parameters and approaches employed to analyze the topology of a PTN [5]-[7]. Moreover,
a brief discussion on the fundamental graph theoretic
concepts will be made whenever necessary.
The remainder of the paper is structured as follows.
Section II introduces a few preliminary steps to be followed to construct a real-world network topology from
given datasets, i.e., collecting the real-world datasets
from various online sources, and data mining to extract
useful information from both computational and visualization perspectives. Section III presents various spaces
of graph representation for studying the topological representation of PTNs. Section IV discusses in detail the
contributions of previous works in terms of the use of
appropriate network parameters that aid PTN analysis.
Section V focuses on some distinctive contributions accomplished in PTN analysis which might pave the way
for future research or some food for thought. Finally, in

T. Shanmukhappa, I. W.-H. Ho, and C. K. Tse are with the Department of Electronic and Information Engineering, The Hong Kong Polytechnic University,
Hong Kong. K. K. Leung is with the Department of Electrical and Electronic Engineering, and Computing, Imperial College London, United Kingdom.

40

IEEE CIRCUITS AND SYSTEMS MAGAZINE

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
