Gephi

modularity optimisation method?

Asked by Gautier Krings

I have some doubts about the modularity optimisation algorithm that is currently used.
In the wiki, it is stated to be the Louvain algorithm, but the results provided by Gephi often produce lower quality results than the python or matlab code provided online.
for sure, the results can always vary depending on the initial order of encoding of the entries, but even for small graphs with trivial community structure, the algorithm returns suboptimal results.

Does the method implemented in Gephi differ from the original method?

Question information

Language:
English Edit question
Status:
Open
For:
Gephi Edit question
Assignee:
No assignee Edit question
Last query:
Last reply:
Revision history for this message
Sébastien Heymann (sebastien.heymann) said : 		#1

Hi,

Could you share a dataset showing this?

Revision history for this message
Gautier Krings (gautier-krings) said : 		#2

Sure,
I have an undirected graph composed of a clique of 16 nodes on one hand, and 4 cliques of 4 nodes on the other hand.
Every pair of cliques of 4 nodes are linked together by 2 random edges.
Finally, there is one edge from one random node of the large clique to one random node taken in the small cliques.

This is a case where the resolution limit of modularity occurs; the "intuitive" partition should give 5 communities: the large clique and the 4 small cliques. However, the modularity of this partition is 0.3146, and there exists a better partition in two communities: the large clique on one hand, and the 4 small cliques grouped together on the other hand. This partition has a modularity of 0.3505.

The code provided online (matlab or python) finds the optimal partition (2 communities) while gephi returns either a partition in 4 or 5 communities.

Here's the dataset:
1 clique of 16 nodes (IDs: 0 to 15)
1 clique of 4 nodes (IDs: 16 to 19)
1 clique of 4 nodes (IDs: 20 to 23)
1 clique of 4 nodes (IDs: 24 to 27)
1 clique of 4 nodes (IDs: 28 to 31)

inter-clique edges:
16 22
17 20
17 28
18 26
18 28
19 24
21 25
21 30
22 27
23 30
24 29
25 29
4 22

I can share a gephi file if needed, if you tell me how to share a file.

Revision history for this message
Sébastien Heymann (sebastien.heymann) said : 		#3

Now you can on the bug report:

https://bugs.launchpad.net/bugs/727701

Can you help with this problem?

Provide an answer of your own, or ask Gautier Krings for more information if necessary.

To post a message you must log in.