[Networkit] Centrality algorithms on directed graphs

Elisabetta Bergamini elisabetta.bergamini at kit.edu
Sun Jan 18 13:56:33 CET 2015


Hi Lorenzo,

You are right, the DynBetweenness algorithm supported only undirected graphs.
You can now download the latest version with support for weighted graphs from the repository. If you could test it again on your instances, that would be helpful.
However, please notice that the dynamic betweenness algorithms have been implemented mainly for a comparison purpose and their speedups on the static algorithm are not always good (in particular on weighted graphs). 
The dynamic approximation algorithm instead has very good speedups compared to the static approximation ones, we’ll add support for directed graphs as soon as possible. Are your graphs small enough that you can compute exact betweenness on them or do you need an approximation?

Best,

Elisabetta


On 07 Jan 2015, at 11:57, Lorenzo Severini <lorenzo.severini at gssi.infn.it> wrote:

> 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
> 
> 
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150118/fa49bd15/attachment.html>


More information about the NetworKit mailing list