[SOLVED] Splitting Modularity and Louvain Algorithm

[dcombe]

Hello.

While my advisor ask me for an app for calculating modularity over a partition, I see that there is no stat for a partition in Gephi (while I consider Partition management is one of the strength of Gephi).
Wouldn't it be nice to allow modularity calculation without performing thepartition using the Louvain algorithm?

Don't you think that "Modularity" in Network Overview is an unclear label for Louvain application? In order to replace it, I would think to something like "Best modularity clustering" (in order to say that modularity is given in the report of the function).
And, as it seems that Louvain uses random numbers in its algorithm, should I consider that modularity in not deterministic in Gephi?

These are only few comments about my approach to some Gephi functions ; Gephi rocks.

Best regards,
David C.

[admin]

Hi,

Louvain method is one of the more accurate way to compute modularity, and as we want to have only one integrated algorithm to compute it, we should keep this name.

In the end, we would better have a panel dedicated to clustering and move it inside.

But I'm not sure to understand "allow modularity calculation without performing the partition using the Louvain algorithm"?

Clustering is not deterministic with the Louvain method. Compute it twice on the same graph, and you should have slightly different partitions.

[L.J.]

Hello dear admin,

Although Blondel et al., JSTAT 2008 algorithm is really fast (compared with the algorithm by Roger Guimerà based on simulated annealing, being Roger's algorithm much more accurate as it is said even in the paper by Blondel)

One of the problems that I have when using gephi is that when I calculate modularity and community finding using Roger's algorithm, I cannot create a partition in gephi with those modules, and I have to introduce the module ID for each node in the gexf file as an attribute. If the number of modules is small it is easy to paint all the modules with a different colour, but if the number is more than 10... it is not so easy. So it would be very very useful if the gexf format support those partitions (as pajek for example does), or that the color bar of the ranking tool can support discrete values (each value in one customizable color).

A problem that I can see when comparing the results obtained with the two mentioned algorithms, is that Blondel's algorithm is hierarchical, so it is possible to find modules inside of modules. The big problem here is that gephi don't allow the user to modify that hierarchical property. For example I'm comparing the results that I obtained with Roger's and with Gephi, and I see that Gephi gives divide some of the modules found by Roger's algorithm into a few modules, but that is not the structure that maximizes modularity, and I would like to tell Gephi not to calculate modules inside of modules (what I'm trying to explain can be easily seen plotting a modular network with YifanHu's Multilevel layout, and showing the modules found by Roger's algorithm and the modules found by gephi)

Roger.pdf

Community finding with Roger's algorithm

(8.72KiB)Downloaded 397 times

Gephi.pdf

Community finding with Gephi

(8.93KiB)Downloaded 488 times

A general gephi problem regarding statistics, is that you don't say anywhere which algorithm you are using, taken from which reference, or you don't give the opportunity to modify algorithm parameters (if they exist).

I develop my own code, and I don't need gephi to perform any metric, I use it only to make nice layouts, but many people will thank a tool than can be trusted based on a well known bibliography etc etc.

A table quoting algorithms and references will be very useful. A different topic is that a tutorial on how to make dynamic graphs will be also extremely useful. (in that sense you are probably losing the match against UbiGraph )

Anyway, you are doing a great job.

[admin]

Hi L.J.,

Your remarks are very accurate.

Yes we have opened a bug issue about the modularity: https://bugs.launchpad.net/gephi/+bug/727701

Note that you can implement your own statistics by a plugin in Gephi: http://wiki.gephi.org/index.php/HowTo_write_a_metric
The plugin will be integrated in the user interface like other metrics, and made available to the whole community if you publish it on the Plugins Center.

However I'm afraid not to understand the problem with the GEXF. A partition in Gephi is just an interpretation of an attribute in which the values can be used as such. Please verify that you Module ID is of type Integer, so it will be available as a parameter of the Partition Panel.

We certainly should add a documentation inside Gephi to display a list of papers we implement the algorithms. We started something on the Wiki but with room for improvements! Our main problem is that we just don't have enough time...researchers that participate in the project are _very_ rare. Any help on improving the documentation prior to write a manual would be really appreciated.

On dynamic graph, have a look at this page.

[L.J.]

As usual, thanks for your fast reply.

Integer type of data was probably the only one I didn't tried... and it works perfectly. It is a nice trick to remember.

Some times in lab meetings we talk about the issue of creating a software to help people to use the tools/metrics that we develop. And that could be the perfect complement to gephi. I can't promise anything (since we don't have any spare time and every one do his own stuff in python, C++ or Matlab, being Java useless. Also other people in the lab uses other visualization software that maybe have a better connection with python...), but I will talk about the possibility to create a metrics package that complements one of those software (maybe Gephi).

Best regards
L.J.

PS: some good French scientist such as Alain Barrat uses Gephi, may be their lab can contribute to the project (just an idea).

[admin]

That would be great!

I'm in the same case here at LIP6 ComplexNetworks team, so one of my colleague created a Python console as a plug-in.
Eytan Adar is also a GSoC mentor this year to help porting the Gython script language in Gephi, initially available in GUESS.

Alain Barrat and his groups do very interesting researches in dynamic networks, so we are regularly in contact. They already contributed to Gephi by creating the Graph Streaming API during the last GSoC