[Networkit] Centrality algorithms on directed graphs
christian.staudt at kit.edu
Mon Jan 5 19:26:15 CET 2015
Am 02.01.2015 um 10:51 schrieb Meyerhenke, Henning (ITI) <henning.meyerhenke at kit.edu>:
> Dear Henning,
> thank you, I tried the C++ version and it works.
> Furthermore, I would like to know if centrality algorithms (in
> particular betweenness algorithms) work properly on directed graphs.
> Best Regards,
our centrality algorithms have not been tested enough on *directed* graphs. I’ve run a small test of these algorithms, with the following results:
test graph: G = generators.ErdosRenyiGenerator(100, 0.1, directed=True).generate()
- Betweenness: running;
In : %time centrality.Betweenness(G).run().ranking()
CPU times: user 2.65 ms, sys: 276 µs, total: 2.93 ms, Wall time: 1.14 ms
- ApproxBetweenness: running;
In : %time centrality.ApproxBetweenness(G).run().ranking()
CPU times: user 336 ms, sys: 2.01 ms, total: 338 ms Wall time: 88.7 ms
- ApproxBetweenness2: running;
In : %time centrality.ApproxBetweenness2(G, 10).run().ranking()
CPU times: user 306 µs, sys: 1 µs, total: 307 µs Wall time: 314 µs
The betweenness algorithms are all based on shortest path kernels (BFS or Dijkstra), which simply compute directed shortest paths in this case. I assume the results are therefore correct, but we need to verify this with additional unit tests.
- PageRank: running extremely slow, looks like an infinite loop ; we should consider this a major bug, because PageRank is expected to work on directed graphs.
example command: %time centrality.PageRank(G, 0.85).run().ranking()
- EigenvectorCentrality: running, but surprisingly slow; results need validation.
In : %time centrality.EigenvectorCentrality(G).run().ranking()
CPU times: user 7.6 s, sys: 14.5 s, total: 22.1 s Wall time: 15.4 s
- SciPyPageRank: error, ZeroDivisionError: float division by zero;
In : %time centrality.SciPyPageRank(G).run().ranking()
- SciPyEVZ: running; results need verification
In : %time centrality.SciPyEVZ(G).run().ranking()
CPU times: user 18 ms, sys: 1.54 ms, total: 19.6 ms Wall time: 18.4 ms
@ authors of the respective classes: please review your implementation if needed and improve test coverage.
@ Lorenzo: If you can verify that the working algorithms give you sensible results, that would be very helpful.
@ Max: Can you please file the bugs/ToDos into our tracker?
More information about the NetworKit