Several Possible Errors in Leiden Implementation

[fantaosha]

Thanks for your great work! However, after reading the code of Leiden, I'm afraid that there are probably several errors in refine_impl.cuh.

1. In the computation of well-connected vertices, I think the correct implementation should be

return wcut > (resolution * wdeg * (louvain_volume - wdeg)) / total_edge_weight;

According to the paper, Eq. (A4) rather than Eq. (A5) is used in the algorithms and proofs. Note that Eq. (A4) is CPM while Eq. (A5) is modularity. Therefore, if modularity is used, there should be a division of total_edge_weight. This also applies to the computation of well connected communities, which should be

bool is_dst_leiden_cluster_well_connected =
      dst_leiden_cut_to_louvain > resolution * dst_leiden_volume * 
             (louvain_cluster_volume - dst_leiden_volume) / total_edge_weight;

2. I think the computation of modularity gain should be

mod_gain = aggregated_weight_to_neighboring_leiden_cluster -
                   resolution * src_weighted_deg * dst_leiden_volume / total_edge_weight;

since the vertex has not been merged into dst_leiden_cluster.

[naimnv]

Thank you. It somehow slipped my mind for a while. After quite some debugging we fixed those errors.