[Networkit] Read simple edgelist

Christian Staudt christian.staudt at kit.edu
Wed Sep 30 11:14:30 CEST 2015


On 28 Sep 2015, at 22:36, Maximilian Vogel <maximilian.vogel at student.kit.edu> wrote:

>> So is there a good parallelized SNA program out there that I should consider for a good implementation of parallalized centrality measures?
> We once benchmarked most of our implementations and compared them with other frameworks, however I can't find them right now. Maybe, Christian has them somewhere. Either we are better or you'd get to know better frameworks... ;-)

An early paper on NetworKit [2] contains some comparative benchmarks, but they are outdated by now: Several NetworKit kernels have become faster.


> When using ApproxBetweenness2 or ApproxCloseness (both sequential), you have to specify the number of samples and this directly relates to the running time. Unfortunately I don't know how many samples to choose to get "reasonable" results.


What a “reasonable” approximation is is a good but tricky question. I think we can’t answer this independently of an application and an application-specific cost/benefit analysis. Here is what we know:

- centrality.ApproxBetweenness (Riondato/Kornaropoulos) accepts a parameter epsilon such that the absolute values are at most epsilon off from the exact betweenness. The good thing is that you have this guarantee and you do not have to estimate the number of samples directly. The bad thing is that a) the benefit of an additive error bound on betweenness (which is a fraction) is debatable, and b) in order to hold this provable guarantee, the algorithm is somewhat less efficient than it could be.
- centrality.ApproxBetweenness2 (Sanders/Geisberger) computes more efficiently, but you have to estimate the number of samples and you get no proven error bound. I recommend this as the default, because efficiency trumps additive error bound when doing exploratory analysis.
- In experiments, we have seen that both algorithms preserve the ranking of nodes by betweenness quite well with few samples. The error is usually far lower than the given bound for ApproxBetweenness, and it is lower the higher the betweenness of a node [1].


[1]: https://www.researchgate.net/publication/265967336_Approximating_Betweenness_Centrality_in_Large_Evolving_Networks
[2]: https://www.researchgate.net/publication/260756093_NetworKit_An_Interactive_Tool_Suite_for_High-Performance_Network_Analysis

Best,
Chris
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150930/0f1f0d26/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150930/0f1f0d26/attachment.sig>


More information about the NetworKit mailing list