[Networkit] CoreDecomposition and self-loops
matteo at cs.brown.edu
Sun Oct 4 01:58:46 CEST 2015
> 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 =)
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 163 bytes
Desc: Message signed with OpenPGP using GPGMail
More information about the NetworKit