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
575 stars 77 forks source link

leidenalg.CPMVertexPartition reference for negative weights #123

Closed alisonpeard closed 1 year ago

alisonpeard commented 1 year ago

Hi,

Thanks for this great package!

The documentation states that the CPMVertexPartition is "well-defined for both positive and negative edge weights", but there is no mention of negative weights in the referenced paper:

Traag, V. A., Van Dooren, P., & Nesterov, Y. (2011). Narrow scope for resolution-limit-free community detection. Physical Review E, 84(1), 016114. 10.1103/PhysRevE.84.016114

Is there a paper related to this algorithm that proves this statement?

ragibson commented 1 year ago

That reference does appear to discuss negative links, both in reference to a cited paper on a Potts model and the author's own extension of a Potts model to negative links.

In any case, this seems clear by inspection.

CPMVertexPartition [...] This quality function is well-defined for both positive and negative edge weights.

The Constant Potts Model's quality function basically just adds the weights of the network and subtracts a constant, so there shouldn't be any issues with negative weights.

vtraag commented 1 year ago

Thanks @ragibson for answering @alisonpeard's question!

In addition to what @ragibson already said, you can find some more details in my thesis, in particular section 5.2.