search

vtraag / leidenalg

Implementation of the Leiden algorithm for various quality functions to be used with igraph in Python.
GNU General Public License v3.0
596 stars 78 forks source link

Correctly consider neighbouring nodes in queue #70

Closed vtraag closed 3 years ago

vtraag commented 3 years ago

Previously, neighbouring nodes were only considered for the first graph in case of multilayer graphs for the move_nodes function. Additionally, neighbouring nodes were insufficiently considered. Moreover, in the case of move_nodes_constrained, some objects were incorrectly not initalized, leading to the bug noted in #68. To avoid future confusion, the object referring typically to the first partition and graph are explicitly removed. This fixes #68.

Presumably, this change will increase the runtime somewhat, but is likely to also lead to better quality. This needs to be analysed a bit further still.

vtraag commented 3 years ago

A quick test using a simple planted partition model (10 clusters, average degree 10, mixing parameter 0.7) for varying network sizes shows that indeed the implementation now takes more time, but finds substantially better partitions (in terms of quality value).

image