[ANN] LightGraphs v1.3.3 - another bugfix

Hi all,

LightGraphs.jl has been updated to v1.3.3 to fix a bug in core_number. No other changes have been made.

I expect to have a cool LG announcement in the next few days. Please stay tuned :smiley:.

Edited to add more detail:

This is a bug in the correctness of core_number. The old version produced incorrect results when run on directed graphs with bidirectional edges. The reason is that the old code used all_neighbors to determine the set of neighbors to process; the issue is that all_neighbors ensures no duplicates: so if you had an edge from X → Y and another from Y → X, the neighbors of X would only include Y one time. This is not what the algorithm specifies.

So we fixed it by explicitly using outneighbors and inneighbors so that bidirectional edges are included. Fortuitously, this also resulted in a speedup as all_neighbors needed to deduplicate; and we explicitly do not want that behavior here.

So - if you’ve been using core_number results with directed graphs anywhere, (including with k_core and the other degeneracy functions), you will probably want to re-run your results with this fix applied.

5 Likes