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:

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

Phase 2 — Aggregation:

• Build new graph where nodes = communities, edges = sum of inter-community edges
• Repeat Phase 1 on the aggregated graph
• 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