/MultiOT

Optimal transport on Multilayer networks

Primary LanguageJupyter NotebookGNU General Public License v3.0GPL-3.0

MultiOT (Optimal Transport Dynamics on Multilayer Networks)

Code style: black

Python implementation of the MultiOT algorithm employed and developed in:

This is a an algorithm that uses Optimal Transport theory to extract optimal paths in multilayer networks. Such a task is carried out accordingly to the mathematical frameworks formulated in the works above.

If you use this code please adequately cite the references provided.

Table of Contents

What's included

  • main.py: main function of MultiOT that controls all methods contained in src/.
  • src/: source folder containing all core methods.
  • dashboard.ipynb: tutorial notebook with a basic usage of the code.
  • data/input/real_data: contains all data needed to perform simulations on the Copenhagen's transportation network [4].
  • data/output/synthetic/: default output directory to serialize results of the algorithm.
  • setup.py: setup file to build the Python environment.
  • utils.ipynb: functions used by dashboard.ipynb.
  • misc/: files used for the README.md.

[4] Michael Szell, Urban bicycle networks, existing and synthetically grown (1.0.0). Zenodo (2021).

How to use

Requirements

All the dependencies needed to run the algorithms can be installed using setup.py, in a pre-built conda environment. In particular, this script needs to be executed as:

python setup.py

Code usage

To download this repository, copy and paste the following line in your terminal:

git clone https://github.com/cdebacco/MultiOT

You are ready to test the code! If you want to know how, click HERE to test it on a notebook.

Code details

Input & Output

The algorithm's main inputs are:

  • G: the multilayer network.
  • S: the mass matrix containing the mass entry and exit distributions.
  • w: the edges weights (Euclidean lengths that are weighted by the code [1-3]).

For Copenhagen's transportation network, these inputs are serialized in data/input/real_data/copenhagen_{network,S,w}.pkl. For synthetic graphs they are automatically generated by the code.

Methods

  • src/dynamics.py: Multicommodity dynamics on multilayer networks [1,2]
    This is a scheme capable of finding optimal multicommodity fluxes on multilayer network networks by solving a dynamical system of equations where different commodities interact and share a unique infrastructure. Traffic congestion can be tuned by means of a critical exponent (beta) which can set to be different at every layer.

  • src/dynamics_sp.py: Shortest path dynamics on multilayer networks [3]
    This method can be employed to find shortest path fluxes on multilayer network networks by solving a dynamical system of equations.

  • src/dijkstra.py: Multi-source multi-sink Dijkstra's algorithm on multilayer networks [3]
    This script contains a multi-source multi-sink implementation of Dijkstra's algorithm where all Origin-Destination paths are found iteratively using a single-source single-sink Dijkstra.

  • src/filtering.py: Shortest path filtering on multilayer networks
    This scheme allows to refine results extracted by src/dynamics_sp.py. Particularly, network paths containing loops (possibly arising when the convergence thresholds are not properly tuned) can be eliminated by re-running src/dynamics_sp.py or src/dijkstra.py on the subgraphs supporting each commodity's fluxes.

Parameters

The main parameters used by main.py to run the code are (together with their data types as requested per input by the algorithm):

  • topol (str): Type of network topology, can be 'synthetic' or 'real'.
  • Ns (str): Number of nodes in each layer.
  • betas (str): Critical exponents in each layer.
  • ws (str): Inverse velocity for all layers (also referred to as alpha for effective lengths).
  • p (float): Monocentric/random inflows of mass for synthetic networks.
  • V (bool): Verbose flag for additional output.
  • Vtimestep (int): Frequency when to print algorithm metadata.
  • relax (float): Relaxation of Laplacian pseudoinverse.
  • delta (float): Discrete time step.
  • delta_filtering (float): Discrete time step for filtering.
  • tot_iterations (int): Maximum iteration limit for the algorithm.
  • epsilonmu (float): Convergence threshold for conductivities/capacities.
  • epsilonJ (float): Convergence threshold for OT cost.
  • epsilonmu_filtering (float): Convergence threshold for conductivities/capacities in filtering.
  • epsilonJ_filtering (float): Convergence threshold for OT cost in filtering.
  • tau_filtering (float): Threshold to trim fluxes in dynamics filtering.
  • seedG (int): Seed for random graph generation.
  • seedmu (int): Seed for random noise initialization of conductivities.
  • seedS (int): Seed for random choice of sources/sinks.
  • dynamics_flag (bool): Flag to run multi-commodity dynamics.
  • dynamics_sp_flag (bool): Flag to run shortest path dynamics.
  • dijkstra_flag (bool): Flag to run multi-source multi-sinks Dijkstra's algorithm.
  • filtering_flag (bool): Flag to run filtering.
  • ifolder (str): Input folder containing data.
  • ofolder (str): Output folder for storing results.

Additional files

  • src/initialization.py: Initialize all variables needed for the core methods.
  • src/generate_planar.py: Generates a multilayer networks by connecting multiple planar networks, one per layer.
  • src/tools.py: Miscellaneous functions used by the core scripts.

Visualizations

Bordeaux



Copenhagen


Contacts

For any issues or questions, feel free to contact us: