I have been working on a Network-based clustering approach. I used "cluster_optimal" of 'igraph' package in R for clustering. The function works by modularity maximization algorithm. I have understood the concept of modularity (Newman, 2006). But I could not understand how modularity maximization works though I have read the corresponding paper (https://pdfs.semanticscholar.org/7e36/674b63ab1c05579b26af6f30c6b0aa17e057.pdf) Can anyone explain how the modularity maximization works in plain word?
Modularity optimization is usually done by Louvain Algorithm in practice. It's a greedy approach to optimize modularity as follows:
- Each node is assumed to be its own community. Then the change in modularity of the network is calculated by putting each node $i$ and each of its neighbors $j$ in the same community. The neighbor that contributes largest change wins the merging. This is applied to all nodes repeatedly until no change happens in this phase anymore. Now you move to second phase.
- In second phase you replace each community by a single node. Internal edges of each community are represented by weighted self-loops and edges between nodes in different communities are represented as weighted edges between new nodes. Since this network is built you get back to the first step and do the same.
Modularity is still a great thing for community detection (graph/network clustering) but you need to be aware of Resolution Limits.
Hope it helped!