Louvain Community Detection

Overview

Louvain algorithm detects communities by optimizing modularity — the fraction of edges within communities minus expected fraction if edges were random. A greedy, hierarchical algorithm that runs in O(n log n) for sparse graphs. Produces a hierarchy of communities at multiple resolutions.

When to Use

Trigger conditions:

• Discovering natural groupings in social, organizational, or interaction networks
• Segmenting users/customers by behavioral similarity
• Analyzing modular structure of complex networks

When NOT to use:

• For overlapping communities (use DEMON or BigCLAM)
• When communities are pre-defined and you're classifying nodes (use label propagation)

Algorithm

IRON LAW: Modularity Has a RESOLUTION LIMIT
Louvain optimizes modularity, which has a known resolution limit
(Fortunato & Barthélemy, 2007): it cannot detect communities smaller
than √(2E) where E = total edges. In large networks, small but real
communities may be merged. Use multi-resolution methods or Leiden
algorithm (improved Louvain) for better results.

Phase 1: Input Validation

Build undirected weighted graph from interaction data. Edge weights represent interaction strength (frequency, duration, volume). Gate: Graph loaded, no isolated nodes (or decide how to handle them).

Phase 2: Core Algorithm

Phase 1 — Local moves:

1. Assign each node to its own community
2. For each node, compute modularity gain of moving to each neighbor's community
3. Move node to community with maximum positive gain
4. Repeat until no beneficial moves remain

Phase 2 — Aggregation: 5. Build new graph where nodes = communities, edges = sum of inter-community edges 6. Repeat Phase 1 on the aggregated graph 7. Continue until modularity stops improving

Phase 3: Verification

Check: modularity Q > 0 (non-trivial partitioning), community sizes are reasonable (not one giant + many singletons), manual inspection of sample communities. Gate: Modularity positive, community sizes follow power-law-like distribution.

Phase 4: Output

Return community assignments with modularity score.

Output Format

{
  "communities": [{"id": 0, "size": 45, "top_members": ["Alice", "Bob"], "internal_density": 0.35}],
  "summary": {"num_communities": 12, "modularity": 0.65, "largest": 120, "smallest": 5},
  "metadata": {"algorithm": "louvain", "nodes": 500, "edges": 2000}
}

Examples

Sample I/O

Input: Email network of 200 employees, weighted by email frequency Expected: Communities roughly corresponding to departments/teams, modularity ~0.5-0.7.

Edge Cases

Input	Expected	Why
Complete graph	One community or random split	No modular structure
Disconnected components	Each component = community	Natural separation
Weighted vs unweighted	Different communities	Weights change modularity calculation

Gotchas

• Non-deterministic: Node processing order affects results. Run multiple times and select the partition with highest modularity, or use Leiden algorithm (more stable).
• Resolution parameter: Standard Louvain uses γ=1 in modularity. Varying γ reveals communities at different scales. γ>1 finds smaller communities; γ<1 finds larger ones.
• Leiden > Louvain: Louvain can produce badly connected communities (communities where removing one node disconnects them). Leiden algorithm fixes this guarantee.
• Temporal stability: In dynamic networks, community assignments can change drastically between snapshots even when the network changes minimally. Use temporal smoothing.
• Interpretation: Community detection finds structure, but interpreting WHY nodes cluster requires domain knowledge. Don't over-interpret automatically detected communities.

References

• For Leiden algorithm (improved Louvain), see references/leiden.md
• For multi-resolution community detection, see references/multi-resolution.md