[Networkit] CoreDecomposition and self-loops
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>>
> > 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 =)
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the NetworKit