[Networkit] Centrality algorithms on directed graphs

Lorenzo Severini lorenzo.severini at gssi.infn.it
Wed Jan 7 11:57:54 CET 2015


Hello,

I've run small test on betweenness algorithms (both exact and 
approximated) and it works properly.

However, I tried the DynBetweenness algorithm and it seems to me not 
working properly (after an addition of an edge (u,v), it returns higher 
betweenness score of u w.r.t. the exact algorithm)

Best Regards,
Lorenzo Severini



Il 05/01/15 19:26, Christian Staudt ha scritto:
> 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
>
>

-- 
Lorenzo Severini

PhD Student in Computer Science

Gran Sasso Science Institute
L'Aquila (AQ) - Italy




More information about the NetworKit mailing list