It uses a localized greedy search to find optimal partitioning of the network, therefore it is one of the fastest off-the-shelf implementations. To give a brief preview of what the algorithm does, we would like to provide the steps performed in the algorithm.
- Firstly, it treats every node in the network as a community in itself.
- Then, it calculates the quality of the community, which is quantized the modularity function. The modularity function is described below.
- Let us consider that modularity function is what we want to maximize, so a community with high modularity is a well-formed community otherwise ill-formed.
- At each step the algorithm iterates over other communities that could be merged with a community that we are looking at.
- This process goes on until we find no merge-able communities in the network, i.e. any further merge would reduce the modularity of the community.
The modularity function is given by $Q$, where $Q$ is
where is weight of the edge between and .
Here is degree of the node and is total weight of edges in the network.