algo-net-community

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.