Article citation information:

Kwatra, D., Ramachandra Rao, K., Bhatnagar, V. Novel accessibility metrics based on hierarchical decomposition of transport networks. Scientific Journal of Silesian University of Technology. Series Transport. 2023, 118, 139-160. ISSN: 0209-3324. DOI: https://doi.org/10.20858/sjsutst.2023.118.10.

Divya KWATRA[1], Kalaga Ramachandra RAO[2], Vasudha BHATNAGAR[3]

NOVEL ACCESSIBILITY METRICS BASED ON HIERARCHICAL DECOMPOSITION OF TRANSPORT NETWORKS

Summary. Scientific analysis of public transport systems at the urban, regional, and national levels is vital in this contemporary, highly connected world. Quantifying the accessibility of nodes (locations) in a transport network is considered a holistic measure of transportation and land use and an important research area. In recent years, complex networks have been employed for modeling and analyzing the topology of transport systems and services networks. However, the design of network hierarchy-based accessibility measures has not been fully explored in transport research. Thus, we propose a set of three novel accessibility metrics based on the k-core decomposition of the transport network. Core-based accessibility metrics leverage the network topology by eliciting the hierarchy while accommodating variations like travel cost, travel time, distance, and frequency of service as edge weights. The proposed metrics quantify the accessibility of nodes at different geographical scales, ranging from local to global. We use these metrics to compute the accessibility of geographical locations connected by air transport services in India. Finally, we show that the measures are responsive to changes in the topology of the transport network by analyzing the changes in accessibility for the domestic air services network for both pre-covid and post-covid times.

Keywords: integral accessibility, network topology, weighted networks, k-core decomposition, eigenvector centrality, airlines network

1. INTRODUCTION

Accessibility research has rapidly progressed in the last two decades [1-3]. However, implementation of most of the proposed accessibility metrics is limited in practice, facing challenges in their adoption [4-5]. Levine gives a critical review of the views that present obstacles in the practical implementation of accessibility metrics [6].

Traditionally, accessibility has been defined as the ease of reaching services, goods, activities, or destinations. Hansen introduced accessibility as the potential opportunity for interaction [7]. Since then, a plethora of accessibility definitions have been advanced in seminal papers [8-10]. Ingram defines accessibility as ”capable of being reached”, thus alluding to it as a measure of proximity between two geographical locations [9]. Koenig asserts that accessibility is associated not only with reaching the destination but also with the quality and availability of service provided by the available transport network [8]. Geurs and Van Wee describe the accessibility of a location as a reflection of the spatial organization and quality of the transport system that enables an individual’s connectivity to the location [3].

Given diverse definitions, accessibility is often assessed by considering the measures that evaluate the availability and quality of a transport service. Accessibility can either be relative or integral. The categorization is based on the degree of connectivity of the location with another location or all possible locations in the network. Relative accessibility is asymmetric, yet it is the simplest measure of accessibility. Integral accessibility of a location is the aggregation of its relative accessibility to all other locations in the network. Koenig highlighted two dimensions for studying accessibility in transport networks, namely transport services and activity [8]. The ease of traveling from one location to another in terms of distance, time, or cost reflects the transport service dimension of accessibility. Activity dimension, on the other hand, is measured in terms of distribution and amount of attractive activities at a location, including stores, offices, residences, etc. Handy distinguished between local and regional accessibility based on the distance between a given location and activity [11].

Geurs and Van Wee classified accessibility measures into four categories based on location, utility, people, and infrastructure [3]. Location-based measures describe the level of accessibility to spatially distributed specific activities (for example, jobs within a particular region) [12, 13]. Utility-based measures typically incorporate individual traveler preferences and activities at a location for quantifying accessibility. Hellervik et al. considered such activities as attractor variables for quantifying accessibility [14]. People-based measures consider people’s behavior by focusing on their space and time and the use of places based on the activities they are interested in [15]. Infrastructure-based measures use travel speed and level of congestion between pairs of locations to quantify accessibility between them [16].

Handy argued that in addition to the abovementioned measures, one should focus on the reachability of location and not on the means to reach it while quantifying accessibility [17]. Affirming the argument, Wu and Levinson emphasized that distance between locations is nonexistent unless they are connected by a network and invigorates the study of accessibility measures based on the topology of the transport network [1].

It is well established that network topology augments transport and activity dimension and provides a holistic picture of the accessibility of a geographic location. It defines the physical connectivity between two geographical locations and is known to influence accessibility significantly [18-20]. Hierarchy is a well-recognized topological characteristic that reveals the organization of a network. However, its potential has been recently realized for the analysis of transport networks[21-24].

1.1 Motivation and contribution

According to Koenig, transport services and activities are the two dimensions of transport networks [8]. We advocate the study of accessibility measures in transport networks along the third dimension, that is, network topology. Our argument is grounded on several existing studies emphasizing that connectivity in transport networks influences accessibility [1, 19, 20]. We advance this view further and assert that the accessibility of a geographic location is additionally impacted by its position in the hierarchical decomposition of the transport network.

We propose novel accessibility metrics based on an inherent hierarchy of nodes in the network topology revealed by −core decomposition. Since the algorithm for -core decomposition is linear in the number of edges, accessibility for large networks (for example, nationwide, continent-wide or global transport networks) can be computed efficiently. The measures are flexible and proficient at capturing the combined effect of opportunities and reachability. They can also accommodate attributes like travel cost, travel time, distance, frequency of service, etc., that arise naturally in the analysis of transport networks. These attributes can be assigned as edge weights in the network to yield an objective accessibility metric. When new services are added or existing ones are withdrawn, the accessibility of nodes is impacted. The proposed metrics are responsive to changes in the topology of the transport network.

The proposed core-based accessibility measures consider the density of connections in the immediate neighborhood, two-hop neighborhood, that is, region, and the entire network. The intuition that density-differential of transport connections for a geographical location is an essential determinant of accessibility is well captured by core-based accessibility metrics. To the best of the authors’ knowledge, this is the first attempt to design accessibility metrics that can be computed and interpreted at multiple granularity levels while exploring the topological hierarchy of the transport network.

The rest of the paper is organized as follows. Section 2 presents the background, explains the -core decomposition of a complex network, and graph-theoretic measures related to accessibility research. Then in Section 3, we propose and explain the core-based accessibility measures. We present applications of the proposed accessibility measures on the test network in Section 4 and a case study to compare the accessibility of Indian airports connected by domestic airlines in the pre-covid and post-covid times in Section 5. Finally, we conclude the paper.

2. BACKGROUND AND RELATED WORKS

Recently, complex networks have attracted serious attention for the analysis of urban and national level public transport systems. A complex network is an abstract mathematical structure , where is the set of nodes and is the set of edges. There exists an edge between , if and only if they are directly related. The definition of relation is specific to the application. The network is represented by an adjacency matrix , where if , else . In case the relation between two nodes is directional, the adjacency matrix is asymmetric. Further, if the strength of the relation is quantified, denotes the weight of the edge . Unless specified, we assume a network to be undirected and unweighted.

Example 1: We model the transport system as a simple, weighted and undirected toy network , as shown in Fig. 1, where is the set of 11 geographical locations. The edge weight represents the connection strength between and (distance, time to travel, or cost of travel etc.). Tab. 1 shows the weighted and symmetric adjacency matrix for .

Fig. 1. Toy transport network with 11 nodes and 15 edges

Tab. 1

Weighted adjacency matrix for toy network in Fig. 1

Node
	0	0	0	0	8	0	0	0	0	0	0
	0	0	10	7	4	4	0	12	0	0	0
	0	10	0	11	3	0	0	3	0	0	0
	0	7	11	0	7	0	2	0	0	4	0
	8	4	3	7	0	17	0	0	0	0	0
	0	4	0	0	17	0	0	0	0	0	0
	0	0	0	2	0	0	0	0	0	0	0
	0	12	3	0	0	0	0	0	7	0	0
	0	0	0	0	0	0	0	7	0	0	5
	0	0	0	4	0	0	0	0	0	0	0
	0	0	0	0	0	0	0	0	5	0	0

2.1 Topology-based accessibility measures

The topology of a network reveals the patterns of connectivity between geographical locations. Researchers have employed degree, closeness and betweenness centrality measures to quantify the accessibility in transport networks [19, 20, 25-27].

Degree has been used to determine important nodes in transport networks [26]. Since the degree is a local property of the node, it indicates connectivity in the immediate neighborhood of a geographical location. However, it may not be an accurate predictor of accessibility as it does not indicate the extent of connectivity of neighbor nodes. For instance, in Fig. 1, nodes and have the same degree but is more accessible due to its connections with better connected nodes ( and ) in the network than .

Closeness centrality of a node is calculated as the reciprocal of the sum of the shortest path length from node to other nodes in the network, as given below.

(1)

The measure indicates the importance of a node by quantifying its closeness to other nodes in the network. Nodes with higher scores are easier to reach than other nodes in the network and thus reflect higher accessibility.

Betweenness centrality measures the extent to which a node lies on paths between other nodes. It is computed as the sum of the fraction of shortest paths between all pairs of nodes passing through vi, as shown below.

(2)

Here, is the number of the shortest paths between the nodes passing through node , and is the number of paths between nodes and in the network.

Betweenness centrality is useful to identify nodes that serve as a bridge or transfer points to other nodes in the network. Removal of these nodes from the network may disrupt reachability. Betweenness centrality is augmented with other measurable attributes of the geographical location to quantify betweenness-accessibility [27]. Betweenness centrality of terminal nodes is zero, due to which the betweenness-accessibility of such nodes may be zero.

2.2 Hierarchical decomposition: preliminaries

Complex networks can be decomposed into a hierarchy of sub-networks based on the connectivity of nodes, such that the densest sub-network is at the top. Hierarchy is recognized as an important principle of organization in complex networks and is observed in all real-life networks [28]. Examples of hierarchy span from social networks [[29], [30]], biological networks [31, 32], technological networks [33], and urban systems [34] to transport networks [22-27], [35]. We unravel the hierarchy of nodes (geographical locations) using the -core decomposition to quantify their accessibility.

Seidman proposed the -core method to decompose a complex network into a hierarchy of maximally connected sub-networks [36]. The decomposition gives rise to a laminar family such that . Here, is the sub-network induced by the nodes with core values greater than or equal to . Seidman defines the -core decomposition of a network as follows [36].

Definition 1: -core: Given a simple, undirected, unweighted network , -core is the largest sub-network of induced by the subset of nodes and , if and only if the degree of each node in is greater than or equal to . Thus, coreness of a node is defined as:

(3)

The -core of is obtained by recursively removing all nodes with degrees less than until the remaining nodes in the network have degrees at least . It is established that the -core of a network is unique and connected [37].

Batagelj and Zaversnik proposed a linear time algorithm for -core decomposition [38], which makes it very attractive for analyzing large sparse networks common in diverse domains. The algorithm is available in well-known R[4] and Python[5] packages.

Example 2: Fig. 2 shows the -core decomposition of the toy network shown in Fig. 1. The -core sub-networks are extracted through a peeling process. As minimum degree of the nodes is one, core value is assigned to the nodes , and they are removed from the network. Removal of node reduces the degree of to one and hence is also assigned core value 1. Next, nodes with degree 2 are assigned the core value 2 and are removed from the network . Proceeding in this way, nodes with degree 3 are assigned the core value 3 . After removing these nodes, we get a null network. Thus, we have maximum core value for .

Fig. 2. Core decomposition of the toy network shown in Fig. 1
reveals three level hierarchy (ovals) in the network.
Nodes marked in the same color have the same core value

2.3 Hierarchical decomposition of transport network

The emergence of hierarchy in transport networks is well documented by Yerra and Levinson [39]. Boguna et al. argued that the core of a network plays a significant role in enhancing the navigability of networks [40]. Wuellner et al. used core decomposition to analyze the seven largest airlines in the US [41]. They observed that nodes belonging to the highest k-core are the hub nodes and the most viable transfer points [41]. Thus, the authors concluded that nodes with higher core values are more resilient to attacks on nodes and edges of a network. Azimi-Tafreshi et al. used k-core decomposition to compare the topological structures of various low-cost and major airlines in the country [35].

Du et al. decomposed the Chinese airlines network into three layers: core, bridge, and periphery [22]. They concluded that the core layer is densely connected and sustains the maximum flow of flights connecting airports of capital cities. And the bridge layer consists of airports that connects two other layers. Further, the periphery layer is sparsely connected and sustains little flight flow connecting airports in remote areas. Dai et al. explored the evolution of the topological and multilayered structure of the Southeast Asian air transport network from 1979 to 2012 [23]. They decomposed the network into three layers based on the k-core values of the nodes. The periphery layer has nodes with core value one, the core layer has nodes with the maximum core value, and the bridge layer has nodes with intermediate core values. The authors concluded that the multilayered structure of the Southeast Asian air network has significantly evolved and is less mature and integrated than its EU counterpart.

3. HIERARCHY-BASED ACCESSIBILITY METRICS

We propose to use the core decomposition of a network to quantify the accessibility of nodes in the transport network, advancing the ideas proposed in [22], [35], [40], [41]. The underlying intuition is that better-connected nodes in higher cores of the network are more advantaged. Existing topology-based accessibility measures (Betweenness accessibility [27]) do not acknowledge the advantage that accrues due to linkage with better accessible nodes. Hence, we propose three novel core-based accessibility metrics for unweighted and weighted networks in this section.

3.1 Accessibility metrics for unweighted networks

We define and introduce the mathematical formulations for the proposed three topology-based metrics for unweighted networks, highlighting the role of connectivity in quantifying the accessibility of nodes in transport networks.

A. Core Accessibility

Core accessibility is a measure that provides a snapshot of similar connectivity patterns of nodes in the network. A node with core value k is connected to at least similarly connected nodes. Thus, the core value gives a lower bound to the connectivity of a node.

Definition 2: Core Accessibility (CA): Given a simple, unweighted and undirected network , core accessibility of a node is defined as the core value of in core decomposition of .

(4)

Core accessibility partitions the network into multiple layers (levels), generalizing the three-layered representation suggested by [22]. Maximum core accessibility in the network indicates the levels of hierarchy in the network. Accordingly, it can be used to compare navigability in the network as suggested in [40]. Since core accessibility indicates minimum connectivity, it groups multiple locations at the same hierarchical level. Consequently, core accessibility is a coarse metric (Section 4). We define below an advanced metric for perceptive comparison of accessibility of geographic locations at the regional level.

B. Local Core Accessibility

Connectivity in the immediate neighborhood of the node plays an influential role in determining its accessibility at the local level. Since the accessibility of a node (location) is impacted by that of its neighbors, a node stands to gain an advantage if it is connected to neighbor nodes with higher accessibility. Local core accessibility measure considers the density of connections in the two-hop neighborhood of a node by giving due consideration to the core accessibility of all its neighbors.

Definition 3: Local Core Accessibility (LCA): Given a simple, unweighted and undirected network , local core accessibility of node is defined as the sum of the core accessibility values of neighbor nodes of .

(5)

Here, denotes the set of neighbors of . Local core accessibility serves as a metric for quantifying regional accessibility of geographical locations. Aggregating core accessibility of neighbors empowers the LCA to expose finer differences in the accessibility of geographical locations within a region. Hence, it is particularly useful in discriminating between the local accessibility of nodes with same core accessibility.

C. Network-wide Core Accessibility

Intuitively, the accessibility of a node at the global level is affected by the accessibility of its neighbors, which in turn are impacted by the accessibility of their neighbors, and so on. The nodes connected to neighbors with higher regional accessibility are advantaged compared to those with neighbors having lower regional accessibility. This intuition is captured by the Eigen Vector centrality [6] of a node in a network which quantifies the importance of a node recursively while considering the topology of the network [42].

Network-wide core accessibility quantifies the accessibility of a node at the global level and is computed recursively by considering the local core accessibility of its neighbors. Consider matrix that consolidates local core accessibility of all pairs of nodes in as follows.

(6)

Element in connotes the accessibility advantage that node gets because of node . It is noteworthy that for a node pair , the accessibility advantage for from may be different from that for from . The difference arises due to the variation in their respective neighborhood networks. Retention of the accessibility differences among nodes due to their location in the overall topology of the network renders matrix asymmetric. Lack of symmetry also empowers matrix to expose subtle differences between the accessibility of nodes while considering their position in the hierarchy prevalent in the network. Example 3 in Appendix D demonstrates the construction of matrix for the toy network given in Fig. 1.

L can be considered an adjacency matrix of a weighted and directed graph with nodes at an abstract level. Eigenvector centrality of the nodes in this network connotes network-wide core accessibility. Let vector of size denote the network-wide core accessibility of all nodes in . We initialize to all ones assuming that all nodes are initially equally accessible over the entire transport network. Subsequently, network-wide accessibility of all nodes is computed iteratively using L (Definition 4).

Definition 4: Network-wide Core Accessibility (NCA): Let L be the matrix of pairwise local core accessibility values as computed in Equation (6). Network-wide accessibility , of a node is computed iteratively as:

(7)

until converges.

NCA provides a global (network-wide) view of the accessibility of locations and thus can be classified as an Integral accessibility measure as defined by Ingram [9]. Further, NCA is more discerning than LCA because it ensconces the location of the node in the overall topology of the network.

We present applications of core-based accessibility measures for unweighted transport networks in Section 4.

3.2 Accessibility metrics for weighted networks

Accessibility measures proposed in the previous sub-section highlight the role of connectivity in quantifying the accessibility of nodes in transport networks. However, these measures ignore several important aspects of real-world transport networks like the cost of travel, transport capacity, travel time, distance, transport modes, service frequencies, etc. These attributes of connectivity between two nodes can be naturally modeled as edge weights in the transport network and have a substantial impact on the quantitative assessment of the accessibility of locations.

Given a simple, undirected and weighted network , where is the weight matrix representing the weight of edges, as per the attribute(s) chosen for study. Matrix could represent any of the attributes of connectivity mentioned above or a function of these attributes. For example, a product of travel cost and capacity denotes revenue earned by the services company. Weighted degree of node is the sum of weights of edges incident on it. Normalized weighted degree of is defined as follows.

(8)

Please note that isolated nodes in the network have normalized weighted degree zero.

Abiding by the fact that the weights of the edges impact the accessibility of nodes, it is now feasible to differentiate their accessibility considering their normalized weighted degree. We, thus, extend the definitions of the three accessibility indicators given in Section 3.1 to propose their weighted versions, namely weighted core accessibility, weighted local core accessibility, and weighted network-wide core accessibility.

Definition 5: Weighted Core Accessibility (wCA) of a node is defined as the product of its normalized weighted degree ( ) and its core accessibility.

(9)

Definition 6: Weighted Local Core Accessibility (wLCA) of a node is defined as the product of its normalized weighted degree and its local core accessibility.

(10)

Definition 7: Weighted Network-wide Core Accessibility (wNCA) of a node u ∈ V (G) is defined as the product of its normalized weighted degree and its network-wide core accessibility.

(11)

We present a case study in Section 5 to demonstrate the advantages of the proposed weighted metrics.

4. APPLICATION OF CORE-BASED ACCESSIBILITY METRICS FOR UNWEIGHTED NETWORK

We consider an unweighted and undirected test network of domestic air connectivity by Air India between 36 states and union territories of India that are coded[7] with two letters. Two states are connected if and only if two cities in the states are connected by a flight. We compute the proposed core-based accessibility metrics for this network, rank the nodes, and explain the significance of each metric.

The k-core decomposition of the test network unfolds the hierarchy that provides insight into the different layers contributing to the network connectivity (Błąd! Nie można odnaleźć źródła odwołania.). Nodes with higher core values ( = 5, cyan blue) belong to denser regions of the network compared to those in lower cores. Edges marked in black connect the nodes in the same core, and edges marked in blue connect the nodes in different cores. Node SK is disconnected in the network as no Air India flight is connecting it to any state[8], and hence its core value is zero in this network. Throughout this paper, we use this test network to explain the relevant concepts and measures.

4.1 Comparing core accessibility

Based on the premise that the position of a node in the hierarchical decomposition of the network determines its accessibility in the network, we compare the accessibility of different Indian states and union territories serviced by Air India. We compare the core accessibility of locations in the transport network shown in Błąd! Nie można odnaleźć źródła odwołania.. Core decomposition of the network reveals five levels of hierarchy, indicating that states can be ranked from 1 to 5 based on their connectivity patterns. Nodes belonging to highest core are ranked one and have maximum core accessibility in the network. Tab. 2 shows the ranks of connected nodes in the test network.

Limitations of Core Accessibility: As evident in Tab. 2, core accessibility (CA) bunches multiple locations together and assigns the same rank to them. In other words, it cannot discriminate between the relative importance of nodes in the same core. For example, AS and BR are ranked three, as shown in Table 2, even though AS is better connected than BR, as shown in Błąd! Nie można odnaleźć źródła odwołania.. It is noteworthy that core accessibility cannot bring out this difference between similarly ranked locations.

Fig. 3. Core Decomposition of unweighted and undirected test network reveals five levels of hierarchy in the network. Nodes with the same color belong to the same core

Tab. 2

Ranks of nodes in the test network according to their core accessibility (CA)

Rank	1	2	3	4	5
Nodes in the test network	AP, DL, KA, MH, TS, TN, WB	GA, KL, OD	AN, AS, BR, GJ, MP, PY, UP	AR, CG, CH, HP, HR, JK, LA, MN, MZ, NL, PB, RJ	DD, JH, LD, ML, TR, UK

4.2 Comparing accessibility at the regional level

The local core accessibility (LCA) measure quantifies the ease of reaching a location (node) within a region by aggregating core accessibility of its neighbor nodes. LCA captures finer distinctions between nodes with the same core accessibility values by considering the location of its neighbors in the network hierarchy. Nodes with the same core accessibility may have different LCA values due to differences in the core accessibility of their respective neighbors. Analyzing nodes AS and BR, ranked equally for core accessibility measure, have different local core accessibility values. Note that in Table 3a, AS is ranked 10, while BR does not appear among the top 15 nodes. Thus, the LCA measure can distinguish among the nodes ranked equally by the core accessibility measure.

(a) Neighbor of node AS with their respective CA values

(b) Neighbor of node OD with their respective CA values

Fig. 4. Core accessibility values of neighbor of nodes AS and OD as in the test network

Consider the seven highest-ranked nodes (AP, DL, KA, MH, TS, TN, and WB), according to their core accessibility in Tab. 2. These nodes are ranked uniquely by the LCA measure, as shown in Table 3a. It is interesting to note that though AS has a lower core accessibility than OD, it has a higher LCA value. This is because AS is connected to nodes with higher core accessibility than OD, as shown in Figures 4a and b.

(a) Neighbors of GJ with their respective LCA values

(b) Neighbors of AN with their respective LCA values

Fig. 5. LCA values of neighbors of GJ and AN as in the test network

Limitations of Local Core Accessibility: Though the LCA computes the accessibility of a node by giving due consideration to its neighborhood, it is deficient in discerning the network-wide accessibility of nodes. Two nodes with the same local core accessibility may have different patterns of network-wide connectivity. For example, in Table 3a, AN and GJ in the test network (Błąd! Nie można odnaleźć źródła odwołania.) have the same local core accessibility. But neighbor nodes of GJ have higher regional accessibility than the neighbors of AN. This is illustrated in Figure 5a, showing the neighbors of GJ, and Figure 5b, showing the neighbors of AN along with their local core accessibility values. The LCA is unable to discriminate the nodes on this ground and thus ranks them equally.

Tab. 3

Ranks of top 15 nodes of the test network in Błąd! Nie można odnaleźć źródła odwołania. for their
(a) local core accessibility and (b) network-wide core accessibility )

(a) values

Node		Rank
DL	71	1
MH	58	2
TN	48	3
WB	42	4
KA	41	5
TS	36	6
AP	32	7
KL	28	8
GA	22	9
AS	21	10
OD	20	11
MP	18	12
UP	16	13
AN	15	14
GJ	15	14
PB	14	15

(b) values

Node		Rank
DL	1	1
MH	0.8156	2
TN	0.6385	3
KA	0.539	4
WB	0.4822	5
TS	0.4475	6
AP	0.3598	7
KL	0.2732	8
OD	0.1719	9
GA	0.1552	10
AS	0.1317	11
MP	0.1298	12
GJ	0.1037	13
UP	0.0982	14
PB	0.0806	15

4.3 Comparing accessibility at the network level

Transport planners and service providers often need a global (network-wide) view of the accessibility of locations. NCA measure further teases out the differences in accessibility from the perspective of the overall topology of the network. Consider nodes GJ and AN, ranked equally (14) by the LCA measure, as shown in Table 3a. They are assigned different network-wide accessibility values (Table 3b). GJ is ranked 13 by the NCA measure, but AN does not appear among the top15 nodes. Thus, NCA discriminates among the nodes ranked equally by the LCA measure. Critical observations, as elaborated below, provide additional insights into the advantages of network-wide accessibility.

Table 3 displays the top 15 nodes ranked according to their network-wide core accessibility values. Consider nodes WB and KA, which ranked four and five, respectively, for LCA values (Table 3a). Interestingly, despite KA and WB being connected to a few common neighbor nodes (AS, DL, MH, TN, and TS), KA is ranked higher than WB according to network-wide core accessibility (

Fig. 6). This is due to more connections of KA to nodes with higher regional accessibility (GA, AP, and KL), as shown in

Fig. 6a. On the other hand, WB is connected to more nodes with relatively lower regional accessibility (AR, BR, AN, ML, MZ, NL, and TR). This can be observed from the neighborhood network of WB, as shown in

Fig. 6b.

(a) Neighborhood of node KA with their respective LCA values

(b) Neighborhood of node WB with their respective LCA values

Fig. 6. Neighborhood of KA and WB as in the test network

5. COMPARING ACCESSIBILITY IN WEIGHTED AND UNWEIGHTED NETWORKS

We first demonstrate the advantages of the weighted version of accessibility metrics over their unweighted counterparts using the monotonicity of the metrics as a quality measure. Subsequently, we present a case study demonstrating the application of the proposed metrics to study temporal changes in transport networks. We use the proposed metrics to compare the accessibility of Indian airports in pre-and post-covid times. The data for both experiments are sourced from the Directorate General of Civil Aviation[9]. The code for the metrics is written in R (64 bits, v 4.0.3)[10].

5.1 Assessing the quality of metrics

It is important to assess the discriminatory power of the metrics as all values are eventually transformed to rank for practical utility. A metric that assigns the same rank to many nodes is less preferable to a metric that can tease out the differences better and has fewer nodes with the same rank.

We use the monotonicity function to assess the fidelity of our metrics quantitatively [43]. We rank the nodes according to their accessibility values. The node with the highest accessibility is ranked one. The nodes with equal accessibility are assigned the same ranks. Let be a vector of the ranks assigned to nodes of the graph , with as the number of ties in the ranks. Monotonicity of ranks is defined as given below.

(12)

Monotonicity of the metrics is one if each node in the network is assigned a unique rank and zero when all nodes are assigned the same rank. We compute the monotonicity of each metric to ensure its efficacy.

5.2 Analyzing the accessibility of a service provider

We construct a simple, undirected, weighted network for the winter schedule 2020 (winter20) of Air Asia, a domestic airline. Then, we compute the weekly frequency of each incoming and outgoing flight, excluding the flights scheduled only for a specific day. Thereafter, we consider the minimum frequency of incoming/outgoing flights between pairs of nodes (airports) in the network as the edge weight. The network is shown in Błąd! Nie można odnaleźć źródła odwołania. in Appendix B.

Tab. 4 shows the degree (column Degree), normalized weighted degree (column ), and ranks of nodes (airports) assigned as per the proposed unweighted and weighted versions of the three-accessibility metrics. The nodes are sorted by their normalized weighted degree (column ). We compare the ranks assigned to the airports, presenting a detailed analysis below.

We observe that nodes belonging to the same core (column Core) are ranked equally for core accessibility (column CA). But when the weighted core accessibility is computed, the ranks are distinct. For example, BLR, DEL, BOM, CCU, MAA, and HYD belong to core five and are ranked one according to their core accessibility. However, BLR is ranked highest according to its weighted core accessibility (column wCA) due to the maximum number of flights (158) connecting it to other airports in the network. Since core accessibility bunches multiple nodes together, assigning them the same rank, it has the least monotonicity (0.57), showing that it is a coarse metric. However, when weights are considered, monotonicity increases significantly to 0.98. Note that COK and JAI are differently accessible due to the difference in the accessibility of their respective neighbors. However, despite its high monotonicity, wCA is unable to reflect this difference and assigns the same rank to the two nodes.

LCA, which is designed to reveal the effect of accessibility of its neighbors, can discern between COK and JAI (column LCA in Tab. 4). However, the LCA assigns the same rank to multiple locations (AMD, BBI, IXB, IXR, and PNQ), each of which is ranked distinctly by the wLCA metric. BBI has the highest weighted local core accessibility value due to the highest number of connecting flights (31) among these nodes. Note that wLCA ranks IDR and VTZ equally, which is reflected in its monotonicity value, which is less than the perfect score of one. Lower monotonicity of LCA compared to wCA should not be considered a drawback, as they both quantify accessibility at different granularity levels and have different purposes.

Tab. 4

Ranks of airports connected by Air Asia flight (winter schedule 2020),
according to the proposed core-based accessibility measures

Nodes	Degree		Core	CA	wCA	LCA	wLCA	NCA	wNCA
BLR	17	0.1846	5	1	1	1	1	1	1
DEL	16	0.1729	5	1	2	2	2	2	2
BOM	12	0.09	5	1	3	3	3	3	3
CCU	8	0.0713	5	1	4	5	4	5	4
MAA	9	0.0631	5	1	5	4	5	4	5
HYD	6	0.0502	5	1	6	6	6	6	6
GOI	4	0.0467	4	2	7	9	7	9	8
GAU	4	0.0444	3	3	9	10	10	10	10
BBI	3	0.0374	3	3	10	11	11	11	11
IXR	3	0.0362	3	3	11	11	12	11	12
COK	5	0.0304	5	1	8	8	9	8	9
JAI	6	0.0304	5	1	8	7	8	7	7
IXB	3	0.028	3	3	12	11	13	13	13
AMD	3	0.0234	3	3	13	11	14	12	14
PNQ	3	0.0222	3	3	14	11	15	14	15
SXR	1	0.021	1	5	16	13	17	18	19
IDR	2	0.0164	2	4	15	12	16	15	16
VTZ	2	0.0164	2	4	15	12	16	17	17
IMF	1	0.0082	1	5	18	14	19	19	20
IXC	2	0.007	2	4	17	12	18	16	18
Monotonicity	-	-	-	0.57	0.98	0.87	0.99	0.99	1

As mentioned in Section 4.2, the LCA does not capture the recursive impact of accessibility of the neighbor nodes. Intuitively, a node connected to neighbors with high local accessibility should have better network-wide accessibility. We observe that VTZ and IDR are ranked equally for all metrics except NCA. IDR and VTZ have a common neighbor, BLR. But the difference in their rank is attributed to the difference in the local accessibility of their other neighbor, DEL (rank 2) and MAA (rank 4), respectively. This example shows that NCA is a more discerning metric than the LCA.

Observing the column NCA in Tab. 4, we find that BBI and IXR are ranked equally as they are connected to the same nodes in the network. But BBI is ranked higher by weighted network-wide core accessibility (column wNCA) due to more connecting flights. We observe that the wNCA metric has the highest monotonicity (one) and is the most discerning. Since wNCA depends on the wLCA as well as its connectivity in the network (captured by eigenvector centrality), we believe that wNCA will generate unique rankings. However, in the unlikely case of duplicate ranks of two nodes, both are considered to be equally accessible.

5.3 Temporal changes in accessibility

Temporal changes in accessibility provide valuable inputs to the stakeholders of the transport industry. Transport service networks expand (shrink) over time due to addition (reduction) in destinations or increase (decrease) in frequencies of services. The influence of these changes on the accessibility of locations in the network is often not obvious. We demonstrate the utility of weighted metrics to compare and reveal the changes in the accessibility of Indian airports at two different points in time. We use the domestic airlines network for the following two schedules obtained from the Directorate General of Civil Aviation⁹.

1) Pre-covid times: winter schedule 2019 (winter19)[11] for Air Asia, Air India, Alliance Air, Deccan, Go Air, Heritage, Indigo, Pawan Hans, Spicejet, Star Air, Truejet, and Vistara airlines

2) Post-covid times: winter schedule 2020 (winter20)[12] for Air Asia, Air India, Alliance Air, Go Air, Indigo, Pawan Hans, Spicejet, Star Air, Truejet, and Vistara airlines

For constructing the weighted network for all domestic air carriers, we first construct the network for each airline as described in Section 5.2. Thereafter, we sum up the weights of the edges, where the edge weight connotes the minimum frequency of incoming/outgoing flights between pairs of nodes in the network over all air carriers.

Fig. 7 displays the comparison of wLCA and wNCA values of Indian airports in the pre-and post-covid times. The airports are sorted on weighted accessibility values for pre-covid times.

Fig. 7a reveals that the regional accessibility of the top 10 airports has reduced in post-covid times, as expected. This is attributed to the drop in the number of flights to and from these nodes in the winter20 schedule.

Fig. 7b shows the regional accessibility of the bottom 10 airports. It can be seen that six out of the ten least accessible airports are still not accessible (wLCA is zero) due to the non-resumption of flight services. Surprisingly, the regional accessibility of four airports, namely SXV, LUH, IXP, and TEZ, has improved post-covid. The decrease in the overall connectivity in the network led to this improvement . The increase in the frequency of flights between TEZ and IXP in the post-covid schedule further amplifies their wLCA scores.

Fig. 7c shows the change in network-wide accessibility for the top 10 airports in the two periods. The figure reveals the holistic view of the accessibility of domestic airports at two points in time. The resumption of flights in the post-covid schedule has almost restored the accessibility of the top ten airports. For example, we observe a slight improvement in the network-wide accessibility of BLR and HYD, despite a fall in their regional accessibility. The regional accessibility of BLR and HYD reduces post-covid due to the reduction in the flights connecting them in the network. The increase in their network-wide accessibility is attributed to the increase in the accessibility of their neighbors due to the increase in their connectivity with other nodes in the network. However, network-wide accessibility for six of the bottom ten airports is yet to resume (

Fig. 7d). IXP, IXT, and TEZ are exceptions with an increase in their network-wide accessibility post-covid due to the increased frequency of flights.

a) wLCA values of the top 10
Indian airports

b) wLCA values of the bottom 10
Indian airports

c) wNCA values of the top 10
Indian airports

d) wLCA values of the bottom 10
Indian airports

Fig. 7. Comparison of local and network-wide accessibility of airports in
pre-covid (winter19) and post-covid (winter20) times.
Airports are sorted by their local and network-wide accessibility in winter19 times

6. CONCLUSION

In this paper, we propose novel accessibility metrics based on hierarchical decomposition of a transport network. The metrics gauge the accessibility of a geographical location (node in the network) at different granularity levels and are scalable. Different attributes of accessibility, like travel cost, travel time, distance, quality of service, etc., can be quantified as edge weights establishing the versatility of the proposed metrics.

We use the k-core decomposition of the network to elicit the hierarchical position of a node and use it in three different forms to quantify core accessibility (coarse level), local core accessibility (regional level), and network-wide core accessibility (network level). Weighted versions of the metrics capture finer differences between the accessibility of locations that are similarly connected.

Furthermore, we demonstrate the applications of the proposed metric using test networks of Indian Airlines. We also present a case study of the Air Asia network to elucidate the utility, relative advantages, and disadvantages of the proposed metrics. Finally, we show that the measures are responsive to changes in the topology of the transport network by presenting an analysis of changes in accessibility for the domestic air services network for both pre-covid and post-covid times.

References

1. Wu H., D. Levinson. 2020. “Unifying access”. Transp. Res. Part D Transp. Environ. 83.

2. Levinson D., H. Wu. 2020. “Towards a general theory of access.”. J. Transp. Land Use 13(1).

3. Geurs K.T., B. van Wee. 2004. “Accessibility evaluation of land-use and transport strategies: Review and research directions”. J. Transp. Geogr. 12(2).

4. Handy S. 2020. “Is accessibility an idea whose time has finally come?” Transp. Res. Part D Transp. Environ. 83.

5. El-Geneidy A., D. Levinson. 2022. “Making accessibility work in practice”. Transport Reviews 42(2).

6. Levine J. 2020. “A century of evolution of the accessibility concept”. Transp. Res. Part D Transp. Environ. 83.

7. Hansen W.G. 1959. “How Accessibility Shapes Land Use”. J. Am. Plan. Assoc. 25(2).

8. Koenig J.G. 1980. “Indicators of urban accessibility: Theory and application”. Transportation (Amst). 9(2).

9. Ingram D.R. 1971. “The Concept of Accessibility: A Search for an Operational Form”. Reg. Stud. 5(2).

10. Morris J.M., P.L. Dumble, M.R. Wigan. 1979. “Accessibility indicators for transport planning”. Transp. Res. Part A Gen. 13(2).

11. Handy S. 1993. Regional Versus Local Accessibility : Implications for Nonwork Travel. Univ. Calif. Transprtation Cent.

12. Cui M., D. Levinson. 2020. “Primal and Dual Access”. Geogr. Anal. 52(3).

13. Lee J., H.J. Miller. 2020. “Robust accessibility: Measuring accessibility based on travelers’ heterogeneous strategies for managing travel time uncertainty”. J. Transp. Geogr. 86.

14. Hellervik A., L. Nilsson, C. Andersson. 2019. “Preferential centrality – A new measure unifying urban activity, attraction and accessibility”. Environ. Plan. B Urban Anal. City Sci. 46(7).

15. Neutens T., M. Versichele, T. Schwanen. 2010. “Arranging place and time: A GIS toolkit to assess person-based accessibility of urban opportunities”. Appl. Geogr. 30(4).

16. Manaugh K., A. El-Geneidy. 2012. “Who Benefits from New Transportation Infrastructure? Using Accessibility Measures to Evaluate Social Equity in Transit Provision”. Chapter 12. In: Accessibility Analysis and Transport Planning. Edited by Karst T. Geurs, Kevin J. Krizek, Aura Reggiani. ISBN: 9781781000106.

17. Handy S. 2005. “Planning for Accessibility: In: Access to Destinations. Edited by Levinson D.M., Krizek K.J. Emerald Group Publishing Limited, Bingley. ISBN: 9780080446783.

18. Garrison W., D. Marble. 1962. “The Structure of Transportation Networks”. U.S. Army Transp. Command. Tech. Rep. 62-II: 100.

19. Cats O. 2017. “Topological evolution of a metropolitan rail transport network: The case of Stockholm”. J. Transp. Geogr. 62.

20. Hong J., R. Tamakloe, S. Lee, D. Park. 2019. “Exploring the topological characteristics of complex public transportation networks: Focus on variations in both single and integrated systems in the Seoul Metropolitan Area”. Sustain. 11(19).

21. Matisziw T.C., T.H. Grubesic. 2010. “Evaluating locational accessibility to the US air transportation system”. Transp. Res. Part A Policy Pract. 44(9).

22. Du W.B., X.L. Zhou, O. Lordan, Z. Wang, C. Zhao, Y.B. Zhu. 2016. “Analysis of the Chinese Airline Network as multi-layer networks”. Transp. Res. Part E Logist. Transp. Rev. 89.

23. Dai L., B. Derudder, X. Liu. 2018. “The evolving structure of the Southeast Asian air transport network through the lens of complex networks, 1979–2012”. J. Transp. Geogr. 68.

24. Wang Z., D. Luo, O. Cats, T. Verma. 2020. “Unraveling the Hierarchy of Public Transport Networks”. In: 2020 IEEE 23rd International Conference on Intelligent Transportation Systems, ITSC 2020.

25. Wang J., H. Mo, F. Wang, F. Jin. 2011. “Exploring the network structure and nodal centrality of China’s air transport network: A complex network approach”. J. Transp. Geogr. 19(4).

26. Wang K., X. Fu. 2017. “Research on centrality of urban transport network nodes”. In: AIP Conference Proceedings 1839.

27. Sarlas G., A. Páez, K.W. Axhausen. 2020. “Betweenness-accessibility: Estimating impacts of accessibility on networks”. J. Transp. Geogr. 84.

28. Ravasz E., A.L. Barabási. 2003. “Hierarchical organization in complex networks”. Phys. Rev. E - Stat. Physics, Plasmas, Fluids, Relat. Interdiscip. Top. 67(2).

29. Valverde S., R. V Solé. 2007. “Self-organization versus hierarchy in open-source social networks”. Phys. Rev. E - Stat. Nonlinear, Soft Matter Phys. 76(4).

30. Lu C., J.X. Yu, R.H. Li, H. Wei. 2016. “Exploring hierarchies in online social networks”. IEEE Trans. Knowl. Data Eng. 28(8).

31. Gülsoy G., N. Bandhyopadhyay, T. Kahveci. 2012. “HIDEN: Hierarchical decomposition of regulatory networks”. BMC Bioinformatics 13(1).

32. Mengistu H., J. Huizinga, J.B. Mouret, J. Clune. “The Evolutionary Origins of Hierarchy”. PLoS Comput. Biol. 12(6).

33. Weiss B.A., M. Sharp, A. Klinger. 2018. “Developing a hierarchical decomposition methodology to increase manufacturing process and equipment health awareness”. J. Manuf. Syst. 48.

34. Raimbault J. 2020. “Hierarchy and co-evolution processes in urban systems.” 2020.

35. Azimi-Tafreshi N., J. Gómez-Gardeñes, S.N. Dorogovtsev. 2014. “K-core percolation on multiplex networks”. Phys. Rev. E - Stat. Nonlinear, Soft Matter Phys. 90(3).

36. Seidman S.B. 1983. “Network structure and minimum degree”. Soc. Networks 5(3): 269-287.

37. Bickle A. 2010. The k-cores of a graph. Western Michigan University.

38. Batagelj V., M. Zaversnik. 2003. “An O(m) Algorithm for Cores Decomposition of Networks”.

39. Yerra B.M., D.M. Levinson. 2005. “The emergence of hierarchy in transportation networks”. Ann. Reg. Sci. 39(3).

40. Bogũá M., D. Krioukov, K.C. Claffy. 2009. “Navigability of complex networks”. Nat. Phys. 5(1).

41. Wuellner D.R., S. Roy, R.M. D’Souza. 2010. “Resilience and rewiring of the passenger airline networks in the United States”. Phys. Rev. E - Stat. Nonlinear, Soft Matter Phys. 82(5).

42. Bonacich P. 1972. “Factoring and weighting approaches to status scores and clique identification”. J. Math. Sociol. 2(1).

43. Bae J., S. Kim. 2014. “Identifying and ranking influential spreaders in complex networks by neighborhood coreness”. Phys. A Stat. Mech. its Appl. 395.

44. Mohammed J. Zaki, Wagner Meira Jr. 2014. Data Mining and Analysis: Fundamental Concepts and Algorithms. Cambridge University Press.

Received 06.11.2022; accepted in revised form 19.01.2023

Scientific Journal of Silesian University of Technology. Series Transport is licensed under a Creative Commons Attribution 4.0 International License

[1] Department of Computer Science, Hansraj College, University of Delhi, Delhi, India. Email: divya@hrc.du.ac.in. ORCID: 0000-0002-7688-5293

[2] Department of Civil Engineering, and Transportation Research and Injury Prevention Centre (TRIPC), Indian Institute of Technology Delhi, New Delhi, India. Email: rrkalaga@civil.iitd.ac.in.
ORCID: 0000-0002-7229-519X

[3] Department of Computer Science, University of Delhi, Delhi, India. Email: vbhatnagar@cs.du.ac.in.
ORCID: 0000-0002-9706-9340

[6] See Appendix C for formal definition and example.

[7] See Błąd! Nie można odnaleźć źródła odwołania. in Appendix A for codes of states and union territories.

[8] Note that node SK might be connected by some other airline.

[10] In the interest of reproducibility, the code will be made public after the notification.

[11] Schedule during the period Oct'19 - Mar'20.

[12] Schedule during the period Oct'20 - Mar'21.