# 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

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

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

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

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

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