September 9, 2017 at 9:16 am #893
I am using Braph for the analysis of fMRI networks.
I did an analysis of the community structure and got very different modules when I used the Newman and Louvain algorithms.
Could you explain me the difference in these two algorithms so that I can understand better the results I got?
Thank you so much!
DanielSeptember 11, 2017 at 5:37 pm #923
Thanks for using Braph. I hope that the software works for you and you are able to obtain the results you would like.
Both of the algorithms aim to optimize the modularity, a measure of the quality of the community division of the network. In short, modularity measures the density of the connections within a community and compares it with what it would be in a given random network. The more positive modularity indicates better division of the network into communities. The difference between the algorithms is in the way in which they approach to modularity maximization.
The Louvain method uses an iterative procedure to group the single nodes into communities. It starts by assigning each node in the network to a separate community. By changing the community participation of a node and its neighbors, it optimizes the modularity locally throughout the network. This results in having some community structure in the network. In the second step, these communities become nodes and the first step of local modularity maximization is reapplied. These two steps are repeated until the maximum modularity is obtained and there are no changes in modularity values with any new iteration.
On the other hand, the Newman algorithm is a divisive algorithm. This algorithm uses a metric for an edge called betweeness centrality, defined as the number of shortest paths between any two vertices that include the particular edge. The idea is that any edge that connects two separate communities will have high betweeness centrality because many short paths that run between nodes in the two separate communities would include that edge. Therefore, the algorithm calculates the edge betweeness centrality for each edge and removes the one with the highest one. After each step, the betweeness is recalculated for each edge and again the one with the highest one is removed. Thus, one could proceed with removing edges until the whole network is depleted, calculating the modularity at each step and choosing the intermediate step for which modularity is maximum as the optimal community structure.
Hope this explanation helps. For a more detailed description of the method, I would suggest the original papers of the both algorithm which are very explanatory:
Blondel, V. D., Guillaume, J. L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008(10), P10008.
Newman, M. E., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical review E, 69(2), 026113.
If you need any additional help, please do not hesitate to contact us.