IEEE Circuits and Systems Magazine - Q4 2019 - 51

follow a power law distribution. Such networks are called
scale-free networks. Observing the scale-free property
in public transport networks can be inspiring since it
demonstrates a strong prevalence of the hierarchical
network structure, i.e., hubs at the top of the hierarchy serves maximum demand, while those below are
relatively midget nodes serving mediocre demand. Intuitively, although we would expect a certain number of
stops in a network are serviced by a large number of
routes, it is intriguing to verify such property mathematically. Interestingly, it was observed that some
of the public transport networks do exhibit the scalefree property. Furthermore, as explained later in this
section, the degree distribution in a network is a good
source of inference on the network evolution [23], [42].
Thus, the study of degree distribution has attracted enormous research interest.
The degree distribution exposes the probability of a
randomly selected node in the network having a degree
of k, i.e.,
N
(6)
p k = k or N k = Np k
N
where pk is the probability of finding a node with degree
k, Nk is the number of nodes with degree k, and N is the
total number of nodes in the network. Interested readers may refer to [5, Chapters 3-5] to probe further into
the difference between random and scale-free networks.
Table VII tabulates the degree distributions of various
PTNs reported in the literature. From Table VII, we make
the following observations:
i) An exponential degree distribution in L-space indicates that connecting a newly added node with

the existing nodes is more likely to be random.
This is in contrary to the notion of preferential
attachment where newly added nodes are connected to the already existing influential nodes
in the network, making the degree distribution a
power-law distribution.
ii) An exponential degree distribution in P-space indicates that defining a new route sequence in the
network is more likely to be random in order to
ensure a better coverage and service rather than
along the influential nodes in the network.
iii) An exponential degree distribution in C-space indicates that defining the stops along a route node
is more random than defining the stops along a
route to cover the influential nodes.
Thus, the degree distribution of a network provides
information on the topological evolution of the public
transport network in a city [23]. Up to now, some simple
network evolution models have been proposed based on
fitting empirical data. However, the nature of network evolution has never been verified from the actual deployment
perspective. As demonstrated by Barabási [2], the existence of hubs in a scale-free network can be a result of two
phenomena, namely, growth and preferential attachment.
However, the feasibility of deployment of preferential attachment in a real-world network is yet to be verified!
In our previous work [13], as part of analyzing bus transport networks, we proposed a supernode graph representation, where a supernode is a cluster of geographically
closely-located nodes which satisfy the criterion d th # 100 m,
where d th is the geographical distance between two
nodes. Using the supernode representation, we analyzed

Table VII.
Degree distribution patterns from some public transport network analyses.
L-space

P-space

C-space

References

Bus Transport Network
Power law

Exponential

[16] [20]

Shifted power law

[18]

Power law

[13]

Power law

Shifted power law

[19]

Heavy tailed

Power law

[11] [37]

Exponential

[10] [15] [17]

Exponential

[12] [26]

Exponential

[23] [24]

Power law

[25]

Exponential

[27]

[33] [34]

Metro Transport Network
Power law
FOURTH QUARTER 2019

IEEE CIRCUITS AND SYSTEMS MAGAZINE

IEEE Circuits and Systems Magazine - Q4 2019

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