graphlab-code/graphlab — pull request #149 by dmcennis (2014-07-28 01:34:42+00:00)
Title: Djikstra, Betweeness, Closeness, and Prestige

The Djisktra app creates simultaneously about 3000 shortest path trees from random starting points. Time complexity is about O(l) where l is the number of links in total computations, with actual run-time about O(d) where d is the diameter of the graph.

The Betweeness app creates djikstra trees, then creates an approximate betweeness node score where ratios between nodes have a confidence interval of around +/- 3%. Total computation time for betweeness evaluation is O(n) in total computations with actual run-time being approximately O(d) where d is the diameter of the graph.

The Closeness and Prestige apps create djiskstra trees, then estimate closeness and prestige with a confidence interval of around +/-3%. Time complexity is the same as for betweeness.

Enjoy :-).