#19031: New Algorithm for Top-K Closeness Centralities
-------------------------------------+-------------------------------------
Reporter: borassi | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.9
Component: graph theory | Resolution:
Keywords: Closeness | Merged in:
Centrality, top-k | Reviewers:
Authors: Michele Borassi | Work issues:
Report Upstream: N/A | Commit:
Branch: | a83cdf0e44dfc33e2b0215da7a926bd13dd1bc5c
u/borassi/new_algorithm_for_top_k_closeness_centralities| Stopgaps:
Dependencies: #19007,#19014 |
-------------------------------------+-------------------------------------
Comment (by borassi):
Replying to [comment:6 dcoudert]:
> A first round of comments.
>
> In method `_estimate_reachable_vertices_dir`
> - `The lower bound is stored in reachableL[v]` -> `The lower bound is
stored in reachL[v]`
Done!
> - Although the method will not be tested, could you please add an
`INPUT` section specifying the type and expected size of arrays. You could
also briefly document the algorithm implemented in the method.
Done!
> - please improve the presentation of the block with all variable
declarations. It is hard to read since it constains lots of important
calls to various methods. For instance avoid `cdef int i, nscc =
tarjan_strongly_connected_components_C`and prefer `cdef int nscc =
tarjan_strongly_connected_components_C`
Done!
> - What's the need for using type `uint64_t` instead of `int`? the
corresponding variables are later cast to `int`.
Well, it's a bit tricky. The point is that in the recursion for
`reachU_scc` I might find values that are much bigger than `g.n`. Since I
did not want to test at each step if this occurs, I used `uint64_t` in
order to avoid overflow (these values are smaller than `g.n^2`). Then,
only at the end, I use min (so that now the values do not overflow), and I
set `reachU[i] = <int> min(reachU_scc[scc[i]], g.n)`. However, you are
right with `reachL`, and I modified it.
> - You could use `maxscc = max(scc_sizes[i] for i in range(nscc)`
I don't think so, `maxscc` is not the maximum size of a SCC, but it is the
SCC with maximum size. In other words, your instruction outputs
`scc_sizes[maxscc]`, not `maxscc`. Am I missing something?
> For method `_compute_reachable_vertices_undir`, you should add some
documentation at the beginning of the method.
Done
> Method counting sort: no comment, but in the future we should certainly
create a method somewhere.
Agree!
> In method `def centrality_closeness_top_k(G, int k=1, int verb=0)`
> - `verb` -> `verbose`
Done!
> - the tests for the validity of the results are excessive. There is no
need for the loop `range(1000)`. Testing for *one* randomly chosen graph
with say `n=20` nodes and `random.randint(1, n*(n-1) / 2)` edges is
sufficient.
Done! I left it because I had to test it 100,000 times to find the last
bug...
> - we can do that `for x in sorted_vert[:n]:` when `sorted_vert` is an
array of ints ???
Yep: !http://docs.cython.org/src/reference/language_basics.html
> - `if directed: gamma = 0 else: gamma = 1 ` -> `gamma = 0 if directed
else 1`
Done!
> - when `stopped == True` you don't quit the `for j in
range(layer_current_beginning,layer_current_end):`. May be you should
replace this loop with a while.
I added an 'if' at the end of the loop.
> - you set `gamma = 0`. So you need `gamma==1` only once for undirected
graphs. Correct?
Hmm, correct, but I realized that I could do a little better by slightly
changing the implementation. So this does not apply anymore.
--
Ticket URL: <http://trac.sagemath.org/ticket/19031#comment:7>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
