Roadmap

Done

Unweighted graphs:

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

ToDo

Unweighted graphs:

• Other network parameters

Weighted graphs:

• Betweenness centrality
  • Both JGraphT-SNA and NetworkAnalyzer (also here) 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). It would probably be best to write my own implementation. Options:
    1. Dijkstra's algorithm (see the end of the Pseudocode section), A*, Floyd-Warshall, or Johnson (better for sparse graphs).
    2. See [Fast and Exact Route Planning][] for information on contraction hierarchies (CH). This recent technology (based on Robert Geisberger's [thesis][thesisGeisberger] (July 1, 2008; 70 pages), combined with a bidirectional Dijkstra search, is probably the fastest way to calculate all-pairs shortest paths.
       • CHs are already implemented in [GraphHopper][]. The problem is that the GH implementation is giving slower results using CHs than JGraphT-SNA using a simple Dijkstra search.
       • See video lectures 6 and 7 of the 2012 [Efficient Route Planning][] course (summer 2012). In the corresponding exercises, students are asked to implement CH.
       • Parallelized version: See Christian Vetter's paper [Parallel Time-Dependent Contraction Hierarchies][] (2009).
    3. Also see the [Route Planning in Transportation Networks][] research group for a long list of publications and recent advances.
    4. See [Route Planning in Road Networks] and Dominik Schultes' [thesis][thesisShultes] (February 7, 2008; 235 pages) of the same name for the following:
       • Highway hierarchies
       • Highway-node routing
       • Transit-node routing

[thesisGeisberger]: [Fast and Exact Route Planning]: http://algo2.iti.kit.edu/routeplanning.php [GraphHopper]: https://github.com/graphhopper/graphhopper [Efficient Route Planning]: http://ad-wiki.informatik.uni-freiburg.de/teaching/EfficientRoutePlanningSS2012 [Parallel Time-Dependent Contraction Hierarchies]: http://algo2.iti.kit.edu/english/1588.php [Route Planning in Transportation Networks]: http://i11www.iti.uni-karlsruhe.de/en/projects/route_planning/index [Route Planning in Road Networks]: http://algo2.iti.uka.de/schultes/hwy/ [thesisShultes]: http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf