Roadmap

Done

Unweighted graphs:

• Certain centrality measures
  • Betweenness centrality - using Brandes
  • 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:
    • Dijkstra's algorithm. See the end of the Pseudocode section.
    • A*
    • Floyd-Warshall
    • Johnson (better for sparse graphs).
    • Contraction hiearchies?
      • The problem is that the GraphHopper implementation is giving slower results using contraction hierarchies than JGraphT-SNA using a simple Dijkstra.