Graph cut

Graph cut is a problem of finding a minimal set of edges whose removal breaks a connected component into multiple disconnected components. Finding such a minimal edge set is often an NP-hard combinatorial problem. However, it is possible to find a fairly good cut by relaxing the discrete combinatorial problem into a spectral decomposition problem.

• A tutorial on spectral clustering | SpringerLink

Modularity

Modularity introduces the idea that communities must be denser than random connections (i.e. a null model). The introduction of null models is a major departure from graph cuts, which may find communities sparser than random connections.

• [cond-mat/0308217] Finding and evaluating community structure in networks
• Phys. Rev. E 74, 036104 (2006) - Finding community structure in networks using the eigenvectors of matrices
• Modularity and community structure in networks | PNAS

We can introduce domain knowledge about random connections. For instance, if a network is a railroad network, the random network must be a planner graph with no edges crossing. There are many variants of modularity combined with different null models:

• Uncovering space-independent communities in spatial networks | PNAS

Limitation:

• Resolution limit in community detection | PNAS
• Phys. Rev. E 81, 046106 (2010) - Performance of modularity maximization in practical contexts
• Tiago de Paula Peixoto — Blog

Embedding + Clustering

Stochastic Block model