Speed and accuracy of Louvain method in Gephi

[xptrxptr]

Hi all.

I have a simple question about community detection in Gephi.

Are there any more details available which version of Louvain method
is actually implemented in Gephi?
I compared results obtained by Gephi and Pajek and found out two facts:
a) results obtained by Pajek have significantly higher modularities
(especially for some values of resolution parameter)
b) results in Pajek are obtained much faster

In Pajek documentation it says that they implemented
"Multilevel Coarsening and Multilevel Refinement algorithm"

I guess your algorithm is only original Louvain method with only coarsening
and without multilevel refinement?
But what surprizes me, that in this case I would expect that your implementation
should be faster (since it is simpler) but it is actually slower
(especially for larger networks).

Any response would be highy appreciated, since I need
to explain the algorithm used as well.

Petra

[taynaud]

Concerning speed:
I do not know how Louvain is implemented in Pajek.

In Gephi, it is not as efficient as it could since the whole graph is copied and the algorithm works on its own copy of the graph.

Another optimisation is to stop the algorithm when the modularity does not raise of more than epsilon and I think it is not implemented.

A possibility is also the language and how the graph is stored. For instance, the python version of louvain is 10 times slower than the C implementation, mostly because of the graph storage and python.

Finaly, Louvain is not totally deterministic and you may be in a case where it is slow. Randomness may help here. Do you use weights (some very small ?) ?


Finally, concerning modularity:

I think that the modularity reported is always the Newman's modularity of the partition found, thus it depends only on the partition and not the resolution parameter. Thus, optimisation is done with the resolution parameter, but not the numeric value reported. Thus, you are not comparing exactly the same things.


I do not know what Pajek call coarsening and multi level refinment. Gephi implements only Louvain Method and not small optimisations of modularity achievable (for instance, optimising again modularity after last partition) as described in Blondel et al. paper. You should be carefull with "modularity over optimisation". Modularity is a very interesting metrics, but you should not stick too much to small modularity gain that are not always meaningfull.

Thomas

[pegerp]

Modularity is a very interesting metrics, but you should not stick too much to small modularity gain that are not always meaningfull.

Hi. I've noticed earlier that small differences in modularity in Gephi can produce aesthetically different results when used with Force Atlas 2 layout algorithm. See https://forum.gephi.org/viewtopic.php?f=32&t=1585 (compare: http://i.imgur.com/zI3q1.png vs. http://i.imgur.com/JAhOp.png). Taynaud explained the modularity well.

In my network it was feasible to run the modularity algorithm several times and pick the most pleasing module coloring result. In the process I noticed that the higher the reported modularity value is the more pleasing the coloring on Force Atlas 2 layout is.

[xptrxptr]

...I do not know what Pajek call coarsening and multi level refinment....

Explained here:
http://dl.acm.org/citation.cfm?id=1970376

...Modularity is a very interesting metrics, but you should not stick too much to small modularity gain that are not always meaningfull...

That is true for small graphs, e.g. 1.000-10.000 nodes, but when dealing with graphs with millions of nodes
already improvement for 0.001 can produce much better communities.

[xptrxptr]

I just tried the latest version of Pajek and found there another very useful community detection algorithm.
It is called VOS. For many graphs the communites found by this method are better
than the one obtained by Louvain.
Since we know that all modularity based clusterings have problems my question is:
do you plan to include some other communiy detection method in the near future?
Thanks.
XPeTRa

[admin]

No, but the community can implement other algorithms, which will also have their own problems too.

[xptrxptr]

Thanks for reply.
I found the following page very interesting:
comparison of Louvain method and VOS Clustering:
http://mrvar.fdv.uni-lj.si/pajek/commun ... ainVOS.htm
I tried it with graphs with some tens of millions of nodes
and it works really well.
Petra

[albertocottica]

Hello all,

can I ask what it means that Louvain is not totally deterministic? On a small network (200 nodes, 1500 edges, weighted with weights being integers) I get different values every time I run the algorithm. Also the number of subcommunities changes, which is a bit unsettling.

[xptrxptr]

Multilevel coarsening and refinement algorithm (which is implemented in Pajek) is much more stable than standard Louvain method.
For network like yours, I need approx. 3 restarts to get the stable final result.

On
http://mrvar.fdv.uni-lj.si/pajek/commun ... xample.htm
there is a useful hint about results obtained by community detections:
Compare the partitions obtained in two runs with the same resolution parameter (using Partitions/Info/Cramer's V, Rajski, Adjusted Rand Index). If the correlation of the two partitions is small, the number of communities is probably not the right one, therefore we suggest to try the algorithm with another (larger or smaller) value of resolution parameter.

I hope that will be of some help to you.

Petra

[albertocottica]

Thanks, Petra, I had managed to miss your reply!