kcore_decomposition using out degree

Dear all,

I am wondering how exactly the k-core decomposition for directed network is
defined in graph-tool.

With the following network:

Gt = gt.Graph(directed=True)
Gt.add_edge_list([(1, 0),(2, 0),(2, 1),(3, 1),(3, 0),(4, 0),(4, 1),(5, 1),
                  (5, 0),(6, 0),(6, 1),(7, 4),(7, 0),(8, 3),(8, 0),(9, 0),
                  (9, 2),(10, 2),(10, 3),(11, 2),(11, 3),(12, 5),(12, 3),
                  (13, 2),(13, 12),(14, 11),(14, 0)])

The k-core decomposition is:

print(gt.kcore_decomposition(Gt, 'in').a)

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

print(gt.kcore_decomposition(Gt, 'out').a)

[10 5 4 4 1 1 0 0 0 0 0 1 1 0 0]

print(gt.kcore_decomposition(Gt, 'total').a)

[2 2 2 2 2 2 2 2 2 2 2 2 2 2 2]

I don't understand the results for the out-k-core.

The same analysis in igraph (using shell_index()) gives:
in-core : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
out-core : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
total : [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

Looking at the source code of kcore_decomposition, it looks like when
deg=='out', the decomposition is done on the reversed network, but still
using the out-degree. Is it normal? I am a bit confused.

Thanks,

Alex

attachment.html (1.74 KB)

You're right; the directed case is being implemented inconsistently. I
have fixed this in git.

Note, however, that "directed k-core" is a fairly nonstandard thing, and
definitions will vary.

Best,
Tiago

Ok, thank you for the fix and clarification.

Best,

Alex

2016-09-05 5:56 GMT-04:00 Tiago de Paula Peixoto <tiago(a)skewed.de>:

attachment.html (1.47 KB)