search

taynaud / python-louvain

Louvain Community Detection
BSD 3-Clause "New" or "Revised" License
964 stars 200 forks source link

Coefficient of `degc_totw` in modularity calculation. #82

Closed whatever60 closed 2 years ago

whatever60 commented 3 years ago

Hi, there is my question about how the modularity is calculated during node moving.

I think the following code —

https://github.com/taynaud/python-louvain/blob/0be2657088ace315959f44e2b02030c597cf63a3/community/community_louvain.py#L483-L502

comes from such derivation —

image

And to my best understanding, degc_totw represents

image

where node c moves from community x to community y, and capital K is the degree of community and lowercase k is degree of node. (I omit resolution there).

So, where is the coefficient 2? Thank you.

ComplexLychee commented 2 years ago

Hi there, good spot.

It seems that the discrepancy comes from the fact that there is a factor 2 in the $\delta e$ term in your derivation. The code implementation in lines 487-488 and lines 494-495 excludes the coefficient 2, which does not affect the result.

It might be helpful to look at the equation (2) in the original Louvain paper: https://iopscience.iop.org/article/10.1088/1742-5468/2008/10/P10008/meta, which also appears in issue #71 .

taynaud commented 2 years ago

Thanks, indeed this coefficient does not affect the results

whatever60 commented 2 years ago

Thank you Lizhi.