IEEE Circuits and Systems Magazine - Q4 2019 - 58

information and specifically correlation between node
degrees in the network. Depending on the correlation
type, the network can be either assortative (connection
between two high-degree or low-degree nodes) or dissassortative (connection between a high-degree node
and a low-degree node). Assortativity can be assessed
in terms of the average degree of a node's neighbors
[58]. Moreover, Newman [59] later demonstrated that assortativity can be effectively evaluated by the Pearson
correlation coefficient, i.e.,
ki + ji 2
2 E
i
i
r=
ki + ji 2
j 2i + k 2i
M -1 /
- ;M -1 /
2
2 E
i
i
M -1 / j i k i - ;M -1 /

(20)

where ji and ki are the degrees at both ends of an edge i,
M is the number of edges, and - 1 # r # 1. The network
is assortative if r is +ve, and disassortative if r is -ve. Foster et al. [60] extended (20) for a directed network where
four typical assortative mixing levels are observed,
namely, r(in, in), r(in, out), r(out, in) and r(out, out) denoting the correlation between in-degree of two nodes,
out-degree of two-nodes, in-degree of a node, and an
out-degree of a node, respectively. The physical significance of assortativity is that a negative value of r shows
the existence of core-periphery network structure and
a positive value of r shows a layered network structure.
In PTN analysis, it is more desirable for the network to
be disassortative in order to offer better service and
connectivity in a core-periphery structure. However, if
a PTN follows a layered architecture, it is desirable to
have assortative mixing between highly central nodes
or hubs, which in turn are expected to have a disassortative mixing with other nodes in the network.
It has been observed that smaller networks are expected to be more disassortative, and larger networks
exhibit both assortative and disassortative tendency
[18], [21], [24]. Chatterjee et al. [22] developed the degree-correlation matrix to visualize the connectivity
preferences of nodes in the L-space and P-space representations. Strong assortativity has been observed in
L-space among low degree nodes, whereas, in P-space,
strong assortativity can be seen in nodes of certain
node degrees. Also, Ferber et al. [17] investigated the
assortativity for the second neighbor ^r (2)h of a node,
and found that a more positive r (2) indicates stronger
correlation with the immediate neighbors as well as the
second neighbors. Although the property of assortative
mixing has so far been studied with respect to a node
degree, the polarization of nodes with respect to other
parameters (e.g., various centrality measures) may offer
a different perspective in understanding the network behavior. Such study of social behavior of public transport
58

IEEE CIRCUITS AND SYSTEMS MAGAZINE

stops and routes will provide important information for
the design of stop locations and route distribution.
I. Communities
Community is a pair-wise parameter studied at node
level and yet offers a global view in network theory.
Identifying communities in a network, also called network partitioning, can be thought of as an extension to
identifying assortative mixing in the network, but over a
much larger set of nodes. A community is a subgraph of a
network with nodes of similar behavior (in terms of connectivity), and there are dense links within a community
but much fewer links between communities. Graph partitioning has been a hot research topic in the field of graph
theory in the past decade since evaluating communities,
especially in large and dense networks involve computationally intensive processes. An index called modularity is employed to evaluate communities in a network, as
demonstrated by Newman and Girvan [61], [62], i.e.,
Q = / s ij - / s ij s ki
i

(21)

ijk

where sij is a component of matrix s which defines the
number of edges in the original network that connects
nodes in community i to nodes in community j, and
0 # Q # 1. Here, Q = 0 indicates the absence of similar
degree connectivity in a network (random graph), and
Q = 1 indicates a strong connection within the communities. Equation (21) has been popularly used to evaluate
the modularity index for all types of networks (directed,
undirected, weighted and unweighted). Moreover, in
the survey conducted by Khan and Niazi [63], various
modularity metrics have been considered depending on
the network type. In the study by Háznagy et al. [12], the
city's center has been found to have a few communities
whereas the periphery has numerous communities. The
work by Bona et al. [25] has identified 187 different communities with a modularity value between 0.3 and 0.7 for
a PTN in a Brazilian city. For the Chinese city of Qingdao,
Zhang et al. [19] observed a high modularity value of 0.8
with an average of 20 communities. Furthermore, a total
of 46 communities with a strong modularity value of 0.91
was observed in an urban rail transit system in China [18].
Sun et al. [27] also found a weak modularity value of 0.34
with 7 communities in urban bus networks, where communities have been consistently identified with respect
to their spatial coverage. Appendix C offers various perspectives of understanding community structures under
various spaces of network representation. A physical significance of identifying communities in a network is that
knowing the structural equivalence of nodes and their
communities is crucial to understanding of the behavior
of the intra-community and inter-community nodes.
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