commugrow — Community-Preserving Graph Expansion

Grow a small undirected, unweighted graph into a larger synthetic graph while preserving community structure in expectation. We detect communities on the base graph (Louvain/Leiden/greedy), estimate a block probability matrix (P), and sample a larger Stochastic Block Model (SBM) or degree-corrected SBM–like graph with the same mesoscale pattern.

TL;DR: give me Karate Club; give you a 10× bigger graph with the same communities (up to randomness).

Features

• Detect communities on the base graph (Louvain by default; Leiden/greedy supported).
• Estimate inter-community probabilities (P) from the base graph with Laplace smoothing.
• Sample SBM or degree-corrected SBM–like graphs at any scale factor.
• Re-detect communities on the synthetic graph and report modularity, ARI/NMI (if scikit-learn is installed).
• Spectral sanity checks (normalized Laplacian eigenvalues).
• Optional plots and a confusion matrix figure.

Install

Option A: pip (editable dev install)

git clone https://github.com/mdindoost/commugrow.git
cd commugrow
python -m venv .venv
source .venv/bin/activate  # Windows: .venv\Scripts\activate
pip install -e ".[all]"

Option B: minimal deps

pip install -e .
# If you skip extras: you still have Louvain (python-louvain). Leiden & ARI/NMI are optional.

Extras:

• pip install ".[leiden]" adds leidenalg + igraph
• pip install ".[metrics]" adds scikit-learn for ARI/NMI
• pip install ".[plots]" adds matplotlib
• pip install ".[all]" pulls everything

Usage

Run from anywhere after installation:

commugrow --scale 10 --method louvain --use-dcsbm --plots --seed 42 -v

CLI

commugrow [FLAGS...]

--scale <float>           Scale factor for number of nodes (e.g., 10.0 => ~10x). Default: 10.0
--method {louvain,leiden,greedy}
                         Community detector for base & synthetic graphs. Default: louvain
--epsilon <float>        Laplace smoothing for P estimation. Default: 0.5
--use-dcsbm              Enable degree-corrected SBM–like sampler. Default: off
--plots                  Save eigenvalue histograms and a confusion matrix (if sklearn). Default: off
--seed <int>             RNG seed. Default: 42
-v / -vv                 Verbosity. -v=INFO, -vv=DEBUG. Default: -v

Example

commugrow --scale 8 --method leiden --use-dcsbm --epsilon 0.5 --plots --seed 1 -v

The run prints base/synthetic community sizes, modularities, the block matrix (P), recovery metrics (ARI/NMI if available), and spectral snippets. Plots (if requested) are written to the current directory.

API (advanced)

Everything is driven by a single CLI entry point (commugrow). If you want to integrate into your own Python code, you can import the functions from commugrow.cli (they are kept self-contained).

Why it works (short version)

1. Detect a partition on the base graph (mesoscale structure).
2. Estimate the inter/intra-community connectivity matrix (P).
3. Scale community sizes and sample from SBM (or DCSBM-like) with (P).
4. Re-detect to verify: modularity, ARI/NMI, spectral shape should be comparable.

This preserves community structure in expectation, not an isomorphic copy. For “same degree + sparse + spectral control,” see k-lifts; for exact normalized-spectral embedding, see equitable blow-ups.

Roadmap

• Optional k-lifts per block (community-preserving lifts).
• Graphon-based sampling for dense regimes.
• Seeding with an arbitrary base graph via --input path.
• Deterministic rounding / size constraints.

Citation

If this repo helps you, please cite it (replace metadata as needed):

@misc{commugrow,
  title  = {commugrow: Community-Preserving Graph Expansion},
  author = {Mohammad Dindoost},
  year   = {2025},
  url    = {https://github.com/<you>/commugrow}
}

License

MIT — see LICENSE.