Roadmap

Done

Unweighted graphs:

• Certain centrality measures
  • Betweenness centrality - using Brandes' algorithm in A Faster Algorithm for Betweenness Centrality (2001) based on Breadth-First Search (BFS).
  • Closeness centrality - using results from the calculation for betweenness.

ToDo

Unweighted graphs:

• In GDMS-Topology, rename ST_ClosenessCentrality to ST_NetworkAnalyzer and output a table of nodes with the geometry (?), node id, betweenness and closeness values. For now, ST_ClosenessCentrality stores just the node id and the closeness in a table.
• Other network parameters: See NetworkAnalyzer for a list of possibilities. Some parameters can only be calculated for directed (or undirected) graphs.
  • Parameters that should be very easy to compute:
    • Degree, in-degree, out-degree
    • Neighborhood connectivity
    • Shortest path length distribution
    • Network diameter
    • Stress centrality (the number of shortest paths passing through a vertex)
    • etc.
  • Slightly more complicated
    • Clustering coefficient
    • Shared neighbors
    • Topological coefficient
    • etc.

Weighted graphs:

• Betweenness centrality
  • Both JGraphT-SNA and NetworkAnalyzer compute betweenness only for unweighted graphs using Brandes.
  • Modify Brandes' algorithm by replacing BFS with another one-to-many shortest paths algorithm to find (and count) all shortest paths (not just one). Options:
    1. Old-fashioned: Dijkstra (see the end of the Pseudocode section), A*, Floyd-Warshall, or Johnson (better for sparse graphs).
    2. More recent: Hierarchical methods
       • See especially Engineering Route Planning Algorithms for a survey of recent developments in route planning techniques in transportation networks up to 3 million times faster than Dijkstra.
       • See the Fast and Exact Route Planning website for information on contraction hierarchies (CH). This recent technology (based on Robert Geisberger's thesis [Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks] thesisGeisberger (July 1, 2008; 70 pages), combined with a modified bidirectional Dijkstra search, is probably the fastest way to calculate all-pairs shortest paths. This research group already implemented CHs in C++.
         • The best Java implementation of CHs seems to be GraphHopper. The problem is that the GraphHopper implementation is giving slower results using CHs than JGraphT-SNA does using a simple Dijkstra search. The source code is not very well documented. It would probably be best to write my own implementation.
         • See video lectures 6 and 7 of the Efficient Route Planning course (summer 2012). In the corresponding exercises, students are asked to implement CHs.
         • Parallelized version: See Christian Vetter's paper Parallel Time-Dependent Contraction Hierarchies (July 13, 2009). In his diploma thesis [Fast and Exact Mobile Navigation with OpenStreetMap Data][] (March 1, 2010; 78 pages), Vetter developed the C++ mobile routing application MoNav based on CHs using OpenStreetMap data.
       • Also see the Route Planning in Transportation Networks research group for a long list of publications and recent advances.
       • See Route Planning in Road Networks and Dominik Schultes' thesis (February 7, 2008; 235 pages) of the same name for the following:
         • Highway hierarchies
         • Highway-node routing
         • Transit-node routing
• Other centrality measures and network parameters (just as for unweighted graphs).