Modularity

This is an algorithm for the problem of Community Detection.

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.

Modularity Function

The modularity function is given by $Q$, where $Q$ is

$Q={\frac {1}{2m}}\sum _{i,j}[A_{ij}-{\frac {k_{i}k_{j}}{2m}}]\delta {c_{i},c_{j}}$

where $A_{ij}$ is weight of the edge between $i$ and $j$.

$\$k_{i}=\sum _{j}A_{ij}\$$

$m={\frac {1}{2}}\sum _{ij}A_{ij}$

Here $k$ is degree of the node $i$ and $m$ is total weight of edges in the network.