IEEE Circuits and Systems Magazine - Q4 2019 - 53

for directed networks. At the global level, the global clustering coefficient is given by
CD = 1
N

/ Ci .

(9)

Again, all symbols are defined in Table 3. For an in-depth
discussion of evaluating clustering by identifying triads
or cliques in different graph types, interested readers
are referred to ref. [43].
The study of clustering coefficients by itself has not
attracted much attention from researchers in the analysis
of PTNs. However, some inspiring observations can be
made from the relationship between Ci and k.
i) The dependency of Ci and k closely resembles a
power law where the value of Ci for a given k (C i (k))
is close to unity for small values of k, and C i (k) decreases rapidly with increasing k [11], [16], [20].
ii) As observed from (7) and (8), the inverse dependency of Ci on k indicates the hierarchical structure of a network in the L-space representation,
where high degree nodes (hubs) tend to form numerous connections with their neighbors, thus
reducing the possibility of their neighbors having
connections among themselves. This reduces the
local clustering coefficient of high degree nodes.
On the other hand, a low degree node has a greater tendency to be connected among its neighbors,
increasing its local clustering coefficient [11].
iii) In the P-space representation, all stations of a specific route form a perfect clique, with C i = 1 for
all nodes in the route. The value of C i becomes
smaller when the nodes are shared by multiple
routes. Thus, in the P-space representation, the
fully connected subgraphs of all stops along a route
constitute local cliques, and these local cliques
are shared between routes through the common
nodes. Hence, the nodes with a low degree and a
high clustering coefficient belong to a fully connected local clique, whereas the nodes with a high
degree and a low clustering coefficient connect
multiple local cliques, reflecting that hubs act as
coordinating points for several routes [16], [23]-
[25], [44]. Thus, the distribution of C i (k) gives an
indication on how the clustering is organized for
nodes of various degrees.
Appendix C summarizes the common interpretations
of transitivity under various spaces of network representation, and Tables IV to VI give the ranges of values of the
global clustering coefficient under the various spaces of
network representation. It can be seen that the clustering in P-space is significantly higher than that in L-space
due to the existence of more local cliques in P-space.
Although clustering has been extensively employed in
FOURTH QUARTER 2019

L-space PTN analysis, the physical significance of evaluating both local and global clustering coefficients in Lspace is vague. Moreover, the clustering coefficient is
more meaningfully interpreted in the P-space representation for a PTN analysis. Also, evaluating the clustering
coefficient in B-space (bipartite graph) is meaningless
since the neighbors of a node are from the same group,
and there exists no connection between nodes of the
same group in B-space. However, evaluating clustering
in C-space conveys interesting information on the extent
of route overlapping in a network which is an extremely
useful information for route optimization, and thus deserves more work.
D. Travel Distance in Hops
In a PTN, the number of hops to be traversed to accomplish a journey between any two chosen stops in a
network is normally measured by path length. In graph
theory, a path is a sequence of nodes connected by
links. The shortest path length is the shortest number
of links between two chosen nodes, and the average
path length (geodesic path) is the average of the shortest path length between all node pairs in the network.
The diameter is the longest of all shortest paths, and is
an upper bound of the average path length. Although
the measure of path length conveys no information on
the number of transfers to be made during the journey,
it is still an important measure in the public transport
network analysis from a passenger point of view since
the number of hops is definitely one of the prime factors
considered by the passengers in selecting a route for the
journey. There are a few notable algorithms for finding
the average path length in a network [45]. However, it
should be noted that the edge weight should be cautiously chosen (represented) in the evaluation of the average path length in a weighted graph in order to avoid
a wrong interpretation of the measured path length. For
example, the Dijkastra's algorithm using dij (geographical distance between two stops) and vij (average vehicular speed along a road segment) as the edge weight may
generate two completely different results in evaluating
the path length between two chosen nodes [46]. The average shortest path length is usually given by

/ d ij

Gd H =

i!j

N (N - 1)

6i = j = 1, 2, .., N

(10)

where dij is the geodesic distance between nodes ni and
nj. Also, d ij = 1 if there exists a path between the two
nodes, and d ij = 3 otherwise, implying a possible divergence problem in a non-connected graph. A smaller
value of d indicates a shorter travel distance (with or
without transfers) that a passenger should take to
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