#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 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]`
- 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.
- 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`
- What's the need for using type `uint64_t` instead of `int`? the
corresponding variables are later cast to `int`.
- You could use `maxscc = max(scc_sizes[i] for i in range(nscc)`
For method `_compute_reachable_vertices_undir`, you should add some
documentation at the beginning of the method.
Method counting sort: no comment, but in the future we should certainly
create a method somewhere.
In method `def centrality_closeness_top_k(G, int k=1, int verb=0)`
- `verb` -> `verbose`
- 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.
- we can do that `for x in sorted_vert[:n]:` when `sorted_vert` is an
array of ints ???
- `if directed: gamma = 0 else: gamma = 1 ` -> `gamma = 0 if directed
else 1`
- 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.
- you set `gamma = 0`. So you need `gamma==1` only once for undirected
graphs. Correct?
David.
--
Ticket URL: <http://trac.sagemath.org/ticket/19031#comment:6>
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.
