[Networkit] Inconsistencies in centrality.DegreeCentrality

Maximilian Vogel maximilian.vogel at student.kit.edu
Mon Jun 13 22:37:08 CEST 2016


Hi,


On 07.06.2016 14:57, Elisabetta Bergamini wrote:
> Hi Max,
>
> Thanks for raising this issue. Here’s what I think:
>
> On Jun 7, 2016, at 11:19, Maximilian Vogel 
> <maximilian.vogel at student.kit.edu 
> <mailto:maximilian.vogel at student.kit.edu>> wrote:
>
>> I'd take care of the necessary changes once we settled on the desired 
>> behaviour.
>>
>>   * For the first issue I suggest to add a flag
>>     calledignoreSelfloops=Trueto decide whether to normalize
>>     withnorn-1. This could also be automatically detected by
>>     callingG.hasSelfloops().
>>
> I would be in favor a flag ignoreSelfloops that specifies whether we 
> should count self loops in the degree of a node and whether we should 
> normalize to n or n-1 (the two should be coherent). Personally I don’t 
> like the idea of detecting this automatically with G.hasSelfloops(), 
> because the user might want to assume that there can be self loops, 
> even if the particular graph he’s computing degree centrality on 
> doesn’t have any.
I've done and pushed 
<https://algohub.iti.kit.edu/parco/NetworKit/NetworKit/changeset/8a06b4937e1be68919beb0092bdccf9af3182c1b> 
the necessary changes. Maybe, someone could take a look at them or test it.

>>   * For directed graphs another flag should be added that the user
>>     can choose between in- our out-degree. Is it of interest/use to
>>     offer also a combined degree centrality?
>>
> I agree about the flag for the in- and out- degree, not sure whether a 
> combined version could be useful.
Maybe I have a use-case, but as long as I'm not sure and nobody else 
waves his hand wanting this, I won't add it.

> I think we should have something similar also for closeness: at the 
> moment it is based on distances FROM a node x TO other nodes (and not 
> the other way around), but I think this is also something the user 
> should be able to specify.
> For that, we could either use G.transpose() (although this would be 
> less efficient and would require to keep two versions of the graph) or 
> modify the SSSP and make it possible to run it on the transposed 
> graph, which should be more efficient and could be useful also for 
> other applications, although it would make the SSSP class even more 
> complicated than it already is. Any thoughts on that?
I think you are right about both things. Keeping two graphs is less 
efficient and shouldn't be necessary at all, but adding another flag to 
the SSSP class would make more bloated, unreadable and harder to 
maintain. I don't see a clean solution yet.

Best,
Max
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/20160613/ce65fab0/attachment.html>


More information about the NetworKit mailing list