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: sage-6.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 ncohen)

I hate it that we do not appear in comparisons like the following, just because we are slower than the worst library :-P

http://graph-tool.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 ncohen

  • Branch set to u/ncohen/18137
  • Commit set to 0402abffb7656e123ce64d38e6a8cb8392eecf89
  • Status changed from new to needs_review

New commits:

7b63297trac #18137: Add new centrality module
0402abftrac #18137: keep only the 'double' version, get rid of the rationals

comment:2 follow-up: Changed 5 years ago by dcoudert

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 pre-compute the ((n-1)*(n-2)), although its minor improvement.
  • You could add cdef double x
  • Variables k and d are not used.
  • You wrote from centrality import centrality_betweenness. Shouldn't it be from sage.graphs.centrality import centrality_betweenness ?

comment:3 in reply to: ↑ 2 Changed 5 years ago by ncohen

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 pre-compute the ((n-1)*(n-2)), 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 and d are not used.

Done.

  • You wrote from centrality import centrality_betweenness. Shouldn't it be from 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 git

  • Commit changed from 0402abffb7656e123ce64d38e6a8cb8392eecf89 to 47291d7a004cef908625eeb40ac3997645a7cce3

Branch pushed to git repo; I updated commit sha1. New commits:

47291d7trac #18137: Review

comment:5 Changed 5 years ago by chapoton

there is numerical noise, add tolerance, see patchbot report.

comment:6 Changed 5 years ago by chapoton

  • Status changed from needs_review to needs_work

comment:7 Changed 5 years ago by git

  • Commit changed from 47291d7a004cef908625eeb40ac3997645a7cce3 to 421dc01c948b631dd227c17aeba0459080293b94

Branch pushed to git repo; I updated commit sha1. New commits:

421dc01trac #18137: Numerical noise

comment:8 Changed 5 years ago by ncohen

  • 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 ncohen

  • Description modified (diff)
Note: See TracTickets for help on using tickets.