From Cohen Courses
Jump to navigationJump to search

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

where is weight of the edge between and .

Here is degree of the node and is total weight of edges in the network.

Relevant Papers