Hi,
I would like to know if the implemented version of the Louvain's algorithm is performing a hierarchical community detection or is it just the first level that is calculated in Gephi.
Thanks in advance.
Phil
[SOLVED] About Community detection
-
Phildumoux
- Posts:1
- Joined:20 Apr 2011 16:47 [phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1275: count(): Parameter must be an array or an object that implements Countable
Re: About Community detection
Hi,
If I understood your question well, then I'd say that the Louvain algo in Gephi finds just the first level of communities.
To get the next levels, you:
- run the Louvain algo to find communities of Level 1.
- group your nodes by communities (you do that in the partition tab, there is a group / ungroup option)
- save the graph as a gexf file, with the option "only visible graph" (this might be unnecessary, but for safety)
- close your project, open the gexf file, and run the Louvain algo. It will then detect the second level of communities.
I did not check again the original Louvain paper to make sure that the communities of level 2 are just Louvain clusters of communities of level 1, but in my memory that was the logic.
Best,
Clement
If I understood your question well, then I'd say that the Louvain algo in Gephi finds just the first level of communities.
To get the next levels, you:
- run the Louvain algo to find communities of Level 1.
- group your nodes by communities (you do that in the partition tab, there is a group / ungroup option)
- save the graph as a gexf file, with the option "only visible graph" (this might be unnecessary, but for safety)
- close your project, open the gexf file, and run the Louvain algo. It will then detect the second level of communities.
I did not check again the original Louvain paper to make sure that the communities of level 2 are just Louvain clusters of communities of level 1, but in my memory that was the logic.
Best,
Clement
-
taynaud
- Gephi Plugin Developer
- Posts:10
- Joined:23 Dec 2010 02:19 [phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1275: count(): Parameter must be an array or an object that implements Countable
Re: About Community detection
It is more complicated I think. "First level" is imprecise, it could be the first level found by the algorithm (the one whith lowest modularity, but the highest number of communities) or the level the closest of the root (the one with the lowest number of communities and the highest modularity). It depends if you consider the root as level 0 or last level.
Gephi should find the level of highest modularity. To summarize the Louvain algorithm, it is composed of two phases that are alterned until the modularity stops increasing :
In the first phase, nodes are moved to neighboring communities greedily to increase modularity
In the second phase, nodes are grouped into their communities to build a new network between communities, and then phase 1 starts on this new network to group communities together.
Each "phase 1 + phase2" corresponds to a level. It the first "phase 1 + phase 2" corresponds to the first level, then it is the level of lowest modularity (with the highest number of communities). Gephi does not give this level, but the last level, corresponding to several successive community grouping which contains the lowest number of communities but the highest modularity (it is a particularity of the dendogram produced by Louvain, the closest level of the root has the highest modularity).
The partition quality found seems low, but I think it is because of an implementation bug. I am working on it, but I do not know when I will have time to finish. If you have examples of networks with lower quality than expected, it would help me (you can send it to me at the adress my_forum_name@gmail.com).
Regards,
Gephi should find the level of highest modularity. To summarize the Louvain algorithm, it is composed of two phases that are alterned until the modularity stops increasing :
In the first phase, nodes are moved to neighboring communities greedily to increase modularity
In the second phase, nodes are grouped into their communities to build a new network between communities, and then phase 1 starts on this new network to group communities together.
Each "phase 1 + phase2" corresponds to a level. It the first "phase 1 + phase 2" corresponds to the first level, then it is the level of lowest modularity (with the highest number of communities). Gephi does not give this level, but the last level, corresponding to several successive community grouping which contains the lowest number of communities but the highest modularity (it is a particularity of the dendogram produced by Louvain, the closest level of the root has the highest modularity).
The partition quality found seems low, but I think it is because of an implementation bug. I am working on it, but I do not know when I will have time to finish. If you have examples of networks with lower quality than expected, it would help me (you can send it to me at the adress my_forum_name@gmail.com).
Regards,