[Networkit] centrality.ApproxCloseness

Elisabetta Bergamini elisabetta.bergamini at kit.edu
Wed Sep 9 16:50:46 CEST 2015


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. 




More information about the NetworKit mailing list