[Networkit] centrality.ApproxCloseness

Christian Staudt christian.staudt at kit.edu
Wed Sep 9 11:41:51 CEST 2015


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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150909/a213509e/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150909/a213509e/attachment.sig>


More information about the NetworKit mailing list