pysurprise 1.2.0

Python bindings for the Surprise network community structure metric

pySurprise

Compute the Surprise metric and run community detection algorithms on complex networks. C++ core via pybind11 for maximum performance.

Installation

pip install pysurprise                # core + algorithms
pip install pysurprise[algorithms]    # optional: igraph for RN

Quick start

import pysurprise

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}

pysurprise.surprise(edges, partition)   # → 3.21...

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]
pysurprise.surprise(edges, partition)

Algorithms

Eight community detection algorithms, all returning dict[str, int]:

from pysurprise import algorithms

partition = algorithms.cpm(edges)
results  = algorithms.run_all(edges)   # run all 8 and compare

Algorithm	Function	Reference
CPM	cpm()	Traag et al., Phys Rev E 84 (2011)
Infomap	infomap()	Rosvall & Bergstrom, PNAS 105 (2008)
RB	rb()	Reichardt & Bornholdt, Phys Rev E 74 (2006)
RN	rn()	Ronhovde & Nussinov, Phys Rev E 81 (2010)
RNSC	rnsc()	King et al., Bioinformatics 20 (2004)
SCluster	scluster()	Aldecoa & Marín, PLoS ONE 5 (2010)
UVCluster	uvcluster()	Arnau et al., Bioinformatics 21 (2005)
Duch-Arenas	duch_arenas()	Duch & Arenas, Phys Rev E 72 (2005)

Benchmarks

Generate synthetic networks with known ground-truth communities:

from pysurprise.benchmarks import lfr_generate, rc_benchmark

# LFR benchmark (power-law degree & community sizes)
edges, gt, sizes = lfr_generate(1000, mu=0.3, seed=42)

# Relaxed Caveman benchmark (open / closed / removal degradation)
edges, gt = rc_benchmark(512, 16, degradation=0.3, mode="open")

Both support paper presets from Aldecoa & Marín (2011, 2012, 2013).

API summary

Function	Description
surprise(edges, partition)	Compute Surprise (accepts int or str labels)
compute_surprise(F, M, n, p)	Low-level: four-parameter Surprise
log_hyper_probability(F, M, n, j)	Single hypergeometric term (log₁₀)
algorithms.run_all(edges)	Run all algorithms and return results
benchmarks.lfr_generate(n, mu, ...)	LFR benchmark generation
benchmarks.rc_benchmark(n, k, D, ...)	RC benchmark generation

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.

License

GPL-3.0-or-later