[Networkit] CoreDecomposition and self-loops

Maximilian Vogel maximilian.vogel at student.kit.edu
Wed Oct 14 14:36:00 CEST 2015


On 13.10.2015 11:23, Arie Slobbe wrote:
> My idea of a user-friendly implementation would be to always ignore 
> self-loops. Including self-loops in the core decomposition calculation 
> is definitely a bug and not a feature. Going with this approach, I 
> would make a note in the documentation that self-loops are always ignored.
I think, that this is the way to go.

> For the ParK implementation, I see a simple solution for the self-loop 
> problem. ParK loads a vector with node degrees, and we can simply 
> adjust node degree to account for self-loops. It looks like this will 
> completely solve the problem. I see the same solution for the 
> runWithBucketQueues implementation.
Yes, the implementations remain mainly untouched, just the 
initiliazation of the node degrees needs to be adapted/corrected.

> If I'm careful, I can fix core decomposition despite this underlying 
> issue with Graph.degree(node u). However, if the underlying problem in 
> the Graph class is solved first, my fix in coreDecomposition will look 
> much prettier.
I don't know which solution you exactly have in mind, but I guess a 
Graph::degree(node u, bool ignoreSelfLoops) would be useful. This would 
also make it much easier to adapt the LocalClusteringCoefficient 
implementation for graphs with self-loops.

> Unfortunately the problem in the graph class is over my head. I would 
> be much appreciate if someone more familiar with the Graph class would 
> take a look.
Well, it's a bit of a bigger task, as one has to check all usages of 
Graph::degree() and Graph::weightedDegree() in all algorithms and take 
care of the consequences.


> On Sat, Oct 3, 2015 at 6:58 PM, Matteo Riondato <matteo at cs.brown.edu 
> <mailto:matteo at cs.brown.edu>> wrote:
>     > On Oct 3, 2015, at 4:47 AM, Henning Meyerhenke
>     <henning.meyerhenke at kit.edu <mailto:henning.meyerhenke at kit.edu>>
>     wrote:
>     > I do not have access to the literature right now, how do others
>     handle self-loops in this context?
>     All algorithms for k-core decomposition I know of require a graph
>     without self loops. This may be laziness on the researcher side
>     =), or actually creating problems, e.g., breaking some properties
>     of the k-core.
>     Indeed self-loops break widely “assumed” properties, e.g., that
>     the sum of the degrees is twice the number of edges, unless you
>     define the contribution of an edge to the degree of a vertex as 2…
>     If you consider self-loop in the k-core, you’ll end up having
>     > My recommendation would be to delete self-loops driven by a
>     user-specified flag (yes/no, default = yes??).
>     I suggest that the algorithm should fail unless the user supplies
>     an flag “ignore-self-loops” set to true, and the default for this
>     flag is no. Perhaps that’s what you are suggesting =)
>     Matteo
> _______________________________________________
> 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/20151014/f31d5c78/attachment.html>

More information about the NetworKit mailing list