[Networkit] CoreDecomposition and self-loops

Matteo Riondato 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...
Name: signature.asc
Type: application/pgp-signature
Size: 163 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151003/be22e6eb/attachment.sig>

More information about the NetworKit mailing list