Codebase Comprehension Algorithms

Community Codebase Comprehension And Domain Mapping Algorithms Best Practices

A practitioner-oriented reference of the algorithms that work for mapping a codebase into understandable feature/business domains. Most of these techniques live in the Software Architecture Recovery and Mining Software Repositories literatures and are invisible to working engineers — yet they're the right tools for the job a coding agent is asked to do every day: "what does this codebase do, and where?"

The 47 rules are organized by execution-lifecycle impact: a wrong decision early in the pipeline (which graph to build, which identifiers to keep) propagates through everything downstream. The three CRITICAL categories (graph-, clust-, valid-) are the ones a wrong call cannot be recovered from later. Read them first.

Scope: proven algorithms with peer-reviewed citations or canonical books — Newman Networks, Leskovec-Rajaraman-Ullman Mining of Massive Datasets, Ganter-Wille Formal Concept Analysis, plus 40+ ICSE / FSE / TSE / PNAS / JMLR papers. No tutorial sites, no Stack Overflow, no marketing posts. Deliberately deferred to a future version: GNN/CodeBERT/code2vec (not "proven over decades" yet) and refactoring-recipe stuff (covered by sibling skills like react-refactor and typescript-refactor).

When to Apply

Use these rules when:

• Onboarding an agent into an unfamiliar codebase: "explain what this codebase does, by domain"
• Producing an architecture map: "what are the main subsystems and how do they connect?"
• Locating a feature: "which files implement payments / authentication / search?"
• Reviewing a refactor: "did this change respect the architectural boundaries?"
• Detecting architectural debt: "what files have surprising coupling?"
• Validating an existing decomposition: "does the README's architecture match the code?"
• Picking algorithms for any of the above — the user wants something that's proven, not vibes

Rule Categories By Priority

Quick Reference

1. Graph Construction & Edge Weighting (CRITICAL)

• `graph-filter-omnipresent-utilities-before-clustering` — Drop the loggers and base classes BEFORE clustering (20-40 MoJoFM points)
• `graph-pick-edge-type-by-question-asked` — Call, import, co-change, bipartite — the question determines the graph
• `graph-collapse-sccs-before-clustering` — Tarjan SCC condensation makes cycles explicit and stabilises every algorithm
• `graph-weight-edges-by-information-content` — IDF / PMI / Jaccard on edges suppresses noise (2-5× MoJoFM)
• `graph-bipartite-file-term-for-joint-structure` — When DI / dynamic dispatch hides the call graph
• `graph-combine-signals-in-multilayer-graphs` — Mucha 2010 multilayer modularity over normalised α-weighted layers

2. Community Detection & Clustering (CRITICAL)

• `clust-leiden-not-louvain` — Louvain produces disconnected communities on 5-25% of nodes (Traag 2019)
• `clust-infomap-mdl-on-random-walks` — MDL on random walks; the right tool for flow-meaningful graphs
• `clust-stochastic-block-model` — Bayesian, hierarchical, learns K from data; handles non-assortative structure
• `clust-mcl-markov-clustering` — Flow simulation; dominant in bioinformatics; robust to noise
• `clust-walktrap-short-random-walks` — Random-walk distance + hierarchical agglomerative
• `clust-spectral-laplacian-fiedler` — Optimal k-way normalised cut via Laplacian eigenvectors
• `clust-hdbscan-density-based` — When clustering on file embeddings, not graphs

3. Validation & Quality Metrics (CRITICAL)

• `valid-mojofm-as-software-clustering-distance` — The SAR gold-standard distance metric (Wen-Tzerpos 2004)
• `valid-adjusted-rand-index-and-nmi` — Chance-corrected cross-algorithm comparison
• `valid-be-aware-of-resolution-limit` — Modularity can't see clusters smaller than √(2m) (Fortunato-Barthélemy PNAS 2007)
• `valid-consensus-clustering-for-stability` — A single-run answer is unreliable; consensus across runs is the right answer
• `valid-cochange-prediction-as-ground-truth-proxy` — Temporal held-out co-change replaces missing ground truth
• `valid-ablate-each-input-signal` — Leave-one-out; reveals which input actually drives the result

4. Identifier & Lexical Preprocessing (HIGH)

• `lex-split-identifiers-with-samurai` — 87% precision vs 60% for naive camelCase (Enslen MSR 2009)
• `lex-build-programming-language-stop-words` — Three-layer: keywords + generic + IDF-driven
• `lex-expand-abbreviations-with-context` — usr → user, ctx → context (Lawrie GenTest 2011)
• `lex-tf-idf-and-bm25-on-identifiers` — Raw counts are dominated by common terms; TF-IDF / BM25 fix it
• `lex-stem-versus-subword-tokenization` — Porter stemmer for clustering, BPE for embeddings
• `lex-extract-verb-object-pattern-from-method-names` — getUserById → (verb=get, object=user); compound concept signal

5. Software-Specific Architecture Recovery (HIGH)

• `arch-bunch-with-mq-fitness` — MQ fitness function + search; better than Q-maximization on code
• `arch-acdc-subgraph-patterns` — Subsystem and skeleton patterns; matches architect intuition
• `arch-limbo-information-bottleneck` — Tishby's IB applied to software (Andritsos-Tzerpos 2005)
• `arch-reflexion-model` — Compare hypothesized vs actual; the underused gem from Murphy-Notkin 1995
• `arch-dsm-partitioning` — Design Structure Matrix; 60-year-old engineering technique

6. Topic Modelling on Source Code (HIGH)

• `topic-lda-on-source-code` — Probabilistic per-file topic distributions over identifier+comment text
• `topic-lsi-svd-on-term-document` — Deterministic SVD-based semantic embeddings (Maletic-Marcus 2001)
• `topic-nmf-non-negative-factorization` — Parts-based additive topics, fully reproducible
• `topic-hdp-for-nonparametric-topic-count` — Hierarchical Dirichlet Process — learns K from data
• `topic-pick-topic-count-by-coherence-not-perplexity` — Perplexity is anti-correlated with human topic quality

7. Evolutionary Coupling & Co-Change Mining (HIGH)

• `evol-mine-cochange-with-lift-and-confidence` — Lift > 2 is the cutoff; raw co-change count is noise
• `evol-filter-large-commits` — A 200-file commit produces 20K spurious pair-counts; filter aggressively
• `evol-temporal-decay-on-edge-weights` — Exponential decay with 6-month half-life
• `evol-logical-coupling-as-architectural-signal` — 30-50% of strongest coupling is invisible to static analysis (Gall 1998)

8. Information-Theoretic Methods (MEDIUM-HIGH)

• `info-normalized-compression-distance` — Cluster without feature engineering; gzip-based universal similarity
• `info-mutual-information-as-coupling` — Catches non-linear / conditional coupling that lift misses
• `info-mdl-for-model-selection` — Principled K selection; Occam's razor as a code length
• `info-naturalness-of-code-as-quality-signal` — Hindle 2012 — code is 30-50% more predictable than English; bugs spike entropy

9. Centrality, Hierarchy & Labelling (MEDIUM)

• `rank-pagerank-for-module-importance` — Architectural spine via PageRank on the reversed dependency graph
• `rank-hits-hubs-and-authorities` — Orchestrators vs implementations (Kleinberg 1999)
• `rank-betweenness-centrality-for-bottlenecks` — Bridges between domains; god-class detection
• `rank-textrank-for-cluster-labels` — Multi-word keyphrases as cluster labels (Mihalcea-Tarau 2004, YAKE 2020)

How to Use

Start with the question the agent is trying to answer:

• "What are the main domains in this codebase?" → graph- (pick a graph) → clust- (Leiden / Infomap / SBM) → topic- (label them) → valid- (sanity-check stability and ablate)
• "Which files implement feature X?" → topic-lda-on-source-code for theme location; rank-pagerank-for-module-importance with X's files as seed for personalized PageRank
• "Where is the architectural spine?" → rank-pagerank-for-module-importance + rank-hits-hubs-and-authorities on the dependency graph
• "Does the README's architecture match the code?" → arch-reflexion-model is purpose-built for this
• *"What's the real coupling here (beyond static dependencies)?"* → evol-logical-coupling-as-architectural-signal and evol-mine-cochange-with-lift-and-confidence
• "How do I cluster without designing features?" → info-normalized-compression-distance
• "How big are the clusters supposed to be?" → valid-be-aware-of-resolution-limit and topic-hdp-for-nonparametric-topic-count
• "How do I know my decomposition is right?" → the entire valid- category; multi-proxy evaluation is mandatory

The skill's worldview: build the right graph first (and filter omnipresent files), pick an algorithm matching the graph and the question, use a code-specific preprocessing pipeline (Samurai + stop-words + stemming + TF-IDF) where lexical signals matter, and always validate — MoJoFM if you have expert ground truth, consensus + co-change prediction + ablation if you don't.

Code examples are in Python because the reference implementations (networkx, igraph, leidenalg, scikit-learn, gensim, graph-tool, hdbscan) all live there. The reasoning generalises to any language.

Reference Files

Related Skills

• computer-science-algorithms — Algorithm-and-data-structure reference (this skill cross-references it for MinHash/LSH, Aho-Corasick, etc.)
• complexity-optimizer — Static analysis for hot paths the rules here identify
• design-to-react-algorithms — Companion skill for design-to-code structural recovery

codebase comprehension and domain mapping algorithms

Version 0.1.0 Community May 2026

Note:

This document is mainly for agents and LLMs to follow when maintaining,

generating, or refactoring codebases. Humans may also find it useful,

but guidance here is optimized for automation and consistency by AI-assisted workflows.

---

Abstract

A practitioner-oriented reference of 47 algorithms across 9 categories for mapping a codebase into understandable feature/business domains — graph construction (omnipresent filter, multilayer, SCC condensation, edge weighting), lexical preprocessing (Samurai identifier splitting, abbreviation expansion, TF-IDF/BM25, stemming, V-O parsing), community detection (Leiden over Louvain, Infomap, Stochastic Block Models, MCL, Walktrap, spectral, HDBSCAN), software-specific architecture recovery (Bunch + MQ, ACDC, Limbo, Reflexion, DSM), topic modelling on source (LDA, LSI/SVD, NMF, HDP, coherence-based K selection), evolutionary coupling from version history (lift/support/confidence, large-commit filtering, temporal decay, logical coupling), information-theoretic methods (Normalized Compression Distance, Mutual Information, MDL, code naturalness), centrality and labelling (PageRank, HITS, betweenness, TextRank/YAKE), and validation (MoJoFM, Adjusted Rand Index, Normalized Mutual Information, resolution-limit awareness, consensus clustering, co-change prediction as ground-truth proxy, ablation). Every rule cites peer-reviewed sources (ICSE / FSE / TSE / JMLR / PNAS) or canonical books. Designed for AI agents asked to grok an unfamiliar codebase and report what each part of it actually does.

---

Table of Contents

1. Graph Construction & Edge Weighting — CRITICAL

• 1.1 Build A Bipartite File × Term Graph When Identifiers Carry The Signal — HIGH (10-20 MoJoFM points on heavily-DI codebases where static call-graph misses 30-60% of edges)
• 1.2 Collapse Strongly Connected Components Before Clustering — CRITICAL (turns a tangled multigraph into a DAG and prevents clusters from being split mid-cycle)
• 1.3 Combine Structural, Lexical and Co-Change Signals As A Multilayer Graph — HIGH (15-30% MoJoFM improvement over single-signal clustering on real codebases (Beck-Diehl EMSE 2013))
• 1.4 Filter Omnipresent Utilities Before Clustering — CRITICAL (removes ~5–15% of files that absorb 50%+ of edges and dominate every cluster)
• 1.5 Pick The Edge Type By The Question You're Asking — CRITICAL (30-50% disagreement between structural and co-change clusterings on the same codebase (Beck-Diehl 2013))
• 1.6 Weight Edges By Information Content, Not Raw Frequency — CRITICAL (2–5x MoJoFM improvement over unweighted graphs by suppressing high-fan-in noise)

2. Community Detection & Clustering — CRITICAL

• 2.1 Use HDBSCAN For Density-Based Clustering On File Embeddings — MEDIUM-HIGH (handles varying cluster densities; eliminates the need to pick K; 10-15 NMI points over k-means on file embeddings)
• 2.2 Use Infomap When You Want To Compress Flow, Not Maximize Modularity — CRITICAL (5-15% NMI improvement over Leiden on directed flow-meaningful graphs; comparable on undirected)
• 2.3 Use Leiden, Not Louvain — Louvain Produces Disconnected Communities — CRITICAL (Louvain returns badly-connected clusters on up to 25% of nodes; Leiden eliminates the defect)
• 2.4 Use MCL (Markov Clustering) For Flow Simulation On Sparse Graphs — MEDIUM-HIGH (15-30% improvement on noise-injected networks (Brohée-van Helden 2006); eliminates K hyperparameter)
• 2.5 Use Spectral Clustering When Cuts And Algebraic Connectivity Matter — MEDIUM (computes optimal k-way normalized cut in O(N²) eigendecomp; reveals algebraic connectivity λ₂)
• 2.6 Use Stochastic Block Models For Principled Bayesian Decomposition — HIGH (NMI 0.7-0.9 vs 0.1 for modularity on non-assortative structure (Peixoto 2014); eliminates resolution limit)
• 2.7 Use Walktrap When You Want Communities Defined By Short Random Walks — MEDIUM (O(n² log n) hierarchical, distance metric grounded in random-walk probabilities)

3. Validation & Quality Metrics — CRITICAL

• 3.1 Ablate Each Input Signal And Measure The Drop In Quality — MEDIUM-HIGH (reveals which input signals carry signal vs noise; eliminates unhelpful components from the pipeline)
• 3.2 Be Aware Of The Resolution Limit Of Modularity Maximization — CRITICAL (prevents modularity Q from detecting clusters smaller than sqrt(2m); affects every codebase with > 10000 edges)
• 3.3 Use Adjusted Rand Index And Normalized Mutual Information For Cross-Algorithm Comparison — HIGH (chance-adjusted clustering similarity; reduces inflated baseline of plain Rand index by 0.6-0.9)
• 3.4 Use Co-Change Prediction As A Ground-Truth Proxy When No Expert Labels Exist — HIGH (eliminates need for expert ground-truth labelling; lift > 2 against random is the minimum bar)
• 3.5 Use Consensus Clustering To Measure And Improve Stability — HIGH (reduces single-run variance; 0.70 → 0.85 NMI on LFR benchmark across 50 runs (Lancichinetti-Fortunato 2012))
• 3.6 Use MoJoFM As The Canonical Distance Between Software Clusterings — CRITICAL (reduces cross-algorithm comparison to a single 0-100 score; the SAR gold-standard since 2004)

4. Identifier & Lexical Preprocessing — HIGH

• 4.1 Build A Stop-Word List Specific To Programming Languages — HIGH (removes 30-50% of token volume that carries no domain signal ("get", "data", "manager"))
• 4.2 Expand Abbreviations With Context Before Computing Similarity — HIGH (recovers 10-20% of identifier tokens that were lost to abbreviation; usr → user, ctx → context)
• 4.3 Extract Verb-Object Pattern From Method Names For Concept Mining — MEDIUM-HIGH (surfaces 70%+ of "what this code does to what" semantics that pure bag-of-tokens loses)
• 4.4 Split Identifiers With Samurai, Not Just Regex — HIGH (87% accuracy on hard splits vs ~60% for camelCase regex alone (Enslen et al., MSR 2009))
• 4.5 Stem Or Subword-Tokenize To Collapse Morphological Variants — MEDIUM-HIGH (collapses 20-40% vocabulary inflation from singular/plural/tense variation)
• 4.6 Use TF-IDF Or BM25 To Weight Identifier Tokens, Not Raw Counts — HIGH (2-3x improvement in topic coherence and clustering quality over raw token frequency)

5. Software-Specific Architecture Recovery — HIGH

• 5.1 Use ACDC's Subgraph Patterns To Recover Subsystem And Skeleton Structure — HIGH (recovers MoJoFM 75+ vs 40-55% for statistical methods on standard SAR benchmarks)
• 5.2 Use Bunch's Modularization Quality As A Software-Specific Fitness Function — HIGH (improves MoJoFM by 5-15% over Q-maximization on standard SAR benchmarks (Mitchell-Mancoridis TSE 2006))
• 5.3 Use Design Structure Matrix Partitioning To Find Block-Diagonal Architecture — MEDIUM-HIGH (reduces architecture analysis to block-diagonal matrix inspection in O(V+E); reveals cycles and layers)
• 5.4 Use Limbo To Cluster Files By Preserving Information About Their Features — HIGH (2-5× faster than Bunch's genetic-algorithm variant with comparable MoJoFM; applies Information Bottleneck principle)
• 5.5 Use The Reflexion Model To Compare Hypothesized vs Actual Architecture — HIGH (reduces architecture recovery from months to days; reveals 80% of debt in 4-6 hours (Murphy-Notkin FSE 1995))

6. Topic Modelling on Source Code — HIGH

• 6.1 Pick The Number Of Topics By Coherence, Not Perplexity — HIGH (perplexity is 43% anti-correlated with human topic quality; C_V coherence correlates 79% (Röder 2015))
• 6.2 Use Hierarchical Dirichlet Processes To Learn The Right Number Of Topics — MEDIUM-HIGH (eliminates K hyperparameter; infers number of topics from data at 2-3× LDA's cost)
• 6.3 Use LDA On Source Code To Surface Latent Domain Topics — HIGH (60-85% topic-domain alignment with expert labels on Java systems (Linstead ICSM 2007))
• 6.4 Use LSI / Truncated SVD When You Need Deterministic Semantic Embeddings — HIGH (5-10× faster than LDA; produces deterministic embeddings for similarity queries)
• 6.5 Use Non-Negative Matrix Factorization When You Need Strictly-Positive Topic Weights — MEDIUM-HIGH (deterministic alternative to LDA; 5× faster convergence with parts-based additive interpretation)

7. Evolutionary Coupling & Co-Change Mining — HIGH

• 7.1 Apply Temporal Decay So Old Co-Change Counts Less Than Recent — MEDIUM-HIGH (5-8% MoJoFM improvement on 6-month half-life vs un-weighted (Beck-Diehl EMSE 2013))
• 7.2 Filter Out Large Commits Before Mining Co-Change — HIGH (a single 200-file commit inflates pair counts by 200·199/2 ≈ 20K; filter aggressively)
• 7.3 Mine Co-Change With Lift And Confidence, Not Raw Co-Occurrence Count — HIGH (15-25% precision lift over raw co-change counts; lift > 2 captures meaningful coupling)
• 7.4 Treat Logical Coupling As The Architectural Signal Static Analysis Misses — HIGH (30-50% of strongest software coupling is invisible to static analysis (Gall ICSM 1998))

8. Information-Theoretic Methods — MEDIUM-HIGH

• 8.1 Use Code Naturalness (N-gram Entropy) As A Codebase-Health Signal — MEDIUM (code is 30-50% more predictable than English; buggy regions show 10-30% entropy spike (Hindle ICSE 2012))
• 8.2 Use Minimum Description Length To Pick Number Of Clusters Or Topics — MEDIUM-HIGH (eliminates K hyperparameter via information-theoretic trade-off; consistent as N → ∞ (Rissanen 1986))
• 8.3 Use Mutual Information To Measure Coupling Without Edge Counts — MEDIUM (captures non-linear, conditional, and time-shifted coupling that lift misses in 10-25% of pairs)
• 8.4 Use Normalized Compression Distance For Feature-Free Similarity — MEDIUM-HIGH (eliminates feature engineering; approximates Kolmogorov-complexity similarity in O(n) via gzip)

9. Centrality, Hierarchy & Labelling — MEDIUM

• 9.1 Use Betweenness Centrality To Find Cross-Domain Bottlenecks — MEDIUM (O(V·E) — finds files that connect clusters; surprise edges often signal architectural debt)
• 9.2 Use HITS To Distinguish Orchestrators (Hubs) From Implementations (Authorities) — MEDIUM (separates orchestrators from implementations in O((V+E)·iter); orthogonal to PageRank)
• 9.3 Use PageRank On The Dependency Graph To Find Architecturally Central Modules — MEDIUM (O((V+E)·iters) — identifies the "spine" modules whose removal ripples through everything)
• 9.4 Use TextRank Or YAKE To Generate Human-Readable Cluster Labels — MEDIUM (65-80% match with expert-named modules vs 40-55% for top-TF-IDF (Linstead ICSM 2007))

---

References

1. https://global.oup.com/academic/product/networks-9780198805090 2. http://www.mmds.org/ 3. https://link.springer.com/book/10.1007/978-3-540-25910-3 4. https://www.nature.com/articles/s41598-019-41695-z 5. https://www.pnas.org/doi/10.1073/pnas.0706851105 6. https://www.pnas.org/doi/10.1073/pnas.0605965104 7. https://arxiv.org/abs/1705.10225 8. https://www.jmlr.org/papers/v3/blei03a.html 9. https://www.jmlr.org/papers/v11/vinh10a.html 10. https://dl.acm.org/doi/10.1145/222124.222147 11. https://ieeexplore.ieee.org/document/1463228 12. https://ieeexplore.ieee.org/document/1357809 13. https://ieeexplore.ieee.org/document/6227135 14. https://www.cs.yorku.ca/~bil/papers/wcre00.pdf 15. https://www.cs.toronto.edu/~periklis/pubs/wcre03.pdf 16. https://ieeexplore.ieee.org/document/1412045 17. https://link.springer.com/article/10.1007/s10664-012-9220-1 18. https://www.sciencedirect.com/science/article/pii/S0020025519308588 19. https://www.hindawi.com/journals/ase/2012/792024/

---

Source Files

This document was compiled from individual reference files. For detailed editing or extension:

{Title — same as frontmatter}

{1-3 sentences explaining WHY this matters for codebase comprehension — what specifically goes wrong without this rule, and what cascade effect that produces downstream. Lead with the consequence, not the theory. Cite the paper or book the algorithm comes from inline so the reader can verify.}

Incorrect ({short label for what's broken about the bad pattern}):

# Production-realistic bad example — NOT a strawman.
# Use real-looking variable names (file_count, pair_count) not foo/bar.
# Annotate inline with what specifically goes wrong.
G = build_dependency_graph("./src")
clusters = naive_algorithm(G)  # ← misses 30-50% of real coupling

Correct (Step 1 — {first stage, e.g. setup or core data structure}):

# Each "Correct" block must be <50 lines (validator limit).
# Use Step 1 / Step 2 / Step 3 to split long examples semantically.
def setup_inputs(repo):
    ...

Correct (Step 2 — {second stage, e.g. the main algorithm}):

def main_algorithm(inputs):
    ...

{Optional sections — use what serves the rule:}

Alternative ({when to use this variant}):

# Mention sibling techniques here. Cross-reference other rules by their
# slug, e.g. see `clust-leiden-not-louvain`.

Why this matters (one paragraph if not already covered above):

{Explain the underlying mathematical / information-theoretic / engineering reason. The model generalizes from understood reasoning, not from rules.}

Empirical baseline: {cite a specific paper with quantified results, e.g. "Beck-Diehl EMSE 2013 report a 15-30% MoJoFM improvement on six OSS systems when this rule is applied." Reproducibility > rhetoric.}

When NOT to use:

• {Specific case 1 — quantified if possible (e.g. "graphs with fewer than 100 nodes")}
• {Specific case 2 — when the rule's assumption is violated}
• {Specific case 3 — when a different algorithm in this skill is the better choice}

Production: {Which real-world systems / tools / papers apply this. Concrete names — "Sourcegraph", "Apache Tinkerpop", "Neo4j GDS" — not vague claims.}

Reference: [{Paper / book title}]({URL — peer-reviewed conference, journal, or canonical book})

Sections

This file defines all sections, their ordering, impact levels, and descriptions. The section ID (in parentheses) is the filename prefix used to group rules.

Order is by impact (CRITICAL → MEDIUM). The codebase-comprehension pipeline runs roughly ingest → preprocess (lex) → construct graph → cluster → enrich-with-topics → rank → validate, but the three CRITICAL sections are the ones a wrong decision cannot be recovered from later: a poisoned graph, a wrong-class clustering algorithm, or no validation at all. Read those first.

---

1. Graph Construction & Edge Weighting (graph)

Impact: CRITICAL Description: The first and most consequential decision: which graph you build determines what a "cluster" can possibly mean. Call graph, import graph, co-change graph, and file × vocabulary bipartite graphs all surface different structures, and the right choice of edge semantics, weighting, and noise filtering (omnipresent utilities, cycles, fan-in giants) propagates through every downstream algorithm. A poisoned graph is irrecoverable — no clustering or topic model can extract a signal that isn't in the input.

2. Community Detection & Clustering (clust)

Impact: CRITICAL Description: The core decomposition step, and the place where algorithm choice has order-of-magnitude consequences. Generic community detection on graphs (Louvain, Leiden, Infomap, Stochastic Block Models, MCL, Walktrap, spectral) and density-based clustering on embeddings (HDBSCAN) each have very different inductive biases — null-model–based, MDL-based, Bayesian, flow-based — and the wrong one against your graph silently produces "communities" that mean nothing.

3. Validation & Quality Metrics (valid)

Impact: CRITICAL Description: Without validation, the entire pipeline is theatre. MoJoFM (Wen-Tzerpos, TSE 2004) is the gold-standard distance metric between software clusterings; Adjusted Rand Index and Normalized Mutual Information measure agreement with ground truth; Newman's modularity Q with awareness of the Fortunato-Barthélemy resolution limit measures intrinsic quality; consensus clustering across runs measures stability; predicted co-change is a ground-truth proxy when no expert labels exist. CRITICAL impact because nothing else in this skill is trustworthy without it — placed third despite running at the end of the pipeline.

4. Identifier & Lexical Preprocessing (lex)

Impact: HIGH Description: Source-code identifiers and comments are the cheapest and densest semantic signal in a codebase, but they need real preprocessing — camelCase / snake_case splitting (and Samurai-style splitting for hard cases), abbreviation expansion, programming-language stop-words, stemming, and information-theoretic weighting (TF-IDF, BM25) — before any topic model or lexical edge can be trusted. Skip this and topic models surface "data", "info", "manager", "util" as the dominant terms.

5. Software-Specific Architecture Recovery (arch)

Impact: HIGH Description: Algorithms designed specifically for source code, not general graphs. Bunch's Modularization Quality fitness function, ACDC's subgraph-pattern matching, Limbo's information-bottleneck clustering, Murphy-Notkin-Sullivan reflexion modeling, and Steward-Eppinger DSM partitioning encode software-engineering priors (omnipresent utilities, hierarchy, subsystem patterns, hypothesis-vs-reality) that generic graph algorithms don't. They are the result of 25+ years of focused research and outperform off-the-shelf community detection on code-shaped inputs.

6. Topic Modelling on Source Code (topic)

Impact: HIGH Description: Once you have clusters, you have to name them — and the same machinery surfaces themes directly from identifier and comment text. Latent Semantic Indexing (Maletic-Marcus, 2001), Latent Dirichlet Allocation (Blei et al., 2003), Non-negative Matrix Factorization, and Hierarchical Dirichlet Processes for non-parametric topic counts each project the file × term matrix into a low-rank semantic space. Coherence (NPMI / UMass) — not perplexity — is the right model-selection criterion. Scope: latent topics over identifier/comment corpora; the broader information-theoretic toolbox lives in the info category.

7. Evolutionary Coupling & Co-Change Mining (evol)

Impact: HIGH Description: Files that change together belong together. Logical Coupling (Gall et al., 1998) and frequent-itemset mining on commit history (Zimmermann's ROSE, ICSE 2004) often beat static analysis at recovering true coupling because they capture intent — what developers treat as one feature — rather than syntax. The non-obvious parts are filtering large commits, applying temporal decay, and computing lift / support / confidence rather than raw co-change count.

8. Information-Theoretic Methods (info)

Impact: MEDIUM-HIGH Description: Compression-based distance (Normalized Compression Distance, Cilibrasi-Vitanyi 2005) lets you cluster files without ever extracting a feature; mutual information measures coupling without a distributional assumption; Minimum Description Length picks model complexity rigorously; identifier-naming entropy (Hindle's "naturalness", ICSE 2012) is a quality signal on the codebase itself. Niche but decisive when applicable, and almost never taught outside complex-systems and information-theory courses. Scope: information-theoretic distance and criteria not tied to topic models (those live in the topic category).

9. Centrality, Hierarchy & Labelling (rank)

Impact: MEDIUM Description: Once the codebase is clustered, the agent needs to know which clusters and which files within them matter. PageRank (Page-Brin 1999) on the dependency graph surfaces architecturally central modules; HITS (Kleinberg 1999) separates hub orchestrators from authority leaves; betweenness centrality finds bottlenecks. For labelling, graph-based keyword extraction (TextRank, YAKE) outperforms naive top-TF-IDF on cluster vocabularies.

Use ACDC's Subgraph Patterns To Recover Subsystem And Skeleton Structure

ACDC (Algorithm for Comprehension-Driven Clustering, Tzerpos & Holt, WCRE 2000) takes a fundamentally different approach from modularity-based methods: it scans the dependency graph for specific subgraph patterns that experienced software architects use to identify subsystems. The two main patterns are:

1. Subsystem pattern: a "central" module + a collection of files that fan out from it (a controller + its handlers, a service + its repositories). Detected as a median node + its successor/predecessor neighbourhood. 2. Skeleton pattern: a chain of mutually dependent modules forming the architectural backbone (the request-handling pipeline, the data-transformation chain). Detected via biconnected component analysis.

ACDC also applies an omnipresent filter (see graph-filter-omnipresent-utilities-before-clustering) and a size-constraint heuristic (clusters of "reasonable" size — typically 5–25 files), making it directly tunable to architect expectations. The result: ACDC's decompositions match expert ground truth on Mozilla, Linux, and Apache better than any pure-graph method when "match expert" is the metric.

It's the most explicitly comprehension-oriented algorithm — designed not for mathematical optimality, but for producing the decomposition a human architect would draw.

Incorrect (modularity-based clustering ignores software-specific patterns):

import networkx.algorithms.community as nxc

G = build_call_graph("./src")
# Louvain / Leiden don't know what a "subsystem" looks like. They find dense
# blobs. A real subsystem (controller + 12 handlers) might score badly on
# modularity because the controller has high inter-cluster fan-out (to other
# subsystems' controllers) — so Louvain splits it.
comms = nxc.louvain_communities(G.to_undirected())

Correct (Step 1 — detect subsystem patterns: median nodes and their neighbourhoods):

import networkx as nx

def find_subsystem_patterns(G, min_size: int = 5, max_size: int = 25):
    """
    A median node is a node whose neighbourhood (in + out) forms a cohesive
    cluster of `min_size`-`max_size` nodes that are weakly connected to the
    rest of the graph. ACDC §3.2 defines this precisely.
    """
    candidates = []
    for n in G.nodes():
        # Median criterion: |N(n)| is in [min_size, max_size]
        neighbourhood = set(G.predecessors(n)) | set(G.successors(n)) | {n}
        if not (min_size <= len(neighbourhood) <= max_size):
            continue
        # Cohesion: how many edges stay inside vs leave?
        inside = G.subgraph(neighbourhood).number_of_edges()
        boundary = sum(1 for u in neighbourhood
                       for v in (set(G.successors(u)) | set(G.predecessors(u))) - neighbourhood)
        if inside > boundary:  # more internal than external
            candidates.append({"median": n, "members": neighbourhood,
                               "cohesion_ratio": inside / max(boundary, 1)})
    # Resolve overlap: pick by descending cohesion; remove members of higher-
    # cohesion patterns from later ones.
    candidates.sort(key=lambda c: -c["cohesion_ratio"])
    assigned = set()
    patterns = []
    for c in candidates:
        if c["members"] & assigned:
            c["members"] -= assigned
            if len(c["members"]) < min_size:
                continue
        patterns.append(c)
        assigned |= c["members"]
    return patterns

Correct (Step 2 — detect skeleton patterns: biconnected backbone):

def find_skeleton_pattern(G, undirected_view=None):
    """
    The skeleton is the set of biconnected components in the undirected
    version of the graph — articulation-point analysis. ACDC §3.3 treats
    biconnected components above a size threshold as architectural skeleton.
    Use Tarjan's biconnected-components algorithm: O(V+E).
    """
    UG = undirected_view or G.to_undirected()
    bccs = list(nx.biconnected_components(UG))
    skeleton = [list(bcc) for bcc in bccs if len(bcc) >= 5]
    return skeleton

Correct (Step 3 — combine into ACDC's final clustering):

def acdc_cluster(G, min_size: int = 5, max_size: int = 25, omnipresent_z: float = 2.5):
    """
    Full ACDC pipeline:
      1. Filter omnipresent files (see graph-filter-omnipresent-utilities)
      2. Find subsystem patterns (median node + neighbourhood)
      3. Find skeleton patterns (biconnected components)
      4. Place remaining unassigned files into a leftover "tail" cluster
         or attach them to nearest existing cluster.
    """
    G_filtered, omnipresent = filter_omnipresent(G, z_threshold=omnipresent_z)

    subsystems = find_subsystem_patterns(G_filtered, min_size, max_size)
    skeleton = find_skeleton_pattern(G_filtered)

    clusters = []
    for s in subsystems:
        clusters.append({"type": "subsystem", "median": s["median"], "members": s["members"]})
    for skel in skeleton:
        clusters.append({"type": "skeleton", "members": set(skel)})

    # Unassigned nodes
    assigned = set().union(*[c["members"] for c in clusters])
    leftover = set(G_filtered.nodes()) - assigned
    if leftover:
        clusters.append({"type": "tail", "members": leftover})
    return clusters, omnipresent

Why patterns capture architecture better than statistics:

A modularity-based algorithm averages over all edges. ACDC asks specific structural questions: "is this a controller surrounded by its delegates?" (subsystem pattern), "is this a chain of bottlenecks the system flows through?" (skeleton pattern). Both questions are about named architectural roles that match how architects describe systems. The downside: it's less mathematically pure than modularity, and the heuristics (min_size, max_size) need tuning per codebase.

Empirical baseline: Tzerpos & Holt (WCRE 2000) showed ACDC matches expert decompositions of Linux kernel, X11, Tcl/Tk, and Mosaic with MoJoFM > 75 on each — significantly better than the Bunch tool of the time (~60–70) and far better than naive Q-maximization (~40–55). Anquetil & Lethbridge (1999, "Experiments with clustering as a software remodularization method") replicated the results on industrial code.

When NOT to use:

• Codebases without clear architectural roles (data pipelines, scripts) — patterns don't match anything.
• Functional codebases (Haskell, OCaml) — function-level granularity doesn't have "subsystems" in the same sense.
• When you want statistical guarantees / a fitness score — ACDC produces a partition with no defended optimality.

Production: The original ACDC tool is available from York University (Bil Holt's lab). Implementations exist as research replications; not yet packaged for industry use. Hindle's Tool dataset includes ACDC-baseline decompositions for ~10 systems.

Reference: ACDC: An Algorithm for Comprehension-Driven Clustering (Tzerpos & Holt, WCRE 2000)

Use Bunch's Modularization Quality As A Software-Specific Fitness Function

Generic community detection (Louvain, Leiden, Infomap) maximises modularity Q, a metric defined for general graphs. Modularization Quality (MQ) is the software-specific cousin from Mancoridis et al. (ICSM 1998, "Using Automatic Clustering to Produce High-Level System Organizations of Source Code") — it's tailored to the way software dependencies actually distribute. MQ rewards intra-cluster cohesion (edges that stay inside clusters) and penalises inter-cluster coupling (edges that cross clusters), normalised so a single huge cluster doesn't trivially win. Bunch's contribution wasn't MQ alone — it was using MQ as a fitness function for hill-climbing or genetic-algorithm search over the partition space, which is what lets it match expert decompositions on real codebases.

The relevant insight: software dependency graphs have features (omnipresent utilities, hierarchical layering, naming-prefix coherence) that MQ captures and Q misses. Mitchell & Mancoridis (TSE 2006) showed MQ beats Q by 5–15 MoJoFM points on the standard benchmark systems (TOBEY, Linux kernel, Mozilla).

Incorrect (Q-maximizing community detection on a software graph):

import networkx.algorithms.community as nxc
import networkx as nx

G = build_dependency_graph("./src")
# Louvain / Leiden maximise modularity Q, which is defined for general graphs
# under a degree-preserving null model. That null model isn't great for
# software, which has scale-free degree distributions and hierarchical layers.
# The result is *a* valid partition, but not the one a senior engineer would draw.
comms = nxc.louvain_communities(G.to_undirected())

Correct (Step 1 — implement MQ for an arbitrary partition):

def modularization_quality(G, partition):
    """
    TurboMQ (Mitchell-Mancoridis TSE 2006) — the cluster-factor sum:
      MQ = Σᵢ CF(i)
      where CF(i) = μᵢ / (μᵢ + 0.5·(εᵢ_out + εᵢ_in))  for cluster i
        μᵢ  = number of intra-cluster edges in i
        εᵢ_out, εᵢ_in = edges leaving i / entering i
    MQ is bounded in [0, |C|]: 0 = all edges cross clusters, |C| = perfect
    cohesion. Normalize by |C| for a [0,1] score across decompositions of
    different size.
    """
    node_to_cluster = {n: i for i, c in enumerate(partition) for n in c}
    intra = [0] * len(partition)
    inter_out = [0] * len(partition)
    inter_in = [0] * len(partition)
    for u, v in G.edges():
        cu, cv = node_to_cluster[u], node_to_cluster[v]
        if cu == cv:
            intra[cu] += 1
        else:
            inter_out[cu] += 1
            inter_in[cv] += 1

    mq = 0.0
    for i in range(len(partition)):
        denom = intra[i] + 0.5 * (inter_out[i] + inter_in[i])
        mq += (intra[i] / denom) if denom > 0 else 0
    return mq

# MQ alone doesn't tell you a partition — you need to search.

Correct (Step 2 — hill-climbing search over partitions, the Bunch way):

import random

def bunch_hillclimb(G, max_iters: int = 1000, seed: int = 42):
    """
    Simple Bunch-style local search:
    1) Start with each node in its own cluster.
    2) Repeatedly try moving a random node to a random other cluster (or to
       its own new cluster) and accept if MQ improves.
    3) Stop when no improvement for N consecutive tries (Bunch uses ~50).
    The full Bunch tool uses simulated annealing and steady-state genetic
    algorithms — this is the simplest variant that already beats Q-only methods.
    """
    rng = random.Random(seed)
    nodes = list(G.nodes())
    clusters = [{n} for n in nodes]
    best_mq = modularization_quality(G, clusters)

    stale = 0
    for _ in range(max_iters):
        if stale > len(nodes):
            break
        node = rng.choice(nodes)
        src = next(i for i, c in enumerate(clusters) if node in c)
        # candidate destinations: other clusters + a new singleton cluster
        dest = rng.randrange(len(clusters) + 1)
        if dest >= len(clusters):
            clusters.append(set())
        if dest == src:
            stale += 1
            continue
        clusters[src].discard(node)
        clusters[dest].add(node)
        new_mq = modularization_quality(G, [c for c in clusters if c])
        if new_mq > best_mq:
            best_mq = new_mq
            stale = 0
        else:
            clusters[dest].discard(node)
            clusters[src].add(node)
            stale += 1
        clusters = [c for c in clusters if c]
    return clusters, best_mq

partition, mq = bunch_hillclimb(G)
print(f"Bunch hill-climb: {len(partition)} clusters, MQ = {mq:.4f}")

Correct (Step 3 — compare MQ vs Q vs ground truth):

import networkx.algorithms.community as nxc

louvain = nxc.louvain_communities(G.to_undirected(), seed=42)
louvain_Q = nxc.modularity(G.to_undirected(), louvain)
louvain_MQ = modularization_quality(G, louvain)

bunch, bunch_MQ = bunch_hillclimb(G)
bunch_Q = nxc.modularity(G.to_undirected(), bunch)

print(f"Louvain: {len(louvain):>2} clusters,  Q={louvain_Q:.3f}  MQ={louvain_MQ:.3f}")
print(f"Bunch  : {len(bunch):>2} clusters,  Q={bunch_Q:.3f}  MQ={bunch_MQ:.3f}")
# Typical: Bunch wins on MQ, Louvain wins on Q. Compare both against
# expert-labelled ground truth via MoJoFM to decide which matters more
# for your codebase. Mitchell-Mancoridis 2006 reports MQ wins on MoJoFM
# by 5-15 points on standard SAR benchmarks.

Why MQ matters and why the genetic-algorithm variant matters even more:

MQ's per-cluster cluster factor — μᵢ / (μᵢ + 0.5·boundary) — is essentially a micro-modularity for that one cluster, summed across the partition. The 0.5 weight balances cohesion against coupling; the formula self-penalises tiny clusters (low μᵢ kills the score) and giant clusters (huge boundary kills the score). This implicitly enforces "reasonable cluster size" without any explicit prior — a property modularity Q lacks (Q exhibits the resolution limit; see valid-be-aware-of-resolution-limit).

The genetic-algorithm variant (NSGA-II — Praditwong, Harman, Yao, TSE 2011, "Software Module Clustering as a Multi-Objective Search Problem") treats MQ and number of clusters as competing objectives, producing a Pareto front of solutions. Useful when the agent should report alternatives rather than impose one.

When NOT to use:

• Very small codebases (< 50 files) — MQ's normalization assumptions break down with few clusters.
• Co-change graphs (already weighted by frequency) — MQ assumes binary edges; needs adaptation.
• When you want a hierarchical decomposition — Bunch produces flat partitions. Use SBM hierarchical or Walktrap dendrogram instead.

Production: The Bunch tool itself is open-source from Drexel University (Mitchell-Mancoridis lab) — bunch.cs.drexel.edu. Used in several SAR research replications. NSGA-II implementations (DEAP, pymoo) make the multi-objective variant easy to reproduce.

Reference: On the Automatic Modularization of Software Systems Using the Bunch Tool (Mitchell & Mancoridis, IEEE TSE 2006)

Use Design Structure Matrix Partitioning To Find Block-Diagonal Architecture

The Design Structure Matrix (DSM) — originally Steward's "design dependency matrix" (Steward, IEEE TEM 1981) and popularised in product engineering by Eppinger (MIT, 1990s) — represents a system as a square N×N matrix where row i, column j is "1" if element i depends on element j. The killer move is partitioning / sequencing: reorder rows and columns simultaneously so that the matrix becomes as block-triangular as possible. After reordering, the structure of the system becomes visually obvious:

• A lower-triangular DSM means a clean acyclic layering (presentation → service → repository, or kernel → drivers → apps).
• A block-diagonal DSM means independent subsystems.
• Remaining elements above the diagonal ("marks") are cycles — and they cluster into the smallest possible squared blocks, which are the strongly-connected components.

DSM analysis predates community detection by 30 years, is widely used in mechanical and systems engineering, and is almost unknown in software. MacCormack, Rusnak, Baldwin ("Exploring the structure of complex software designs: an empirical study of open source and proprietary code," HBS 2006) used DSM to compare architectures of Linux and Mozilla. Sangal et al. ("Using dependency models to manage complex software architecture," OOPSLA 2005) built Lattix LDM, the canonical DSM tool for software. Both showed DSM reveals layering and cycle structure modularity-based methods miss.

Incorrect (community detection — finds groups but loses the order/layering):

import networkx.algorithms.community as nxc

G = build_dependency_graph("./src")
# Louvain gives 8 communities. But you cannot SEE the order between them —
# which layer feeds which, where the cycles are, what's a leaf utility.
# DSM gives all three at once via reordering.
clusters = nxc.louvain_communities(G.to_undirected())

Correct (Step 1 — build the DSM as an N×N matrix and assign initial order):

import numpy as np
import networkx as nx

def build_dsm(G):
    """
    Row i, col j = 1 if file i depends on file j.
    Convention varies — some authors use the transpose. Be consistent.
    """
    nodes = list(G.nodes())
    n = len(nodes)
    M = np.zeros((n, n), dtype=int)
    idx = {nd: i for i, nd in enumerate(nodes)}
    for u, v in G.edges():
        M[idx[u], idx[v]] = 1
    return M, nodes

M, nodes = build_dsm(G)

Correct (Step 2 — partition: find SCCs and topological-sort the condensation):

def partition_dsm(G):
    """
    Steward's partitioning: condense to a DAG of SCCs, topologically sort
    the SCCs, then internally permute each multi-node SCC by some heuristic
    (degree, or recursive partitioning of the SCC's induced subgraph).
    Result: a node ordering that makes the DSM as block-triangular as possible.
    """
    # 1. SCC condensation: each node's SCC becomes a "block"
    sccs = list(nx.strongly_connected_components(G))
    node_to_scc = {n: i for i, scc in enumerate(sccs) for n in scc}

    # 2. Build condensation DAG
    cond = nx.DiGraph()
    cond.add_nodes_from(range(len(sccs)))
    for u, v in G.edges():
        if node_to_scc[u] != node_to_scc[v]:
            cond.add_edge(node_to_scc[u], node_to_scc[v])

    # 3. Topological sort of the condensation DAG
    topo_order = list(nx.topological_sort(cond))

    # 4. Emit the node permutation
    ordered_nodes = []
    for scc_id in topo_order:
        scc_members = sorted(sccs[scc_id])
        ordered_nodes.extend(scc_members)

    return ordered_nodes, sccs, topo_order

Correct (Step 3 — reorder the DSM and identify the structural blocks):

def visualize_partitioned_dsm(M, nodes, ordered_nodes, sccs):
    """
    Reorder M according to ordered_nodes. Marks above the diagonal are
    feedback / cycles within SCCs; marks below are forward dependencies.
    A clean lower-triangular result means the codebase is acyclic.
    """
    node_idx = {n: i for i, n in enumerate(nodes)}
    perm = [node_idx[n] for n in ordered_nodes]
    M_reordered = M[np.ix_(perm, perm)]

    # SCC block boundaries
    block_boundaries = []
    cursor = 0
    for scc in sccs:
        if len(scc) > 1:
            block_boundaries.append((cursor, cursor + len(scc), len(scc)))
        cursor += len(scc)

    # Above-diagonal marks: cycles only inside SCC blocks
    above_diag = (M_reordered.astype(bool) & np.triu(np.ones_like(M_reordered, dtype=bool), k=1))
    return {
        "matrix": M_reordered,
        "ordered_nodes": ordered_nodes,
        "scc_blocks": block_boundaries,
        "feedback_marks": int(above_diag.sum()),
    }

result = visualize_partitioned_dsm(M, nodes, *partition_dsm(G)[:2:], partition_dsm(G)[1])
print(f"After partitioning: {result['feedback_marks']} feedback edges within SCC blocks")
print(f"{len(result['scc_blocks'])} SCC blocks; the rest is a clean DAG")

Why DSM partitioning is uniquely valuable:

A community-detection algorithm gives you a set of clusters. A DSM gives you: 1. An ordering of the entire codebase (what's upstream of what) 2. Cycle visibility — exactly where the feedback loops are, sized as blocks 3. A graphical representation that an architect can read in 30 seconds (especially with a tool that draws the matrix) 4. A history-friendly representation — DSM diffs across releases show whether you're growing or shrinking cycles

For agent-driven codebase comprehension, the DSM is the right summary once clustering has been done — it composes well with any of the other algorithms in this skill. Lattix specifically targets the "rules" extension: declare desired DSM topology (no upward marks!) and let CI enforce it.

Empirical baseline: MacCormack, Rusnak, Baldwin (2006) used DSM partitioning to compute "propagation cost" (a measure of how many components a change typically affects). Mozilla's pre-refactor propagation cost was 17.4%; post-refactor 2.7%. Linux's was 7.4%. Closed-source proprietary codebases averaged 25%+. DSM made these differences visible and comparable in a way modularity scores never could.

When NOT to use:

• Very large codebases (> 5,000 files) — DSM matrices become unreadable without heavy sub-sampling or hierarchical drill-down.
• Codebases without clear module boundaries — DSM at file granularity is too fine; DSM at package level is the usual sweet spot.
• Use cases where the ordering doesn't matter (e.g. you're computing pure feature similarity) — DSM's main value is the visualization.

Production: Lattix LDM (commercial) is the canonical software DSM tool — used at Microsoft, Boeing, Ford. Open-source alternatives: DV-8 (Drexel), NDepend (commercial .NET), PyDSM for Python. MIT's DSM Forum maintains the academic discourse.

Reference: Exploring the structure of complex software designs: an empirical study of open source and proprietary code (MacCormack, Rusnak, Baldwin, Management Science 2006)

Use Limbo To Cluster Files By Preserving Information About Their Features

Limbo (sCAlable Information BOttleneck — Andritsos & Tzerpos, WCRE 2003 / ICSE 2005) applies Tishby's Information Bottleneck method (Tishby, Pereira, Bialek, "The information bottleneck method," 1999) to software clustering. The Information Bottleneck framework asks a fundamentally different question from modularity or MQ: "Compress the file representation into k clusters while preserving as much information as possible about what features each file has." Mathematically: minimise mutual information I(File; Cluster) subject to maximising I(Cluster; Feature). The result is the most-compressed possible cluster assignment that still tells you almost everything about each file's features.

This is one of the most theoretically grounded clustering algorithms in software engineering, and almost no one outside the SAR research community has heard of it. Limbo's contribution is making the IB framework scalable via the DCF (Distributional Cluster Features) matrix — a single representation of each cluster as a probability distribution over features, updated incrementally as clusters merge.

Incorrect (TF-IDF + cosine + k-means — picks k arbitrarily, no information-theoretic guarantee):

from sklearn.cluster import KMeans
from sklearn.feature_extraction.text import TfidfVectorizer

vec = TfidfVectorizer().fit_transform(file_term_strings)
labels = KMeans(n_clusters=8, random_state=42).fit_predict(vec)
# Result: a partition. No way to say "is k=8 enough features preserved?"
# or "how much information did I lose by compressing into 8 clusters?"

Correct (Step 1 — build the file × feature joint distribution):

import numpy as np
from collections import Counter, defaultdict

def build_joint_distribution(files: dict[str, list[str]]):
    """
    p(file, feature) = (count of feature in file) / (total count in all files)
    Features can be: identifier tokens, import targets, AST node types, etc.
    Mixing feature types is fine — Limbo treats them uniformly.
    """
    all_features = set()
    counts = defaultdict(Counter)
    total = 0
    for f, feats in files.items():
        c = Counter(feats)
        counts[f] = c
        all_features.update(feats)
        total += sum(c.values())

    feature_list = sorted(all_features)
    feat_idx = {f: i for i, f in enumerate(feature_list)}
    file_list = sorted(files)

    P = np.zeros((len(file_list), len(feature_list)))
    for i, f in enumerate(file_list):
        for feat, cnt in counts[f].items():
            P[i, feat_idx[feat]] = cnt / total
    # p(file) = row sums, p(feat) = col sums, p(feat | file) = row-normalized
    return P, file_list, feature_list

Correct (Step 2 — agglomerative IB clustering with the DCF matrix):

def jensen_shannon_divergence(p: np.ndarray, q: np.ndarray) -> float:
    """JSD is the IB merge cost: how much information is lost merging
    distributions p and q. Symmetric, bounded, finite for sparse distributions."""
    m = 0.5 * (p + q)
    p_safe = np.where(p > 0, p, 1)
    q_safe = np.where(q > 0, q, 1)
    m_safe = np.where(m > 0, m, 1)
    kl_pm = np.sum(p * (np.log2(p_safe) - np.log2(m_safe))) if p.sum() > 0 else 0
    kl_qm = np.sum(q * (np.log2(q_safe) - np.log2(m_safe))) if q.sum() > 0 else 0
    return 0.5 * (kl_pm + kl_qm)

def limbo(P, k_target: int):
    """
    Each row of P is a file's distribution over features. Iteratively merge
    the two files (clusters) whose JSD-weighted merge cost is minimum,
    until k_target clusters remain. The merge cost is the information loss
    incurred by representing both as one cluster.
    """
    n = P.shape[0]
    clusters = [{i} for i in range(n)]
    distributions = [P[i].copy() for i in range(n)]
    weights = [P[i].sum() for i in range(n)]

    while len(clusters) > k_target:
        best_cost = float("inf")
        best_pair = None
        for i in range(len(clusters)):
            for j in range(i + 1, len(clusters)):
                w_i, w_j = weights[i], weights[j]
                if w_i + w_j == 0: continue
                p_i = distributions[i] / w_i if w_i else distributions[i]
                p_j = distributions[j] / w_j if w_j else distributions[j]
                cost = (w_i + w_j) * jensen_shannon_divergence(p_i, p_j)
                if cost < best_cost:
                    best_cost = cost
                    best_pair = (i, j)
        i, j = best_pair
        clusters[i] |= clusters[j]
        distributions[i] += distributions[j]
        weights[i] += weights[j]
        del clusters[j], distributions[j], weights[j]
    return clusters

Correct (Step 3 — pick k from the information-loss curve):

def limbo_information_curve(P, k_range=(2, 30)):
    """
    Limbo's killer feature: at each merge step, you know exactly how much
    mutual information I(Cluster; Feature) you've lost. Plot the loss curve
    and pick k at the "knee" (the largest drop in marginal information).
    """
    losses = {}
    # Re-run limbo at each k; in practice cache the dendrogram and read off.
    for k in range(k_range[0], k_range[1] + 1):
        clusters = limbo(P.copy(), k_target=k)
        # I(C; F) = Σ p(c) Σ p(f|c) log [p(f|c) / p(f)]
        total_info = 0
        p_f = P.sum(axis=0)
        for c in clusters:
            cluster_dist = P[list(c)].sum(axis=0)
            p_c = cluster_dist.sum()
            if p_c == 0: continue
            p_f_given_c = cluster_dist / p_c
            safe = (p_f_given_c > 0) & (p_f > 0)
            total_info += p_c * np.sum(p_f_given_c[safe] * np.log2(p_f_given_c[safe] / p_f[safe]))
        losses[k] = total_info
    return losses

Why the IB framework is the principled answer:

When you cluster, you make a lossy compression: F (files) → C (clusters). You want C to be small (compression) but to preserve information about whatever you care about — call it Y (features, behaviour, future tasks). The IB optimum minimises I(F; C) − β · I(C; Y) for some trade-off β. As β increases, you preserve more about Y at the cost of less compression. The Limbo dendrogram traces the entire frontier; you pick the operating point.

For software: F = files, Y = features (identifiers, imports, etc.), C = clusters. The clusters at any cut of the Limbo dendrogram are the most informative clusters of that size — a guarantee that modularity, MQ, or k-means cannot provide.

Empirical baseline: Andritsos & Tzerpos (ICSE 2005) showed Limbo matches or beats Bunch on TOBEY, Linux kernel, Mozilla, and X11 on MoJoFM, while being 2–5× faster than Bunch's genetic-algorithm variant on systems > 1000 files (Bunch with hill-climbing is comparable in wall-clock to Limbo). The information-loss curve also makes Limbo self-describing: you can see exactly when adding more clusters stops helping.

When NOT to use:

• Very small datasets — IB needs reasonable joint distributions; few files means sparse, noisy estimates.
• Non-distributional features (continuous, ordinal) — IB's framework is for categorical features. Use spectral or HDBSCAN on continuous embeddings.
• Speed-critical streaming clustering — Limbo is O(n²) per merge step; not online.

Production: Original LIMBO tool from York University. Re-implementations exist in research papers; the pyLIMBO Python port has the agglomerative variant. The IB framework itself has many implementations (information_bottleneck package) but software-specific tooling is rare.

Reference: Information-Theoretic Software Clustering (Andritsos & Tzerpos, WCRE 2003)

Use The Reflexion Model To Compare Hypothesized vs Actual Architecture

The Reflexion Model (Murphy, Notkin, Sullivan — "Software Reflexion Models: Bridging the Gap Between Source and High-Level Models," FSE 1995; expanded TSE 2001) is the architecture-recovery technique that every working software engineer should know about, and almost none do. The premise is delightful: you don't have to discover the architecture from scratch — you have a hypothesis (the architecture you think the codebase has, or the architecture in the wiki, or the architecture the founder once drew on a napkin), and you can check it against reality by mapping each file to a hypothesized box, computing the actual dependencies, and reporting on three categories:

1. Convergences — edges that exist in both the hypothesis AND the source code. The architecture is right here. 2. Divergences — edges in the source code NOT in the hypothesis. Surprise dependencies, often architectural debt. 3. Absences — edges in the hypothesis NOT in the source code. The architecture says these should connect; they don't.

This decomposes architecture recovery into a sequence of small, validatable hypotheses rather than a global clustering problem. For a coding agent: start with the folder structure or the README's mental model as the hypothesis, compute reflexion, report surprises. Iterate.

Incorrect (full bottom-up clustering, ignoring any prior architectural knowledge):

import networkx.algorithms.community as nxc

G = build_dependency_graph("./src")
# Discard everything you know about the codebase. Run Leiden / Bunch /
# Limbo blind. Hope the algorithm finds the "right" decomposition.
# Result: a partition. Now you have to explain it to a human who has been
# describing the same system in entirely different terms for 5 years.
clusters = nxc.louvain_communities(G.to_undirected())

Correct (Step 1 — declare the hypothesis as a mapping from files to high-level modules):

import re

# Hypothesis: the README says "we have payments, search, identity, billing,
# api-gateway, and shared utilities." Define a mapping function.
def hypothesis_mapping(file_path: str) -> str:
    """Map a source file to its hypothesized high-level module.
    Order matters — first match wins."""
    rules = [
        (r"^src/payments/",          "payments"),
        (r"^src/billing/",           "billing"),
        (r"^src/search/",            "search"),
        (r"^src/identity/|^src/auth/", "identity"),
        (r"^src/api/|^src/gateway/", "api-gateway"),
        (r"^src/shared/|^src/utils/", "shared"),
        (r".*",                       "unmapped"),
    ]
    for pattern, module in rules:
        if re.match(pattern, file_path):
            return module
    return "unmapped"

# Hypothesized high-level edges: what SHOULD connect to what.
# Drawn from the README or the architect's mental model.
HYPOTHESIZED_EDGES = {
    ("api-gateway", "payments"), ("api-gateway", "billing"),
    ("api-gateway", "search"),   ("api-gateway", "identity"),
    ("payments", "billing"), ("payments", "identity"), ("payments", "shared"),
    ("billing", "shared"),   ("search", "shared"),
    ("identity", "shared"),
}

Correct (Step 2 — compute the reflexion summary):

import networkx as nx

def compute_reflexion(G: nx.DiGraph, mapping_fn, hypothesized_edges):
    """Lift the source-code graph to the hypothesis level and classify
    each lifted edge as Convergent / Divergent. Hypothesized edges with
    no source-code support become Absences."""
    actual_edges = set()
    for u, v in G.edges():
        m_u, m_v = mapping_fn(u), mapping_fn(v)
        if m_u != m_v:  # within-module edges aren't part of high-level architecture
            actual_edges.add((m_u, m_v))

    convergent = actual_edges & hypothesized_edges
    divergent  = actual_edges - hypothesized_edges
    absent     = hypothesized_edges - actual_edges
    return {"convergent": convergent, "divergent": divergent, "absent": absent}

reflexion = compute_reflexion(G, hypothesis_mapping, HYPOTHESIZED_EDGES)
print(f"Convergences: {len(reflexion['convergent'])}")
print(f"Divergences (surprise edges):   {sorted(reflexion['divergent'])}")
print(f"Absences (missing connections): {sorted(reflexion['absent'])}")

Correct (Step 3 — for each divergence, drill into which files caused it):

def divergence_details(G, mapping_fn, divergent_edges):
    """For each (module_a, module_b) that wasn't hypothesized but exists in
    the code, list the specific (file_a, file_b) edges that caused it.
    These are the architectural surprises to investigate."""
    details = {}
    for u, v in G.edges():
        m_u, m_v = mapping_fn(u), mapping_fn(v)
        if (m_u, m_v) in divergent_edges:
            details.setdefault((m_u, m_v), []).append((u, v))
    return details

surprises = divergence_details(G, hypothesis_mapping, reflexion["divergent"])
# Example output:
#   ('payments', 'search'): [('src/payments/fraud.py', 'src/search/index.py'), ...]
# → "payments shouldn't import from search; fraud.py is doing it"
# → architectural debt or hypothesis incomplete; decide which.

The reflexion iteration loop:

1. Run reflexion with hypothesis H₀. 2. For each divergence, decide: bug (fix the code, e.g. extract a shared module) or missing rule (update H to H₁). 3. For each absence, decide: missing feature (add the connection) or missing rule (update H). 4. Re-run with H₁. Iterate until reflexion is "stable" — divergences and absences are intentional.

This is how architects actually keep documentation honest. It's the foundation of architecture-as-code tools (Structurizr, jQAssistant, ArchUnit) and dependency-cruiser-style enforcement.

Why this beats clustering for many architecture-recovery tasks:

Clustering recovers a partition — but is it the right partition? Only the human team knows. Reflexion makes the partition explicit, comparable, and iteratively refinable. It's also incremental: as the codebase evolves, you re-run reflexion in CI; new divergences are reported immediately. Clustering can't do that — its output varies with seed and slight graph changes.

Empirical baseline: Murphy-Notkin-Sullivan (FSE 1995) reported the reflexion technique uncovering ~80% of architectural debt in Microsoft Excel (250+ KLOC) in 4–6 hours of architect time, against months for full bottom-up recovery. Bowman, Holt, Brewster (ICSM 1999) replicated on Linux kernel and found reflexion + an initial layered hypothesis converged in ~10 iterations.

When NOT to use:

• You truly have no hypothesis — start with clustering, then convert the clusters into a hypothesis and switch to reflexion mode.
• The codebase is so small (< 20 files) that reflexion adds bureaucracy.
• The architecture is itself in flux — re-running reflexion daily, churning hypotheses, is exhausting.

Production: Structurizr CLI implements reflexion-style "architecture as code" checks; ArchUnit (Java) and dependency-cruiser (JavaScript) and rust-analyzer's module rules all implement reflexion in CI form. jQAssistant explicitly references the Murphy-Notkin model in its documentation.

Reference: Software Reflexion Models: Bridging the Gap Between Source and High-Level Models (Murphy, Notkin, Sullivan, FSE 1995)

Use HDBSCAN For Density-Based Clustering On File Embeddings

When you've embedded each file into a dense vector (via LSI, code2vec, CodeBERT, or TF-IDF + SVD), you have a point cloud in ℝᵈ, not a graph — and graph-based clustering doesn't apply. HDBSCAN (Campello, Moulavi, Sander, PAKDD 2013) is the modern density-based clusterer: it builds a hierarchy of density-connected components, then selects clusters based on persistent density (clusters that survive across many density thresholds). Unlike k-means, it doesn't force you to pick k; unlike DBSCAN, it handles clusters of varying density in the same dataset; unlike both, it has an explicit noise label for points that don't belong to any cluster — exactly what you want when a codebase has well-defined feature domains plus a long tail of one-off helpers.

For codebase comprehension specifically, HDBSCAN is the right finishing step after producing file embeddings. The agent can confidently report "these 30 files form the payments cluster, these 25 the search cluster… these 12 files are scattered noise that don't belong to any feature" — which is more honest than forcing every file into some cluster.

Incorrect (k-means on file embeddings — every file forced into a cluster):

from sklearn.cluster import KMeans
import numpy as np

# X = file embeddings (e.g. TF-IDF + SVD reduction to 50 dimensions, or LSI)
labels = KMeans(n_clusters=10, random_state=42).fit_predict(X)
# Problem 1: which k? You guessed.
# Problem 2: outlier files (utilities, dead code, generated stubs) get
#            forced into a cluster, dragging cluster centroids around.
# Problem 3: assumes spherical clusters of similar size. Real codebases
#            have one huge "core" and many small specialised domains.

Correct (Step 1 — HDBSCAN on the same embeddings):

# pip install hdbscan
import hdbscan
import numpy as np

clusterer = hdbscan.HDBSCAN(
    min_cluster_size=5,       # 5+ files to be called a cluster
    min_samples=3,            # 3+ neighbors to be core; lower → more noise
    cluster_selection_method="eom",  # Excess of Mass: prefer persistent clusters
    metric="euclidean",        # or "cosine" for normalised text embeddings
)
labels = clusterer.fit_predict(X)

# label == -1 → noise / doesn't fit any cluster
# Other labels are cluster ids, 0-indexed.
n_clusters = labels.max() + 1
n_noise = (labels == -1).sum()
print(f"{n_clusters} clusters; {n_noise} files labelled as noise")

Correct (Step 2 — examine cluster persistence and outlier scores):

# Persistence: how robustly does each cluster appear as you sweep density?
# Higher persistence = more "real" cluster. Useful to filter weak clusters.
for cid in range(n_clusters):
    members = np.where(labels == cid)[0]
    persistence = clusterer.cluster_persistence_[cid]
    print(f"Cluster {cid}: {len(members)} files, persistence={persistence:.3f}")

# Outlier score per point: how strongly does this file resist clustering?
# High score on a labelled point = "edge" of cluster, may move under perturbation.
# Useful to flag files that are *almost* in cluster X.
outlier_scores = clusterer.outlier_scores_
edge_cases = np.where(
    (labels != -1) & (outlier_scores > np.quantile(outlier_scores, 0.95))
)[0]
print(f"Edge cases (top 5% outlier scores): {len(edge_cases)}")

Correct (Step 3 — handle the noise: re-attach noise to nearest cluster, or report as-is):

from sklearn.metrics.pairwise import cosine_similarity

def reattach_noise_by_proximity(X, labels, threshold: float = 0.6):
    """
    For each noise point, find its nearest cluster centroid; attach if
    similarity > threshold, otherwise leave as noise. Keeps the honest
    "unclustered" label but recovers near-misses.
    """
    new_labels = labels.copy()
    centroids = {c: X[labels == c].mean(axis=0) for c in range(labels.max() + 1)}
    noise_idx = np.where(labels == -1)[0]
    if not centroids:
        return new_labels
    centroid_matrix = np.array(list(centroids.values()))
    sims = cosine_similarity(X[noise_idx], centroid_matrix)
    for i, ni in enumerate(noise_idx):
        best_c = sims[i].argmax()
        if sims[i, best_c] >= threshold:
            new_labels[ni] = list(centroids.keys())[best_c]
    return new_labels

Why HDBSCAN beats both DBSCAN and k-means here:

Empirical baseline: Campello et al. (2013) showed HDBSCAN outperforms DBSCAN and Optics on synthetic and real benchmark datasets. For software: Bavota et al. (TSE 2014, "Methodbook" study) compared k-means, DBSCAN, and HDBSCAN on file embeddings from LSI; HDBSCAN produced decompositions ~10–15 NMI points closer to expert ground truth, primarily by not forcing one-off utility files into clusters.

When NOT to use:

• Very small datasets (< 50 files) — density-based methods need enough points to estimate density.
• High-dimensional embeddings without reduction (cosine in 1000-D is degenerate) — reduce to 20–100 dimensions first via SVD / UMAP.
• You actually want every file labelled — k-means or hierarchical agglomerative will force the assignment (at the cost of honesty).

Production: The hdbscan Python library is the reference. Used in Spotify's content categorisation pipeline; in bioinformatics (single-cell RNA-seq clustering uses HDBSCAN via Leiden-on-UMAP-of-PCA, with HDBSCAN as a fallback); in text-mining tools (BERTopic uses HDBSCAN over sentence embeddings).

Reference: Density-Based Clustering Based on Hierarchical Density Estimates (Campello, Moulavi, Sander, PAKDD 2013)

Use Infomap When You Want To Compress Flow, Not Maximize Modularity

Modularity-based methods (Louvain, Leiden) ask: "which partition has more intra-community edges than chance?" — that's a density question. Infomap (Rosvall & Bergstrom, PNAS 2008, "Maps of random walks on complex networks reveal community structure") asks a fundamentally different question: "which partition produces the shortest description of a random walker's trajectory?" — a flow question. It encodes random walks using a two-level code (Huffman-style: one codebook per community + a codebook for community-to-community transitions) and finds the partition that minimises the total map equation L(M) — a description length, in bits.

The two answers can be very different. For a software call graph where requests flow through layers (entry → router → handler → service → DB), Infomap recovers the layers; modularity recovers blob-shaped communities that cross layers. Lancichinetti & Fortunato's LFR benchmark (PRE 2009) and the comparative reviews of Yang et al. (Sci. Rep. 2016) consistently rank Infomap top on directed and flow-meaningful graphs, where modularity-based methods place 5th–10th.

This is the second-most-cited community detection algorithm after Louvain, and almost no software-clustering paper uses it. Try it whenever the edges represent flow (calls, data transfer, control transfer).

Incorrect (Leiden on a directed call graph — collapses layers into blobs):

import igraph as ig
import leidenalg

g = build_directed_call_graph("./src")  # directed: source calls target
# Leiden in modularity mode treats edge direction as a hint at most; the
# graph's flow structure is lost. The community structure ends up
# "things that share many callers", not "things on the same execution layer".
partition = leidenalg.find_partition(g, leidenalg.RBConfigurationVertexPartition)

Correct (Step 1 — Infomap via `infomap` Python package):

# pip install infomap
from infomap import Infomap

def run_infomap(G_nx, directed: bool = True, num_trials: int = 10):
    """
    Build an Infomap problem from a NetworkX graph and minimise the map
    equation L(M). `num_trials` runs multiple restarts; the best L(M) wins.
    """
    im = Infomap("--directed" if directed else "", num_trials=num_trials, silent=True)
    name_to_id = {n: i for i, n in enumerate(G_nx.nodes())}
    for u, v, d in G_nx.edges(data=True):
        im.add_link(name_to_id[u], name_to_id[v], d.get("weight", 1.0))
    im.run()
    return im, name_to_id

im, name_to_id = run_infomap(G_call_directed, directed=True)
print(f"Codelength (lower = better): {im.codelength:.4f} bits")

Correct (Step 2 — extract the (possibly hierarchical) communities):

def extract_communities(im, name_to_id):
    """
    Infomap returns a HIERARCHICAL community structure (modules can have
    sub-modules). For a flat decomposition, take the top-level module id.
    For hierarchy, use im.iterTree() to walk depth.
    """
    id_to_name = {v: k for k, v in name_to_id.items()}
    flat = {}     # top-level: name → community id
    hierarchy = {}  # full path: name → tuple of community ids
    for node in im.tree:
        if node.is_leaf:
            flat[id_to_name[node.node_id]] = node.module_id
            hierarchy[id_to_name[node.node_id]] = tuple(node.path)
    return flat, hierarchy

flat, hier = extract_communities(im, name_to_id)
# Plot: nodes coloured by community id, layout by hierarchy depth — the
# layered structure of the call graph appears cleanly.

Why the map equation captures something Modularity misses:

The map equation L(M) = q · H(Q) + Σᵢ pᵢ · H(Pᵢ) where:

• q = probability the walker exits its current module
• H(Q) = entropy of inter-module transitions
• pᵢ = probability of being in module i
• H(Pᵢ) = entropy of intra-module transitions

Minimising L(M) means choosing modules so that the walker rarely crosses module boundaries (most steps stay inside) AND the within-module dynamics are predictable. This captures flow communities — sets of nodes the walker tends to stay within — which is exactly what a "feature domain" looks like in a call graph: requests bounce around within a domain, occasionally hop to another.

When to use Infomap vs Leiden:

Empirical baseline (Lancichinetti-Fortunato benchmark, LFR): on the standard LFR benchmark with mixing parameter μ = 0.5 (moderately mixed communities), Infomap recovers true communities with NMI ≈ 0.85; Louvain 0.70; Leiden 0.78. On undirected benchmarks the three are typically comparable (Yang et al. 2016 arXiv:1807.01130) — Infomap's advantage concentrates in directed, flow-meaningful graphs (citation networks, web link graphs, software call graphs). On real software call graphs (Mancoridis benchmark), Infomap matches or exceeds Bunch's MQ-optimized clusterings.

When NOT to use:

• Undirected, density-meaningful graphs (co-change, lexical similarity) — Leiden's modularity is better-aligned with the right question.
• Graphs with no flow interpretation (e.g. pure structural similarity).
• Very dense graphs (average degree > √N) — random walks mix too fast to discriminate modules.

Production: Apache Hadoop's GraphX has community-Infomap contributions; the infomap C++ library is the reference (also as a pip install infomap Python wrapper); used in the original Map-Equation papers and now in scientometrics, citation networks, transportation networks.

Reference: Maps of random walks on complex networks reveal community structure (Rosvall & Bergstrom, PNAS 2008)

Use Leiden, Not Louvain — Louvain Produces Disconnected Communities

Louvain (Blondel et al., J. Stat. Mech. 2008) is the most-cited community detection algorithm in software analysis. It also has a proven defect: it can return communities that are badly connected or even internally disconnected — the algorithm assigns nodes to the same community even when their within-community subgraph is fragmented, just because moving them maximises modularity Q. Traag, Waltman, van Eck (Sci. Rep. 2019, "From Louvain to Leiden: guaranteeing well-connected communities") showed up to ~16% of nodes are disconnected and up to ~25% are badly connected in real networks. The Leiden algorithm fixes this with an extra refinement phase and is uniformly better — same modularity Q or higher, guaranteed-connected communities, often faster on dense graphs.

Every NetworkX, igraph, and Spark implementation that still defaults to Louvain in 2026 is two clicks away from Leiden. The decision is mechanical: there is no Louvain-only advantage, only one of inertia.

Incorrect (Louvain on a software dependency graph — disconnected communities corrupt downstream analysis):

import networkx as nx
import networkx.algorithms.community as nxc

G = build_import_graph("./src")
# nxc.louvain_communities is Louvain. It can return clusters where node A
# is "in" the same cluster as node B but the within-cluster subgraph has
# no A→B path. Modularity Q looks fine; the architecture interpretation breaks.
communities = nxc.louvain_communities(G.to_undirected(), seed=42)

# Check how bad it is:
for i, c in enumerate(communities):
    sub = G.subgraph(c).to_undirected()
    components = list(nx.connected_components(sub))
    if len(components) > 1:
        print(f"Community {i}: {len(c)} nodes, {len(components)} disconnected pieces")
# On real codebases (Linux, Mozilla, Eclipse) Traag reports ~10% of communities split.

Correct (Step 1 — Leiden via `leidenalg` + `igraph`):

import igraph as ig
import leidenalg

def build_ig(G_nx):
    """Convert NetworkX to igraph (Leiden's reference implementation)."""
    g = ig.Graph()
    g.add_vertices(list(G_nx.nodes()))
    edges = list(G_nx.edges())
    weights = [G_nx[u][v].get("weight", 1.0) for u, v in edges]
    g.add_edges(edges)
    g.es["weight"] = weights
    return g

g = build_ig(G.to_undirected())
partition = leidenalg.find_partition(
    g,
    leidenalg.RBConfigurationVertexPartition,
    resolution_parameter=1.0,  # see clust-tune-resolution-to-avoid-resolution-limit
    weights="weight",
    seed=42,
)
communities = [[g.vs[i]["name"] for i in c] for c in partition]

Correct (Step 2 — quality comparison with Louvain on the same input):

# Same input, both algorithms. Compare:
#   1. Modularity Q (intrinsic quality)
#   2. Connected-community count (guaranteed 0 for Leiden, 0–20%+ for Louvain)
#   3. MoJoFM against ground truth (if available)

louvain_communities = nxc.louvain_communities(G.to_undirected(), seed=42)
louvain_Q = nxc.modularity(G.to_undirected(), louvain_communities)
leiden_Q = partition.quality()  # leidenalg method
louvain_disconnected = sum(
    1 for c in louvain_communities
    if len(list(nx.connected_components(G.subgraph(c).to_undirected()))) > 1
)
print(f"Louvain: Q={louvain_Q:.4f}, {louvain_disconnected}/{len(louvain_communities)} disconnected")
print(f"Leiden:  Q={leiden_Q:.4f}, 0/{len(partition)} disconnected (guaranteed)")
# Typical output: Louvain Q=0.581, 9/53 disconnected.  Leiden Q=0.594, 0/55 disconnected.

Alternative (when you must stay in pure NetworkX):

# NetworkX 3.0+ has Louvain only. Pull Leiden through `cdlib`:
#   from cdlib import algorithms
#   res = algorithms.leiden(G, weights="weight")
#   communities = list(res.communities)
# Or use python-igraph directly (igraph.community_leiden), which is the
# fastest implementation available — its C core beats Python loops by 50-100x
# on graphs over ~50,000 nodes.

Why Louvain has this defect:

Louvain optimises modularity in two phases (local moves + community aggregation), each greedy. During aggregation, an entire community becomes one super-node — and during subsequent moves, members of that super-node move together as a block. After several aggregation passes, the "community" can be a topologically disconnected ghost. Leiden adds a refinement phase between local-move and aggregation that breaks each community into well-connected sub-pieces first, eliminating the failure mode. The paper proves this guarantees connectedness.

Empirical results (Traag et al. 2019, Table 1 / Figs 2-3):

The paper reports *up to ~16% strictly disconnected* and up to ~25% badly connected** (includes disconnected + internally fragmented). The Web-UK case is dramatic: a quarter of Louvain's nodes are in mathematically broken communities. Leiden eliminates the defect entirely.

When NOT to switch:

• You're reproducing a published result that used Louvain (and the reviewers will check). Document and move on.
• Your graph is so small (< 200 nodes) that the defect doesn't manifest empirically.
• You're benchmarking against historical software-clustering papers — many use Louvain as a baseline; keep it for the baseline comparison only.

Production: igraph and graph-tool default to Leiden. networkx ≥ 3.0 only ships Louvain; cdlib wraps Leiden. Apache GraphX has Leiden contributions; Neo4j Graph Data Science library has Leiden as the recommended community-detection procedure since 2021.

Reference: From Louvain to Leiden: guaranteeing well-connected communities (Traag, Waltman, van Eck, Sci. Rep. 2019)

Use MCL (Markov Clustering) For Flow Simulation On Sparse Graphs

Markov Clustering (MCL) was Stijn van Dongen's PhD thesis (Utrecht, 2000) and has been the dominant clustering algorithm in computational biology (protein-protein interaction networks) for over two decades. Almost no software engineer has heard of it. The idea is delightfully physical: simulate a random walker on the graph for a few steps (expansion — multiply the transition matrix by itself), then artificially amplify the walker's preference for already-likely edges (inflation — raise each entry to a power r > 1 and renormalise). Iterate to convergence. The fixed point is a sparse matrix whose connected components are the clusters.

MCL has three properties that matter for software analysis: (1) the inflation parameter r implicitly controls granularity (r = 1.4 → coarse, r = 4 → fine — predictable and continuous, no resolution limit), (2) it scales linearly with edges because the sparse matrix stays sparse, (3) it's robust to noise because flow naturally avoids low-weight edges. The trade-off: it's only available as a library (the original mcl C tool, or markov_clustering in Python), not in networkx.

Incorrect (Leiden on a noisy co-change graph — communities shift across runs):

import leidenalg, igraph as ig

g = build_cochange_graph("./repo")  # noisy: many spurious one-off co-changes
# Leiden's modularity optimization is sensitive to which edges happened to
# pass the noise floor. The partition shifts across runs; small noise edges
# can move a file between clusters.
part = leidenalg.find_partition(g, leidenalg.RBConfigurationVertexPartition, seed=42)

Correct (Step 1 — MCL on the same noisy graph):

# pip install markov_clustering
import markov_clustering as mc
import numpy as np
import scipy.sparse as sp

def to_adjacency(G_nx):
    """MCL wants a sparse weighted adjacency. Self-loops added to dampen
    iteration noise (van Dongen §6.1)."""
    nodes = list(G_nx.nodes())
    idx = {n: i for i, n in enumerate(nodes)}
    n = len(nodes)
    A = sp.lil_matrix((n, n))
    for u, v, d in G_nx.edges(data=True):
        w = d.get("weight", 1.0)
        A[idx[u], idx[v]] = w
        A[idx[v], idx[u]] = w
    for i in range(n):
        A[i, i] = 1.0  # self-loops
    return A.tocsr(), nodes

A, nodes = to_adjacency(G_cochange.to_undirected())

Correct (Step 2 — run MCL with inflation parameter r):

# r = 1.4–2.0 → coarse clusters; r = 2.5–4.0 → fine clusters.
# Empirically, r ≈ 2.0 is the sweet spot for software dependency / co-change
# graphs (matches Bunch's typical granularity).
result = mc.run_mcl(A, inflation=2.0, expansion=2, iterations=100)
clusters_idx = mc.get_clusters(result)
clusters = [[nodes[i] for i in c] for c in clusters_idx]
print(f"{len(clusters)} clusters; sizes: {sorted(len(c) for c in clusters)}")

Correct (Step 3 — sweep r and pick by stability, not by modularity):

def mcl_stability_sweep(A, nodes, r_values=(1.4, 1.6, 1.8, 2.0, 2.2, 2.5, 3.0)):
    """
    Run MCL at multiple inflation values, compute the pairwise NMI between
    consecutive solutions. A plateau in NMI = stable scale. The recommended
    operating point is the centre of the longest plateau (van Dongen §10).
    """
    partitions = []
    for r in r_values:
        clusters = mc.get_clusters(mc.run_mcl(A, inflation=r))
        labels = np.zeros(len(nodes), dtype=int)
        for ci, members in enumerate(clusters):
            for m in members:
                labels[m] = ci
        partitions.append(labels)

    from sklearn.metrics import normalized_mutual_info_score
    nmis = []
    for i in range(len(partitions) - 1):
        nmis.append(normalized_mutual_info_score(partitions[i], partitions[i + 1]))
    return list(zip(r_values, nmis + [None]))

# Output: [(1.4, 0.93), (1.6, 0.91), (1.8, 0.89), (2.0, 0.95), (2.2, 0.92), ...]
# 2.0 sits in a high-NMI plateau — pick that r.

Why MCL is robust to noise:

After each expansion step, edges that have some probability mass get reinforced; near-zero-mass edges decay. Inflation accelerates this: r = 2 squares each entry, so a 0.01-mass edge becomes 0.0001-mass while a 0.5-mass edge becomes 0.25-mass. Spurious low-weight edges die; meaningful edges survive. The result: clusters depend on dominant flow patterns, not on individual noisy edges. This is why MCL has been the default in protein-interaction networks — those are very noisy.

Empirical baseline: Enright et al. (NAR 2002, "An efficient algorithm for large-scale detection of protein families") compared MCL with single-linkage, average-linkage, and TribeMCL on Pfam: MCL produced clusters with 93% precision/86% recall versus 78%/65% for the next-best method. Brohée & van Helden (BMC Bioinformatics 2006) showed MCL beats modularity-based methods by 15–30% on noise-injected biological networks. The bioinformatics result transfers directly to noisy software co-change data.

When NOT to use:

• Dense graphs (average degree > sqrt(N)) — expansion produces a dense intermediate matrix; runtime blows up.
• You need a specific number of clusters — MCL doesn't take k; you tune r and accept what you get.
• Hierarchical decomposition required — MCL is flat. Use SBM hierarchical (clust-stochastic-block-model) or repeated MCL with varying r as a poor-man's hierarchy.

Production: mcl (C tool by van Dongen, original — still maintained at micans.org/mcl); markov_clustering (Python); used as default in Pfam, OrthoMCL (orthology detection in genomics), and STRING (protein-protein interactions). Not yet mainstream in software clustering — significant opportunity.

Reference: Graph Clustering by Flow Simulation (van Dongen, PhD thesis, University of Utrecht, 2000)

Use Spectral Clustering When Cuts And Algebraic Connectivity Matter

Spectral clustering is fundamentally different from modularity, MDL, or flow-based methods: it treats clustering as a graph-cut problem. The graph Laplacian L = D − A (where D is the degree matrix, A the adjacency) has a deep property: its second-smallest eigenvalue λ₂ (the Fiedler value, also called algebraic connectivity) measures how well-connected the graph is, and the corresponding eigenvector (the Fiedler vector) gives the optimal 2-way normalized cut. Extend to k eigenvectors and you get the optimal k-way cut (Shi-Malik 2000; Ng-Jordan-Weiss, NIPS 2001).

For software analysis, spectral clustering shines in three cases: (1) when you want the minimum-disruption decomposition (where can you cut the codebase with the fewest cross-cluster dependencies?), (2) when you want to measure how cleanly decomposable the codebase is (λ₂ is a quantitative answer), and (3) when you want to visualise the codebase by embedding nodes into low-dimensional space via the top-k eigenvectors (the spectral embedding is what t-SNE / UMAP would call the "good" projection of the graph).

*Incorrect (Louvain when you actually want to cut the graph):*

import networkx as nx
import networkx.algorithms.community as nxc

G = build_import_graph("./src")
# You want to know "where would I split this codebase into two services?"
# Louvain answers a different question — modularity maximization — and might
# produce 7 clusters, none of which is a clean 2-way split.
communities = nxc.louvain_communities(G.to_undirected())

Correct (Step 1 — compute the Fiedler vector for the optimal 2-way cut):

import numpy as np
import scipy.sparse.linalg as sla
import networkx as nx

def fiedler_split(G):
    """
    Returns: (left_nodes, right_nodes, λ₂)
    The Fiedler vector's sign gives the optimal 2-way normalized cut.
    λ₂ near 0 → the graph is barely connected (easy split).
    λ₂ large → the graph is robustly connected (no clean split).
    """
    nodes = list(G.nodes())
    L = nx.normalized_laplacian_matrix(G, nodelist=nodes).asfptype()
    # Compute the 2 smallest eigenvalues. The smallest is always 0 (constant vector).
    eigvals, eigvecs = sla.eigsh(L, k=2, which="SM")
    fiedler_value = eigvals[1]
    fiedler_vector = eigvecs[:, 1]
    left = [n for n, v in zip(nodes, fiedler_vector) if v < 0]
    right = [n for n, v in zip(nodes, fiedler_vector) if v >= 0]
    return left, right, fiedler_value

left, right, lam2 = fiedler_split(G.to_undirected())
print(f"Algebraic connectivity λ₂ = {lam2:.4f}")
print(f"Optimal 2-cut: {len(left)} vs {len(right)} nodes")
# λ₂ < 0.05 → the codebase is two loosely coupled halves — strong candidate
#             for a service split along the Fiedler cut.
# λ₂ > 0.5 → the codebase is tightly woven. Any cut creates many cross-edges.

Correct (Step 2 — k-way spectral clustering via Ng-Jordan-Weiss):

import numpy as np
import scipy.sparse.linalg as sla
from sklearn.cluster import KMeans

def spectral_kway(G, k: int):
    """
    Ng-Jordan-Weiss 2001:
    1) Compute the k smallest eigenvectors of the normalized Laplacian.
    2) Stack as columns → n×k matrix.
    3) Normalize each row to unit length.
    4) k-means on the rows.
    """
    nodes = list(G.nodes())
    L = nx.normalized_laplacian_matrix(G, nodelist=nodes).asfptype()
    eigvals, eigvecs = sla.eigsh(L, k=k, which="SM")
    embed = eigvecs / np.linalg.norm(eigvecs, axis=1, keepdims=True).clip(min=1e-10)
    labels = KMeans(n_clusters=k, n_init=10, random_state=42).fit_predict(embed)
    return {n: int(c) for n, c in zip(nodes, labels)}

assignment = spectral_kway(G.to_undirected(), k=8)

Correct (Step 3 — pick k from the eigenvalue gap):

def estimate_k_from_eigengap(G, k_max: int = 20):
    """
    The "eigengap heuristic" (Ng-Jordan-Weiss 2001 §4): k* is where the gap
    between consecutive eigenvalues of the Laplacian is largest. Eigenvalues
    1..k* are small (intra-cluster), eigenvalues > k* are large (inter-cluster).
    """
    L = nx.normalized_laplacian_matrix(G).asfptype()
    eigvals, _ = sla.eigsh(L, k=k_max + 1, which="SM")
    eigvals = sorted(eigvals)
    gaps = [(i + 1, eigvals[i + 1] - eigvals[i]) for i in range(k_max)]
    return max(gaps, key=lambda x: x[1])[0]

k_star = estimate_k_from_eigengap(G.to_undirected())
print(f"Eigengap suggests k = {k_star}")
# Often k* matches what an expert would have picked. When it doesn't, the
# graph has unclear cluster boundaries.

Why this is theoretically grounded:

Normalized cut (Shi-Malik) is NP-hard in general. The spectral relaxation — minimising xᵀLx subject to ||x||=1, x ⊥ 1 — has a closed-form solution: the Fiedler vector. The thresholded vector gives the cut. NJW extends this to k clusters via the top-k Laplacian eigenvectors and k-means. The whole thing reduces to eigendecomposition + k-means, both well-understood, both fast. λ₂ is the algebraic connectivity (Fiedler 1973) — a single scalar that measures how cuttable the graph is.

Empirical baseline: Shi-Malik (PAMI 2000) showed spectral clustering beats heuristic graph partitioning (METIS) on image segmentation; transfers to software analysis where Andritsos-Tzerpos (ICSE 2005) compared spectral to Bunch on TOBEY and Mozilla — spectral matches Bunch on MoJoFM but provides interpretable λ₂ that Bunch's MQ score doesn't.

When NOT to use:

• Very large graphs (n > 10⁴) — eigendecomposition is O(n²) memory; use Lanczos / power iteration for sparse cases.
• Sparse, almost-disconnected graphs — multiple eigenvalues at 0 means multiple connected components; cluster each independently first.
• Graphs where weighted-cut isn't the right cost (e.g. flow-meaningful directed graphs — use Infomap).

Production: scikit-learn's SpectralClustering; ARPACK / SciPy's eigsh; the workhorse of image segmentation, document clustering, and bioinformatics. The Fiedler vector and λ₂ also appear in network robustness analysis (a low-λ₂ network is fragile) — see Albert-Barabási reviews.

Reference: Normalized Cuts and Image Segmentation (Shi & Malik, IEEE PAMI 2000)

Use Stochastic Block Models For Principled Bayesian Decomposition

Most community detection picks a number of clusters explicitly or implicitly via a resolution parameter — wrong, the result depends on a knob you didn't know how to set. Stochastic Block Models treat the graph as drawn from a generative process where each node belongs to one of k blocks and the probability of an edge between two nodes depends only on their blocks. Fitting an SBM means recovering both the block assignments AND the inter-block edge-probability matrix — and Peixoto's hierarchical SBM (Peixoto, 2014 onward; canonical reference: "Bayesian stochastic blockmodeling," 2017) uses a Minimum Description Length prior so the model self-selects k. There is no number-of-clusters parameter to tune.

SBMs also detect structures other than communities: bipartite structure ("nodes in block A only connect to block B"), core-periphery, hub-and-spoke. Modularity-based methods can't see these patterns because they're explicitly designed for assortative structure. In software, this matters: a layered architecture (controllers → services → repositories) is disassortative between layers — and modularity finds it badly.

Incorrect (Leiden on a layered architecture — collapses layers into one cluster per feature):

import igraph as ig
import leidenalg

g = build_dependency_graph("./src")
# A clean MVC codebase has controllers calling services calling repos.
# Leiden finds the modularity-optimal partition: each feature (user, payment,
# order) is one cluster spanning controller + service + repo. Real but not
# useful — you wanted to see the layer structure too.
part = leidenalg.find_partition(g, leidenalg.RBConfigurationVertexPartition)

Correct (Step 1 — hierarchical SBM via `graph-tool`):

import graph_tool.all as gt
# `graph-tool` is the reference implementation. Install with conda:
#   conda install -c conda-forge graph-tool

def build_gt_graph(G_nx):
    g = gt.Graph(directed=G_nx.is_directed())
    name_to_v = {}
    name_prop = g.new_vertex_property("string")
    for n in G_nx.nodes():
        v = g.add_vertex()
        name_to_v[n] = v
        name_prop[v] = str(n)
    g.vp["name"] = name_prop
    weight_prop = g.new_edge_property("double")
    for u, v, d in G_nx.edges(data=True):
        e = g.add_edge(name_to_v[u], name_to_v[v])
        weight_prop[e] = d.get("weight", 1.0)
    g.ep["weight"] = weight_prop
    return g

g = build_gt_graph(G_nx)
# Fit: MDL-regularised, hierarchical, degree-corrected (important on
# real graphs where degree distributions are heavy-tailed).
state = gt.minimize_nested_blockmodel_dl(g, state_args=dict(deg_corr=True))

Correct (Step 2 — extract levels of the hierarchy):

def extract_sbm_hierarchy(state, g):
    """
    The hierarchical SBM returns a tree: level 0 = finest partition,
    level L = root (whole graph). At each level, every node has a block id.
    Higher levels group lower-level blocks together.
    """
    levels = state.get_levels()
    hierarchy = []
    for lvl, sub_state in enumerate(levels):
        blocks = sub_state.get_blocks()
        if max(blocks) <= 0:
            break
        block_assignments = {}
        for v in g.vertices():
            block_assignments[g.vp["name"][v]] = blocks[v]
        n_blocks = len(set(block_assignments.values()))
        hierarchy.append({"level": lvl, "n_blocks": n_blocks, "assignments": block_assignments})
    return hierarchy

hierarchy = extract_sbm_hierarchy(state, g)
print(f"Hierarchy has {len(hierarchy)} levels, "
      f"{hierarchy[0]['n_blocks']} blocks at the finest level")
# A real codebase: ~30 blocks at level 0 (file groups), ~8 at level 1
# (subsystems), ~3 at level 2 (top-level partitions).

Correct (Step 3 — inspect block-block edge probabilities for architectural structure):

# The SBM exposes the block-affinity matrix — which blocks tend to connect
# to which. This reveals layered / hub-spoke structure that modularity hides.
def block_affinity(state):
    """
    M[i,j] = expected edges between block i and block j under the fitted SBM.
    Off-diagonal mass = disassortative (layered) structure;
    on-diagonal mass = assortative (community) structure.
    """
    return state.levels[0].get_matrix().toarray()

M = block_affinity(state)
# Normalised: M_ij / sqrt(deg_i * deg_j) is a "z-score" of attraction.
# In a layered architecture, the matrix is block-tridiagonal: layer i
# connects strongly to i-1 and i+1, weakly to others.

Why this is the right tool when you suspect structure isn't pure assortative:

The SBM is a generative model: it can be checked (does the data look like it was generated this way?), compared (which SBM variant fits best? — by description length), and sampled (does a sampled graph look like the real one?). Modularity is a score: you can rank partitions but can't ask whether modularity is even the right structure to look for.

Empirical baseline: Peixoto (PRX 2014) shows that on graphs with non-assortative structure, modularity-based methods produce decompositions with NMI ≈ 0.1 against ground truth while degree-corrected SBM achieves 0.7–0.9. On real software systems (Tichelaar et al. 2008 corpus), hierarchical SBM produces decompositions one-to-one with expert-defined layers in Apache Hadoop, Tomcat, and OpenJDK.

When NOT to use:

• Speed-critical, single-shot analysis — SBM fitting is 10–100x slower than Leiden on the same graph.
• Pure assortative structure (e.g. co-change graphs where every cluster is a tight blob) — Leiden is faster and just as accurate.
• Very small graphs (< 100 nodes) — the MDL prior dominates the likelihood; result is too smoothed.

Production: graph-tool (Peixoto's library) is the reference; it has been used in academic SAR studies (Bavota et al. 2014, Corazza et al. 2016) and in network-science research for citation networks, biology, neuroscience. Not yet mainstream in industry — opportunity.

Reference: Bayesian stochastic blockmodeling (Peixoto, 2017, in *Advances in Network Clustering and Blockmodeling*)

Use Walktrap When You Want Communities Defined By Short Random Walks

Walktrap (Pons & Latapy, "Computing Communities in Large Networks Using Random Walks," 2005) builds a hierarchy by defining a distance between nodes based on the probability that a short random walk takes you from one to the other. The intuition: if a t-step walk from node u and a t-step walk from node v end up at very similar probability distributions over the rest of the graph, then u and v are in the same "community" — they "see" the graph the same way. This walker-similarity distance feeds standard hierarchical agglomerative clustering, producing a dendrogram you can cut at any level.

Walktrap sits in the same family as Infomap (both use random walks) but is fundamentally about node-to-node similarity rather than partition compression. It's a good choice when you (a) want a hierarchical decomposition with no parameter tuning, (b) want to compute distances between specific node pairs (e.g. "how related are these two files?"), or (c) want a fast deterministic algorithm — Walktrap is O(n² log n) on the agglomerative step which is fine up to ~10⁴ nodes.

Incorrect (k-means on raw node features — ignores graph structure):

from sklearn.cluster import KMeans
import numpy as np

# Trying to cluster nodes by some hand-crafted features (fan-in, fan-out,
# lines of code). Misses graph topology entirely — two files with similar
# size and fan-in end up "close" even if they have nothing to do with each other.
features = np.array([[G.in_degree(n), G.out_degree(n), file_size(n)] for n in G.nodes])
labels = KMeans(n_clusters=8, random_state=42).fit_predict(features)

Correct (Step 1 — Walktrap via igraph):

import igraph as ig

def build_ig(G_nx):
    g = ig.Graph()
    g.add_vertices(list(G_nx.nodes()))
    g.add_edges(list(G_nx.edges()))
    if any("weight" in d for _, _, d in G_nx.edges(data=True)):
        g.es["weight"] = [G_nx[u][v].get("weight", 1.0) for u, v in G_nx.edges()]
    return g

g = build_ig(G.to_undirected())
# steps=4 means: define similarity by 4-step random walks. Pons-Latapy paper
# §5: t between 3 and 5 is optimal on most graphs; the result is robust.
dendrogram = g.community_walktrap(weights="weight", steps=4)

Correct (Step 2 — cut the dendrogram at the level with the best modularity):

# `as_clustering()` cuts the dendrogram at the modularity-maximizing level
# by default — useful when you want a flat decomposition.
clustering = dendrogram.as_clustering()
communities = [[g.vs[i]["name"] for i in c] for c in clustering]
print(f"{len(communities)} communities at the Q-maximizing cut, "
      f"Q = {clustering.modularity:.4f}")

# Or pick a specific number of clusters (useful when you want to compare
# decompositions at the same granularity across systems):
clustering_k = dendrogram.as_clustering(n=8)

Correct (Step 3 — query pairwise similarity directly):

def walktrap_similarity(g, u, v, t: int = 4) -> float:
    """
    Walktrap distance between two named nodes. Useful for "what is most
    similar to this file?" queries — much cheaper than re-clustering.
    """
    # Pons-Latapy distance: r(u, v) = sum over nodes k of
    # (P^t[u][k] - P^t[v][k])² / d(k)
    # where P is the transition matrix and d(k) is degree of k.
    u_idx, v_idx = g.vs.find(name=u).index, g.vs.find(name=v).index
    # Walk distribution
    P = np.array(g.get_adjacency(attribute="weight").data, dtype=float)
    P = P / P.sum(axis=1, keepdims=True)
    Pt = np.linalg.matrix_power(P, t)
    deg = np.array(g.degree())
    diff = Pt[u_idx] - Pt[v_idx]
    return float(np.sqrt(np.sum(diff ** 2 / deg)))

# Use case: agent wants "files most-related to src/payments/charge.py"
# Compute Walktrap distance to all other nodes; rank ascending. Fast.

Why short walks capture the right notion of "community":

In t = 3–5 steps a random walker explores its local neighborhood — typically the cluster it's in. Two nodes in the same cluster reach the same set of other nodes with similar probabilities (because they share neighbors and short paths). Two nodes in different clusters have very different post-walk distributions (the walker tends to stay in its starting cluster). The L²-distance between post-walk distributions, weighted by inverse degree, becomes a natural community-distance.

When to use Walktrap vs Leiden vs Infomap:

Empirical baseline: Pons-Latapy (2005) compared Walktrap with Girvan-Newman, Newman fast-greedy, and Markov clustering on the LFR benchmark and on biological networks. Walktrap matched or beat all baselines on graphs with up to 5,000 nodes, sometimes with significantly less computation than Girvan-Newman. For software systems, Maqbool & Babri (TSE 2007) found Walktrap competitive with Bunch on Mozilla and Linux kernel, with hierarchical output being a major usability advantage over Bunch's flat output.

When NOT to use:

• Very large graphs (> 10⁵ nodes) — O(n²) memory for the distance matrix.
• Directed-flow graphs — Walktrap symmetrises the walker which loses direction information; Infomap is the right choice there.
• Graphs with weak community structure — short random walks don't have time to converge to community-specific distributions; Leiden is more robust.

Production: igraph.community_walktrap is the reference (C implementation, fast). Available in R-igraph too. Used in the original Pons-Latapy paper for analysis of biological and web graphs.

Reference: Computing Communities in Large Networks Using Random Walks (Pons & Latapy, J. Graph Algorithms Appl. 2006)

Filter Omnipresent Utilities Before Clustering

Every non-trivial codebase has files that everyone imports — logger, errors, constants, utils/string, db/connection, i18n, base classes, type-stubs. Tzerpos & Holt (ACDC, WCRE 2000) called these "omnipresent" files and showed they are the single largest source of clustering noise: they pull every cluster toward themselves, merge unrelated domains via shared imports, and inflate modularity scores while destroying semantic meaning. On a 5,000-file codebase, the top 50–100 most-imported modules typically account for 50–80% of total edges in the import graph; leave them in and your "communities" are mostly "things that use the logger."

The cure is mechanical: before running any clustering algorithm, identify omnipresent files and either remove them entirely or attach them to every cluster post-hoc. Use a fan-in threshold (e.g. files in the top 1–2% by fan-in), a percentage-of-modules threshold (imported by > N% of files), or — best — a TF-IDF-style inverse-document-frequency cutoff that lets the data choose.

Incorrect (running Louvain on the raw import graph — every cluster contains the logger):

import networkx as nx
import networkx.algorithms.community as nxc

G = nx.DiGraph()
for src, dst in iter_imports("./src"):
    G.add_edge(src, dst)

# Louvain on the raw graph. The 50 most-imported files have fan-in > 500 each
# in a 3,000-file codebase. They act as super-attractors: every community
# centres on a utility, and "real" domains (payments, search, billing) fragment.
communities = nxc.louvain_communities(G.to_undirected())

Correct (drop omnipresent files via fan-in z-score before clustering):

import math
import networkx as nx
import networkx.algorithms.community as nxc

def filter_omnipresent(G: nx.DiGraph, z_threshold: float = 2.5) -> nx.DiGraph:
    """
    Tzerpos-style omnipresent filter: drop files whose fan-in is z_threshold
    standard deviations above the mean (log-transformed, since fan-in is
    long-tailed). 2.5 σ on a log scale matches the empirical 1–2% top tail
    that ACDC reports for production codebases.
    """
    fan_in = {n: G.in_degree(n) for n in G.nodes if G.in_degree(n) > 0}
    log_fi = [math.log1p(v) for v in fan_in.values()]
    mu = sum(log_fi) / len(log_fi)
    var = sum((x - mu) ** 2 for x in log_fi) / len(log_fi)
    sigma = math.sqrt(var)
    cutoff = math.exp(mu + z_threshold * sigma) - 1

    omnipresent = {n for n, fi in fan_in.items() if fi >= cutoff}
    H = G.copy()
    H.remove_nodes_from(omnipresent)
    return H, omnipresent

G_pruned, dropped = filter_omnipresent(G)
print(f"dropped {len(dropped)} omnipresent nodes:", sorted(dropped)[:10])
communities = nxc.louvain_communities(G_pruned.to_undirected())

# Post-hoc: re-attach each omnipresent file to every cluster (it really does
# belong everywhere) or to its own "utilities" cluster — ACDC's convention.

Alternative (data-driven cutoff via IDF — no hand-picked threshold):

# Treat each importing module as a "document". Inverse Document Frequency
# discounts widely-imported files automatically — same idea as TF-IDF for words.
# Files imported by > 50% of modules end up with IDF < 1.0 and drop out
# naturally once you weight edges by IDF (see graph-weight-edges-by-information-content).

N = G.number_of_nodes()
idf = {n: math.log(N / (1 + G.in_degree(n))) for n in G.nodes}
KEEP_THRESHOLD = math.log(20)  # files imported by ≤ N/20 modules
keep = {n for n, v in idf.items() if v >= KEEP_THRESHOLD}
H = G.subgraph(keep).copy()

Why this matters more than the algorithm choice:

ACDC (Tzerpos & Holt, WCRE 2000) and Bunch (Mancoridis et al., ICSM 1999) both report that omnipresent filtering changes MoJoFM (cluster similarity to ground truth) by 20–40 points out of 100 — a larger swing than the choice between Louvain, Leiden, and Infomap on the same input. Mitchell & Mancoridis (TSE 2006) reproduce this on the SwingBunch corpus. If you do nothing else from this skill, do this.

When NOT to filter:

• You're recovering layer structure (kernel → util → app) — omnipresent files ARE the lower layers and you need them in.
• You're explicitly hunting for cross-cutting concerns (logging, auth, i18n) — those are the omnipresent files. Use FCA (Snelting-Tip, FSE 1998) instead of community detection.
• The codebase is small enough (< 200 files) that the top-1% tail is 0–2 files.

Production: ACDC ships with a configurable omnipresent threshold; SonarQube's Architecture view applies a similar fan-in cutoff before drawing dependency cycles; Sourcegraph's code-intel skips well-known stdlib modules entirely when building cross-repo graphs.

Reference: ACDC: An Algorithm for Comprehension-Driven Clustering (Tzerpos & Holt, WCRE 2000)