[Networkit] centrality.ApproxCloseness

Arie Slobbe aslobbe at macalester.edu
Wed Sep 9 16:24:56 CEST 2015


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.

On Wed, Sep 9, 2015 at 4:41 AM, Christian Staudt <christian.staudt at kit.edu>
wrote:

> Quick fix: The constructor should check for connectedness and throw an
> exception otherwise. Because that is relatively expensive and connectedness
> might already be known at this point, the check should be optional, but on
> by default (bool checkConnectedness=true in the constructor)
>
> Long-term solution: All closeness algorithms should implement the extended
> definition of closeness (which turns into to standard closeness in the
> connected case), because real inputs are often not connected. I also think
> there are scenarios in which it makes sense to compare closeness across
> components.
>
> I’ve fixed it for now. Are you going to implement the long-term solution?
> Please remove the check if you do.
>
> On 09 Sep 2015, at 11:05, Elisabetta Bergamini <
> elisabetta.bergamini at kit.edu> wrote:
>
> It’s not supposed to work on disconnected graphs (closeness is defined
> only on connected graphs).
> I agree that an exception should be thrown.
>
> However, there are extensions of the definition of closeness that work
> also for disconnected graphs, e.g.:
> c(v) = (r(v)-1)^2/((n-1)*f(v)), where r(v) is the number of node reachable
> from v and f(v) is the sum of the distances from v to these nodes.
>
> We could either implement that (also in Closeness, not only in
> ApproxCloseness) or restrict ourselves to connected graphs and throw an
> exception.
>
>
> On Sep 9, 2015, at 10:43, Christian Staudt <christian.staudt at kit.edu>
> wrote:
>
> Is that supposed to work on disconnected graphs? An example output for
>
> centrality.ApproxCloseness(G, 42).run().scores()
>
> on a disconnected graph looks like this:
>
> [inf,
>  inf,
>  inf,
>  inf,
>  inf,
>  0.00525,
>  inf,
>  0.008571428571428572,
>  0.07,
>  inf,
>  0.21,
>  inf,
>  inf,
>  0.006885245901639345,
>  0.011052631578947368,
>  0.105,
>  inf,
>  inf,
>
> Maybe that is on purpose. If not it should throw an exception. Could we
> please clarify this?
>
> Best,
> Chris
>
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>
>
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>
>
>
> _______________________________________________
> 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/7b8a1c38/attachment.html>


More information about the NetworKit mailing list