[Networkit] centrality.ApproxCloseness

Arie Slobbe aslobbe at macalester.edu
Wed Sep 9 18:02:16 CEST 2015


oops - I forgot to fill out the password after pushing! My changes should
be up now.

Good point about the node ranking. If you're going to work off of the
changes that were made to the class, then perhaps we should revert my
changes. I'm sorry that you're being the one having to clean up after me!

On Wed, Sep 9, 2015 at 9:50 AM, Elisabetta Bergamini <
elisabetta.bergamini at kit.edu> wrote:

> Hi Arie,
>
> I can’t see your changes in the Dev branch.
> Anyway, the division by zero is certainly a problem (it can happen every
> time a connected component is not “covered” by any of the sampled source
> nodes, i.e. if there’s a component from which no source node is selected).
> In addition to that, the approximation algorithm (and also the exact one)
> is defined *only* on connected graphs. If we just applied the algorithm as
> it is now to disconnected graphs, the ranking of nodes wouldn’t make sense
> (nodes in a small component would get a very high closeness because their
> distance to the nodes they can reach is of course very small).
> That’s why, if we want to handle disconnected graphs, we have to use the
> extended definition of closeness that I posted in my previous mail (which
> intuitively gives less importance to nodes in a small component). I can
> take care of that in the next days.
> Best,
>
> Elisabetta
>
> On Sep 9, 2015, at 16:24, Arie Slobbe <aslobbe at macalester.edu> wrote:
>
> > I found the bug. The problem was not so much disconnected components,
> but isolated nodes. For isolated nodes, problem was caused by division by
> zero. I fixed the bug and added a test case for disconnected components.
> ApproxCloseness should now be fixed in the Dev branch.
>
>
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150909/f4ade46b/attachment.html>


More information about the NetworKit mailing list