Modularity
Q = sum over communities of (fraction of edges inside - expected fraction). Ranges [-1, 1]. Higher = better clusters.
Advertisement
Two-phase iteration
Phase 1: each vertex tries joining neighboring community, keep move if ΔQ > 0. Phase 2: contract each community to super-node. Repeat.
Advertisement
Complexity
O(N log N) empirically. No proven bound. Fast in practice.
Resolution limit
Louvain misses small communities in large graphs. Resolution parameter γ tunes granularity.