cugraph icon indicating copy to clipboard operation
cugraph copied to clipboard

Address Leiden clustering generating too many clusters

Open ChuckHastings opened this issue 1 year ago • 0 comments

Our implementation of Leiden was generating too many clusters. This was not obvious in smaller graphs, but as the graphs get larger the problem became more noticeable.

The Leiden loop was terminating if the modularity stopped improving. But the Leiden algorithm as defined in the paper allows the refinement phase to reduce modularity in order to improve the quality of the clusters. The convergence criteria defined in the paper was based on making no changes on the iteration rather than strictly monitoring modularity change.

Updating this criteria results in the Leiden algorithm running more iterations and converging on better answers.

Closes #4529

ChuckHastings avatar Oct 18 '24 18:10 ChuckHastings