pySurprise

Compute the Surprise metric, run community detection algorithms, explore the Surprise landscape, and benchmark everything on synthetic networks. C++ core via pybind11 for maximum performance.

pip install pysurprise

---

Quick start

import pysurprise as pys

edges = [("a", "b"), ("a", "c"), ("b", "c"),
         ("c", "d"), ("d", "e"), ("d", "f"), ("e", "f")]
partition = {"a": 0, "b": 0, "c": 0, "d": 1, "e": 1, "f": 1}

pys.surprise(edges, partition)   # → 2.854...

Integer labels and list partitions also work:

edges = [(0, 1), (0, 2), (1, 2), (2, 3), (3, 4), (3, 5), (4, 5)]
partition = [0, 0, 0, 1, 1, 1]
pys.surprise(edges, partition)

---

Module overview

Module	Purpose
pysurprise (root)	Surprise computation (C++ core)
pysurprise.algorithms	14 community detection algorithms
pysurprise.landscape	Surprise landscape exploration (merge/split curves)
pysurprise.metrics	Partition quality metrics (NMI, VI, ARI, modularity)
pysurprise.benchmarks	Synthetic graph generators (LFR, Relaxed Caveman)
pysurprise.parallel	Parallel execution with disk caching
pysurprise.plotting	Publication-ready figures

---

1. Surprise computation — pysurprise

The core functions live in the root module. The C++ backend makes them fast even on large graphs.

surprise(edges, partition, *, tol=1e-17) → float

Main entry point. Computes Surprise in −log₁₀ scale (higher = better partition).

import pysurprise as pys

S = pys.surprise(edges, partition)

• edges — list[(str, str)] or list[(int, int)]: undirected edge list.
• partition — dict[node, int] or list[int]: community assignment.
• tol — summation tolerance of the hypergeometric tail (see below).

compute_surprise(F, M, n, p, tol=1e-17) → float

Low-level four-parameter Surprise. Computes the cumulative hypergeometric probability directly from the graph statistics:

• F — total possible node pairs, N(N−1)/2.
• M — possible intra-community pairs, Σ sᵢ(sᵢ−1)/2.
• n — total number of edges.
• p — number of intra-community edges.

Surprise = −log₁₀ P(X ≥ p) with X ~ Hypergeometric(F, M, n), summed over the full tail (exact to double precision). The original SurpriseMe code stopped the summation with an inverted test and in practice kept only the first two terms; pySurprise computes the exact value everywhere (the package, the optimisers and the bundled computeSurprise / jerarca binaries), so values can differ from SurpriseMe in the last decimals for good partitions and substantially for partitions close to random.

tol (also accepted by surprise, surprise_from_partition and surprise_from_partition_dict): terms are added until an upper bound of the remaining tail is below tol times the accumulated sum, so the probability has relative error < tol and Surprise an absolute error < tol / ln 10. The default 1e-17 is exact to double precision; 0 sums every term; larger values (e.g. 1e-8) trade accuracy for speed. Must be in [0, 1).

log_hyper_probability(F, M, n, j) → float

Single hypergeometric term in log₁₀ scale. Used internally by compute_surprise.

surprise_from_partition(edges, partition) → float

C++ fast-path for integer-indexed edges and list partitions.

surprise_from_partition_dict(edges, partition) → float

C++ fast-path for string-labelled edges and dict partitions.

---

2. Community detection algorithms — pysurprise.algorithms

All functions accept list[(str, str)] edges and return dict[str, int] partitions.

Classic algorithms (SurpriseMe bundle)

Seven algorithms from the original SurpriseMe distribution, each wrapping a compiled C++ binary:

Function	Algorithm	Reference
cpm(edges)	Constant Potts Model	Traag et al., Phys Rev E 84 (2011)
infomap(edges)	Map equation	Rosvall & Bergstrom, PNAS 105 (2008)
rb(edges)	Reichardt-Bornholdt	Reichardt & Bornholdt, Phys Rev E 74 (2006)
rn(edges)	Ronhovde-Nussinov	Ronhovde & Nussinov, Phys Rev E 81 (2010)
rnsc(edges)	Restricted Neighbourhood Search	King et al., Bioinformatics 20 (2004)
scluster(edges)	SCluster (Jerarca)	Aldecoa & Marín, PLoS ONE 5 (2010)
uvcluster(edges)	UVCluster (Jerarca)	Arnau et al., Bioinformatics 21 (2005)

Optional parameters: timeout=None (seconds), and algorithm-specific settings (e.g. iterations for scluster/uvcluster, attempts for infomap).

Modularity-based

Function	Algorithm	Reference
duch_arenas(edges)	Extremal optimisation for modularity (pure Python)	Duch & Arenas, Phys Rev E 72 (2005)

Surprise optimisers

These directly maximise Surprise using different strategies:

Function	Description
surprise_refine(edges, partition)	Louvain-style greedy refinement (node relabelling + community merges). Pure post-processor — can sharpen any initial partition. Params: max_iters=100, allow_merge=True.
surprise_anneal(edges, init_partition=None)	Simulated Annealing global optimiser. Escapes local optima via Metropolis–Hastings. Params: T_start=2.0, T_end=1e-4, steps=200_000, singleton_prob=0.25, seed=None. Finishes with a surprise_refine polish.
surprise_louvain(edges)	Louvain optimiser of the exact (hypergeometric) Surprise: algorithm SP0 of Tang et al. (2019), i.e. their Louvain_process (multilevel node moves + aggregation into super nodes) from the singleton partition. n_restarts=1 (the paper's algorithm).
surprise_fagso(edges)	FAGSO (Jiang et al. 2014). Ranks edges by Jaccard similarity, greedily merges communities. O(m·log m).
surprise_sp2(edges)	SP2 (Tang et al. 2019). Pre_CS → Louvain_process → Post_CS, transcribed from the paper's pseudo-code (Functions 2–4). n_restarts=1 (the paper's algorithm).
surprise_sp4(edges)	SP4 (Tang et al. 2019). Pre_TS → Pre_CS → Louvain_process → Post_CS; Surprise is optimised on the Pre_TS-rewired network. Params: tau=3, k=None (round(mean degree)), n_restarts=1.
pre_ts(edges)	Pre_TS topology pre-processing (Tang et al. 2019): links each node to its k most similar nodes by cosine similarity of tau-step random-walk profiles.
surprise_m2(edges)	M² (Marin Squared). Hybrid: FAGSO warm-start → asymptotic KL-divergence Louvain → exact Surprise refinement. Multi-restart (n_restarts=4).

Embedding-based

These learn node embeddings and cluster them with K-Means. Require optional dependencies (pip install gensim scikit-learn networkx or pip install node2vec scikit-learn networkx or pip install torch scipy scikit-learn networkx).

Function	Algorithm	Reference
deepwalk(edges)	Random-walk + Word2Vec + K-Means	Perozzi et al., KDD 2014
node2vec(edges)	Biased random-walk + Word2Vec + K-Means	Grover & Leskovec, KDD 2016
vgae(edges)	Variational Graph Auto-Encoder (GCN-VAE) + K-Means	Kipf & Welling, NeurIPS Workshop 2016

Common params: n_clusters=None (auto-estimated), dimensions=128, walk_length=80, num_walks=10, seed=None, refine=False (apply surprise_refine after clustering).

Batch execution

from pysurprise.algorithms import run_all

results = run_all(edges)                          # all 7 classic algorithms
results = run_all(edges, algorithms=["CPM", "UVCluster"], parallel=True)

run_all(edges, *, algorithms=None, timeout=None, parallel=False, n_workers=None) → dict[str, dict[str, int]]

Runs the requested algorithms (default: all 7 classic) and returns {name: partition}. Set parallel=True for multi-process execution.

---

3. Landscape exploration — pysurprise.landscape

Tools for analysing how Surprise changes as community structure is modified through merge and split operations.

Partition operations

Function	Description
relabel(partition)	Relabel community IDs to contiguous 0..K−1.
merge_communities(partition, c1, c2)	Merge community c2 into c1, relabel.
split_community(partition, edges, community)	Bisect a community by internal degree (or random). Params: method="degree", seed=42.

surprise_landscape(edges, partition) → LandscapeResult

Evaluates Surprise for all single-step merge/split neighbours of a partition.

from pysurprise.landscape import surprise_landscape

ls = surprise_landscape(edges, partition, operations="merge_split")
print(f"Current S = {ls.surprise_current:.1f}, K = {ls.k_current}")
print(f"Best merge: ΔS = {ls.best_merge.delta_surprise:+.2f}")
print(f"Best split: ΔS = {ls.best_split.delta_surprise:+.2f}")

• operations — "merge", "split", or "merge_split" (default).
• Returns LandscapeResult with .merges (list of MergeInfo), .splits (list of SplitInfo), .best_merge, .best_split, .best_move.

surprise_curve(edges, partition) → list[CurvePoint]

Traces S vs K by greedily merging (or splitting) communities.

from pysurprise.landscape import surprise_curve

curve = surprise_curve(edges, partition, direction="both",
                       keep_partitions=True, verbose=True)
for pt in curve:
    print(f"K={pt.k}  S={pt.surprise:.1f}  {pt.operation}")

• direction — "merge" (K→1), "split" (K→N), or "both".
• keep_partitions — if True, each CurvePoint.partition stores the full partition dict at that step.
• Returns list of CurvePoint(k, surprise, operation, partition).

surprise_path(edges, partition) → list[PathStep]

Greedy walk that considers both merges and splits at each step, freely navigating the landscape (unlike surprise_curve which only goes in one direction).

from pysurprise.landscape import surprise_path

path = surprise_path(edges, partition, max_steps=50,
                     operations="merge_split", verbose=True)

• Returns list of PathStep(step, k, surprise, operation, delta_surprise, partition).

metric_landscape(edges, partition, score_fn) → GenericLandscapeResult

Generic version of surprise_landscape — accepts any scoring function.

from pysurprise.landscape import metric_landscape
from pysurprise.metrics import modularity

ls_q = metric_landscape(edges, partition, modularity, metric_name="Q")

metric_curve(edges, partition, score_fn) → list[GenericCurvePoint]

Generic version of surprise_curve — traces any metric along the greedy merge path.

from pysurprise.landscape import metric_curve
from pysurprise.metrics import modularity

curve_q = metric_curve(edges, partition, modularity, label="Q", verbose=True)

Data classes

Class	Fields
CurvePoint	k, surprise, operation, partition
PathStep	step, k, surprise, operation, delta_surprise, partition
MergeInfo	c1, c2, surprise_after, delta_surprise, size_c1, size_c2
SplitInfo	community, surprise_after, delta_surprise, size_before
LandscapeResult	surprise_current, k_current, merges, splits, best_merge, best_split, best_move
GenericCurvePoint	k, score, operation, partition
GenericMergeInfo	c1, c2, score_after, delta_score, size_c1, size_c2
GenericSplitInfo	community, score_after, delta_score, size_before
GenericLandscapeResult	score_current, k_current, metric_name, merges, splits

---

4. Metrics — pysurprise.metrics

Partition comparison and quality metrics for benchmark evaluation.

Partition comparison

Function	Description	Range
nmi(partition1, partition2)	Normalised Mutual Information	[0, 1] (1 = identical)
vi(partition1, partition2)	Variation of Information	[0, ∞) (0 = identical)
nvi(partition1, partition2)	Normalised VI = VI / log(n)	[0, 1] (0 = identical)
ari(partition1, partition2)	Adjusted Rand Index	(−0.5, 1] (1 = identical)

All accept dict[str, int] partitions.

Graph-level

Function	Description
modularity(edges, partition)	Newman modularity Q. Requires networkx.
n_communities(partition)	Number of distinct communities in a partition.

Composite / ranking

Function	Description
performance(algo_scores)	Performance P = K − avg_rank for each algorithm (single evaluation).
performance_over_reps(reps)	Mean P averaged over multiple repetitions.
nmi_best_surprise(edges, partitions, gt)	NMI of the partition that maximises Surprise (NMI_S).
nmi_best_modularity(edges, partitions, gt)	NMI of the partition that maximises modularity (NMI_Q).

---

5. Benchmarks — pysurprise.benchmarks

Synthetic graph generators with known ground-truth community structure.

LFR benchmark

Power-law degree and community-size distributions. Uses the native C++ binary from Lancichinetti et al. (exact μ, supports τ₂ = 1).

from pysurprise.benchmarks import lfr_generate, lfr_benchmark, LFR_PAPER_PRESETS

# Generate at μ = 0.3
edges, gt, sizes = lfr_generate(1000, mu=0.3, seed=42)

# Generate + closed degradation
edges, gt = lfr_benchmark(1000, mu=0.1, degradation=0.5, mode="closed", seed=42)

# Paper preset
edges, gt = lfr_benchmark(**LFR_PAPER_PRESETS["2013_scirep_N1000"], mu=0.3, seed=42)

Function	Description
lfr_benchmark(n_nodes, mu, ...)	Full pipeline: generate + optional degradation. Params: degradation=0.0, mode="open" or "closed", average_degree, max_degree, tau1, tau2, min_community, max_community, seed.
lfr_generate(n_nodes, mu, ...)	Generate only → (edges, gt, sizes).
lfr_degrade_closed(edges, gt, degradation)	Apply closed degradation to an existing graph.
set_lfr_binary(path)	Manually set the LFR binary path.
get_lfr_binary()	Get the currently configured binary path.
describe_lfr(...)	Print a human-readable description of LFR parameters.
LFR_PAPER_PRESETS	Dict of preset configurations: "2011_N1000", "2011_N5000", "2012_closed_N1000", "2013_scirep_N1000", "2013_scirep_N5000".

Relaxed Caveman benchmark

Clique-based benchmark with tunable degradation.

from pysurprise.benchmarks import rc_benchmark, rc_generate, RC_PAPER_PRESETS

# Generate + degrade at 30%
edges, gt = rc_benchmark(512, 16, degradation=0.3, mode="open")

# Two-step: generate cliques, then degrade at multiple D values
from pysurprise.benchmarks import rc_generate, rc_degrade_open
clique_edges, gt, sizes = rc_generate(512, 16, seed=42)
edges_30 = rc_degrade_open(clique_edges, degradation=0.3, seed=100)
edges_50 = rc_degrade_open(clique_edges, degradation=0.5, seed=200)

Function	Description
rc_benchmark(n_nodes, n_communities, degradation, ...)	Full pipeline. Params: pielou=None, sizes=None, mode="open" / "closed" / "removal", min_size=3, seed=None.
rc_generate(n_nodes, n_communities, ...)	Generate cliques only → (edges, gt, sizes).
rc_degrade_open(edges, degradation, ...)	Open degradation (replace intra edges with random).
rc_degrade_closed(edges, gt, degradation, ...)	Closed degradation (rewire within budget).
rc_degrade_removal(edges, degradation, ...)	Pure edge removal.
rc_degrade(...)	Alias for rc_degrade_open.
pielou_index(sizes)	Compute Pielou's evenness index for community sizes.
broken_stick_sizes(n_nodes, n_communities, seed)	Generate random community sizes via broken-stick model.
describe_rc(...)	Print human-readable RC parameter description.
RC_PAPER_PRESETS	Dict of paper presets.
RC_ASYMMETRIC_SIZES	Asymmetric community sizes from Aldecoa & Marín (2011).

---

6. Parallel execution — pysurprise.parallel

pmap(func, tasks, *, n_workers=None, cache_dir=None, desc=None, on_error="warn") → list

Parallel map with optional disk caching. Results are returned in order.

from pysurprise.parallel import pmap

def experiment(p):
    edges, gt, _ = lfr_generate(p["n"], p["mu"], seed=p["seed"])
    return evaluate(edges, gt)

tasks = [{"n": 1000, "mu": mu, "seed": 42 + r * 100}
         for mu in [0.1, 0.2, 0.3] for r in range(10)]

results = pmap(experiment, tasks, n_workers=4, cache_dir="./cache")

• func must be a top-level (module-scope) function for pickling.
• cache_dir — when set, results are cached to disk; rerunning skips completed tasks.
• on_error — "warn" (store None) or "raise".

evaluate(edges, ground_truth, ...) → dict

Standardised benchmark evaluation: run algorithms + compute metrics.

from pysurprise.parallel import evaluate

result = evaluate(edges, gt, algorithms=["CPM", "UVCluster"],
                  metrics=("nmi", "surprise", "modularity"))
# result["algorithms"]["UVCluster"]["nmi"] → 0.95
# result["best_surprise_nmi"] → 0.97

• algorithms — subset of algorithm names (default: all 7 classic).
• metrics — tuple of "nmi", "surprise", "modularity".
• parallel / n_workers — run algorithms in parallel.

---

7. Plotting — pysurprise.plotting

Publication-ready figures. All functions return (Figure, Axes) and accept an optional ax parameter for embedding in existing figures.

Core plots

Function	Description
plot_sweep(param_values, series, ...)	Line plot: metric vs parameter (μ, D) with multiple series.
plot_ratio(param_values, ratios, ...)	NMI_Q / NMI_S ratio vs parameter.
plot_performance(param_labels, algo_performance, ...)	Grouped bar chart of Performance P = K − avg_rank.
plot_heatmap(param_labels, algo_values, ...)	Algorithm × parameter heatmap (NMI, S, etc.).
plot_community_sizes(partition, ...)	Community size distribution (bar or histogram).

Paper figure composites

Function	Description
plot_figure1(lfr_nmi_s, lfr_ratios, rc_nmi_s, rc_ratios, ...)	Complete 4-panel Figure 1 (Aldecoa & Marín 2011): NMI_S and ratio for LFR and RC.
plot_figure2(lfr_performance, rc_performance, algo_names, ...)	Two-panel Figure 2: Performance ranking bars for LFR and RC.

Landscape plots

Function	Description
plot_surprise_curve(curve, ...)	S vs K from surprise_curve(). Highlights max and optional true K.
plot_merge_heatmap(landscape, ...)	ΔS heatmap for all pairwise merges from surprise_landscape().
plot_surprise_path(path, ...)	Greedy walk trajectory from surprise_path(). Optional ΔS twin axis.

Dual metric comparison

Function	Description
plot_dual_merge_heatmap(landscape_a, landscape_b, ...)	Side-by-side merge heatmaps for two metrics (e.g. ΔS vs ΔQ).
plot_dual_landscape(curve_a, curve_b, ...)	Two metric curves on dual y-axes (e.g. Surprise + Modularity vs K).

Aggregation helper

Function	Description
aggregate_sweep(results, keys, ...)	Convert raw pmap results into plot-ready dicts for plot_figure1 / plot_figure2.

Style constants

• ALGO_COLORS_2011 — algorithm colour palette matching Aldecoa & Marín (2011).
• CONFIG_STYLES — {config_name: {color, marker}} for LFR configs.
• DEFAULT_COLORS — colourblind-friendly 8-colour cycle.

---

Credits

Developed by José Marín, based on the original SurpriseMe software by Rodrigo Aldecoa and Ignacio Marín. The bundled C++ binaries (Surprise computation, Jerarca, CPM, RB, RNSC, RN, Infomap) originate from SurpriseMe. The LFR benchmark binary is from Lancichinetti et al.

References

Aldecoa R, Marín I (2014). SurpriseMe: an integrated tool for network community structure characterization using Surprise maximization. Bioinformatics 30(7): 1041–1042.

Aldecoa R, Marín I (2011). Deciphering network community structure by Surprise. PLoS ONE 6(9): e24195.

Aldecoa R, Marín I (2013). Surprise maximization reveals the community structure of complex networks. Scientific Reports 3: 1060.

Aldecoa R, Marín I (2012). Closed benchmarks for network community structure characterization. Physical Review E 85: 026109.

Lancichinetti A, Fortunato S, Radicchi F (2008). Benchmark graphs for testing community detection algorithms. Physical Review E 78: 046110.

Jiang J Z, et al. (2014). A fast algorithm for community detection in networks by greedy surprise optimization. (FAGSO)

Tang Y-N, Xiang J, et al. (2019). An effective algorithm for optimizing Surprise in network community detection. IEEE Access 7: 148814–148827. (SP2, SP4)

Perozzi B, Al-Rfou R, Skiena S (2014). DeepWalk: Online Learning of Social Representations. KDD 2014.

Grover A, Leskovec J (2016). node2vec: Scalable Feature Learning for Networks. KDD 2016.

Kipf T, Welling M (2016). Variational Graph Auto-Encoders. NeurIPS Workshop on Bayesian Deep Learning.

License

GPL-3.0-or-later