[Networkit] Centrality algorithms on directed graphs

Christian Staudt 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,
> Lorenzo

Hi,

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;

	example command: 
		In [15]: %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;

	example command: 
		In [16]: %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;

	example command:
		In [17]: %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.

	example command:  
		In [4]: %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;

	example command:
		In [5]: %time centrality.SciPyPageRank(G).run().ranking() 
	
- SciPyEVZ: running; results need verification

	example command:
		In [3]: %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?


Best,
Chris 





More information about the NetworKit mailing list