Ciao Fabio (well spotted…)
Thank you for the heads up - I really appreciate. Below, I try to address the questions you raised in response to mine:
1 - I am only interested in ‘Louvain’ for the sake self-education. I chiefly deploy it to cluster text documents and, not being a developer, I could have happily lived trusting whatever happens to be built into applications such as Gephi, VOS viewer, and obviously igraph. Lately, I’ve been having some issues interpreting apparently small differences between clusters generated by igraph and Gephi (both using Louvain), prompting me to try and replicate what’s going on in there from scratch.
2 - Before I share a fully-fledged graph, it’s enough to consider a very simple example like the one in this post (https://medium.com/walmartlabs/demystifying-louvains-algorithm-and-its-implementation-in-gpu-9a07cdd3b010). I illustrate a ‘dry run’ leading to different results:
a - blogger answer: A = {1, 2, 3}; B = {4}; C ={5,6,7}; D = {8, 9}
b - igraph cluster_louvain answer (modularity: 0.44): A = {1, 2, 3}; B = {4, 5, 6}; C = {7, 8, 9};
c - my ‘from scratch’ answer (modularity: 0.401):
---- c.1) first pass: A = {1,4}; B = {2,3}; C = {5,6}; D= {7}; E = {8,9}
---- c.2) second pass: A = {1,2,3,4}; B = {5,6}; C = {7,8,9}
The core of my query is therefore, how wrong am I in arriving at answer (“c”)? So far, I reasoned as follows re the ‘first pass’:
for each node i
–set ‘best modularity gain’ to zero
–for each neighbouring node j’s community c_j
------remove node i from the community it is currently assigned to
------compute the changein modularity due to moving i into c_j
------if change in modularity > best modularity gain
----------call it c_j*
----------re-assign node i to c_j* (until next round)
----------best modularity gain <- modularity gain at this iteration
------else
----------restore previously assigned community
–end
end
I produced a tableau (that cannot be attached - but see picture below) to illustrate how the above pseudo-code runs in my ‘from scratch’ replication, generating answer “c”. One might notice the presence of ‘ties’ on modularity gains in several occasions.
Since R doens’t seem very popular on here, I spare you the actual R script but obviouly I’m happy to share if sensible.
Hopefully the exapmle above makes enough sense despite the apparent triviality of the issue?
Thanks,
Ettore