Opened 5 years ago
Last modified 5 years ago
#18137 closed enhancement
Centrality betweenness in Sage — at Version 9
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.6 
Component:  graph theory  Keywords:  
Cc:  dcoudert, borassi  Merged in:  
Authors:  Nathann Cohen  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/ncohen/18137 (Commits)  Commit:  421dc01c948b631dd227c17aeba0459080293b94 
Dependencies:  Stopgaps: 
Description (last modified by )
I hate it that we do not appear in comparisons like the following, just because we are slower than the worst library :P
http://graphtool.skewed.de/performance
With this branch we can compute the betweenness centrality in Sage with a decent speed.
Nathann
P.S.: The version of the code that deals with rational instead of floats has been removed because it is *much* slower (60x in some cases), and because I did not see how to make the two coexist without copy/pasting most of the code.
Change History (9)
comment:1 Changed 5 years ago by
 Branch set to u/ncohen/18137
 Commit set to 0402abffb7656e123ce64d38e6a8cb8392eecf89
 Status changed from new to needs_review
comment:2 followup: ↓ 3 Changed 5 years ago by
Hello,
I have only small remarks:
 Wouldn't it be slightly faster to use arrays of bint rather than bitsets ? It would use more memory, but since you want to be fast, any saving is important.
 You could add a doctest to compare the result of your implementation with networkx
 You could precompute the
((n1)*(n2))
, although its minor improvement.  You could add
cdef double x
 Variables
k
andd
are not used.  You wrote
from centrality import centrality_betweenness
. Shouldn't it befrom sage.graphs.centrality import centrality_betweenness
?
comment:3 in reply to: ↑ 2 Changed 5 years ago by
Hello,
 Wouldn't it be slightly faster to use arrays of bint rather than bitsets ? It would use more memory, but since you want to be fast, any saving is important.
It would not be much faster, because most of what this array would contain is zeroes (bint is an int in memory). Plus the bottleneck is float computation in this case :/
 You could add a doctest to compare the result of your implementation with networkx
There is one, isn't there? In centrality.pyx
. The one with a "tolerance" flag.
 You could precompute the
((n1)*(n2))
, although its minor improvement.
I don't think that it is worth it. Save a linear number of multiplications after all this work, really?.. :P
 You could add
cdef double x
Done.
 Variables
k
andd
are not used.
Done.
 You wrote
from centrality import centrality_betweenness
. Shouldn't it befrom sage.graphs.centrality import centrality_betweenness
?
They are in the same folder, so it works. It is even more robust as a result, as we can move them wherever we want and the path does not change.
I also changed a Cython flag which checks for exceptions when doing float divisions.
Nathann
comment:4 Changed 5 years ago by
 Commit changed from 0402abffb7656e123ce64d38e6a8cb8392eecf89 to 47291d7a004cef908625eeb40ac3997645a7cce3
Branch pushed to git repo; I updated commit sha1. New commits:
47291d7  trac #18137: Review

comment:5 Changed 5 years ago by
there is numerical noise, add tolerance, see patchbot report.
comment:6 Changed 5 years ago by
 Status changed from needs_review to needs_work
comment:7 Changed 5 years ago by
 Commit changed from 47291d7a004cef908625eeb40ac3997645a7cce3 to 421dc01c948b631dd227c17aeba0459080293b94
Branch pushed to git repo; I updated commit sha1. New commits:
421dc01  trac #18137: Numerical noise

comment:8 Changed 5 years ago by
 Status changed from needs_work to needs_review
Another thing for which pathbot save us :P
Thanks,
Nathann
comment:9 Changed 5 years ago by
 Description modified (diff)
New commits:
trac #18137: Add new centrality module
trac #18137: keep only the 'double' version, get rid of the rationals