This repository contains python3 codes reproducing the results and grahpics from the
Paper: [1] Orientations and matrix function-based centralities in multiplex network analysis of urban public transport, K. Bergermann and M. Stoll, Applied Network Science, 6, 90, 2021. https://doi.org/10.1007/s41109-021-00429-9
Most methods rely on the German local public transport GTFS data set (feed version 'light-2021-04-22'), which can be downloaded here (170MB):
Data: https://www.tu-chemnitz.de/mathematik/wire/pubs/gtfsdata.tar.gz
(The codes will expect the data in the directory 'gtfsdata' by default. You may change the location by setting the optional argument 'gtfsDataPath' in the relevant functions to the desired directory.)
In order to be able to execute all scripts, you require the following python packages:
Requirements:
- numpy (tested with versions 1.19.5 and 1.20.3)
- scipy (tested with versions 1.6.2 and 1.6.3)
- pandas (tested with version 1.2.4)
- geopandas (tested with version 0.9.0)
- matplotlib (tested with versions 3.4.1 and 3.4.2)
- osmnx (tested with version 1.1.1)
Version: All codes were tested with Python 3.8.10 on Ubuntu 20.04.2 LTS as well as with Python 3.6.9 on Ubuntu 18.04.5 LTS.
This repository contains:
License:
- LICENSE: GNU General Public License v2.0
Directories:
- adjacency_matrices: contains the inter- and intra-layer adjacency matrices in npz-format (numpy) as well as node and layer lists in csv-format, which are produced by the function 'build_supra_adjacency_matrix'
- centralities: contains plots and results of matrix function-based centrality measures applied to the matrices from the directory 'adjacency_matrices' by functions from the directory 'subroutines/centralities'
- centralities/plots: contains the graphical representation of marginal node and marginal layer centralities generated by the functions 'compute_MCs_varying_omega', 'compute_MLC_plots', and 'compute_MNC_plots'
- centralities/results: contains txt-files of the top k (default value: 10) joint, marginal node, and marginal layer centralities of the centrality measures generated by the function 'compute_centralities'
- orientationPlots: contains the orientation plots generated by the functions 'create_aggregated_bearing_plot' and 'OSMnx_street_orientations'
- shapefiles: contains the shape files (polygons or multipolygons representing the respective city's administrative boundaries of the cities proper (excluding suburban areas)) generated by OSMnx [2]
- subroutines: contains all subroutines NOT directly involved in the computation of matrix function-based centralities
- subroutines/centralities: contains all subroutines involved in the computation of matrix function-based centralities
The results and graphics from [1] can be reproduced by executing the
Main script:
- run_experimets.py
It calls the following functions from the directory 'subroutines'. Please refer to the description in the respective file for more information.
Functions:
- subroutines/build_supra_adjacency_matrix.py: uses the GTFS data to construct node and layer lists as well as the following adjacency matrices: unweighted intra-layer, weighted intra-layer (containing travel times as weights), intra-layer frequencies, and unweighted inter-layer adjacency matrices for a specified city
- subroutines/create_aggregated_bearing_plot.py: uses the GTFS data to generate the public transport network orientations for a specified city
- subroutines/filter_by_polygon.py: filters for stops in the GTFS data set, which are located inside the specified city boundaries using shape files generated by 'OSMnx_shapefiles'
- subroutines/OSMnx_shapefiles.py: uses OSMnx to generate shape files specifying a (multi-) polygon that represents the specified city's boundaries
- subroutines/OSMnx_street_orientations.py: uses OSMnx to generate street network orientation plots of a list of cities specified in the function according to the methodology from [3]
- subroutines/centralities/compute_centralities.py: computes matrix function-based centrality measures applying the methods from 'lanczos', 'fAb', and 'gauss_quadrature_rules' to supra-adjacency matrices constructed from the matrices generated by 'build_supra_adjacency_matrix'
- subroutines/centralities/compute_MCs_varying_omega.py: calls 'compute_centralities' to compute marginal layer and marginal node centralities for a range of coupling parameters omega and plots the resulting centralities in dependence of omega
- subroutines/centralities/compute_MLC_plots.py: calls 'compute_centralities' to compute marginal layer centralities and visualizes them via line plots on top of an OSMxn street network
- subroutines/centralities/compute_MNC_plots.py: calls 'compute_centralities' to compute marginal node centralities and visualizes them via scatter plots on top of an OSMxn street network
- subroutines/centralities/fAb.py: evaluates f(A)b given a tridiagonalization of A as well as a basis for the Krylov subspace of A to the vector b [4]
- subroutines/centralities/gauss_quadrature_rules.py: computes lower and upper bounds on subgraph and resolvent-based subgraph centrality via Gauss quadrature rules, given a tridiagonalization of the symmetric input matrix A [5]
- subroutines/centralities/lanczos.py: implements the Lanczos tridiagonalization scheme for symmetric matrices [6,7]
References:
- [1] K. Bergermann and M. Stoll, Orientations and matrix function-based centralities in multiplex network analysis of urban public transport, Applied Network Science, 6, 90 (2021), https://doi.org/10.1007/s41109-021-00429-9
- [2] G. Boeing, OSMnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks, Computers, Environment and Urban Systems, 65 (2017), pp. 126–139, https://doi.org/10.1016/j.compenvurbsys.2017.05.004.
- [3] G. Boeing, Urban spatial order: Street network orientation, configuration, and entropy, Applied Network Science, 4 (2019), pp. 1–19, https://doi.org/10.1007/s41109-019-0189-1.
- [4] N. J. Higham, Functions of matrices: Theory and computation, SIAM, USA, 2008, https://doi.org/10.1137/1.9780898717778.
- [5] G. H. Golub and G. Meurant, Matrices, moments and quadrature with applications, Princeton University Press, USA, 2009, https://doi.org/10.1515/9781400833887.
- [6] G. H. Golub and C. F. Van Loan, Matrix computations, vol. 3, JHU press, USA, 2013.
- [7] C. Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, United States Governm. Press Office Los Angeles, CA, USA, 1950, https://doi.org/10.6028/jres.045.026.