[Networkit] CoreDecomposition and self-loops

Arie Slobbe aslobbe at macalester.edu
Tue Oct 13 11:23:47 CEST 2015


Hello,

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.

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.

However, there might be an issue. Over the summer I discovered an issue
with degree counts for graphs with self-loops, and this issue hasn't been
fixed yet. Some quick testing with iPython shows that Graph.degree(node u)
behaves as expected for directed graphs with self-loops, but the same
command undercounts degrees for nodes with self-loops in undirected graphs.
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.
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.

Arie



On Sat, Oct 3, 2015 at 6:58 PM, Matteo Riondato <matteo at cs.brown.edu> wrote:

>
> > On Oct 3, 2015, at 4:47 AM, Henning Meyerhenke <
> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151013/a0e51553/attachment.html>


More information about the NetworKit mailing list