Algorithms Reference Table

This page provides a compact overview of the algorithms exposed by CDlib. Complexity values are intentionally high-level summaries, since many methods are heuristic, output-dependent, or have implementation-specific performance characteristics.

The table is organized by category and links each algorithm to its API reference page. If an algorithm appears in more than one category in the API, the table uses the most natural placement and notes shared entries where needed.

Crisp Communities

Name	Network type	Complexity	Category	Reference	Docs
agdl	Undirected / directed, weighted	Super-linear, iterative	Crisp	AGDL (2012)	API
async_fluid	Undirected, unweighted	Near-linear per iteration	Crisp	Fluid Communities (2018)	API
label_propagation	Undirected, unweighted	Near-linear per iteration	Crisp	Alias of label_propagation_raghavan	API
bayan	Undirected, weighted	Exponential worst-case, exact/heuristic	Crisp	Bayan (2022)	API
belief	Undirected, unweighted	Iterative, near-linear per pass	Crisp	Scalable detection by message passing (2014)	API
cpm	Undirected, unweighted	Clique-search / exponential worst-case	Crisp	CPM (2011)	API
der	Undirected, weighted	Spectral / super-linear	Crisp	Community Detection via Measure Space Embedding (2015)	API
eigenvector	Undirected, weighted	Spectral, iterative	Crisp	Eigenvector modularity method (2006)	API
em	Undirected, weighted	Iterative, parameter-dependent	Crisp	Mixture community / EM analysis (2007)	API
ga	Undirected, unweighted	Heuristic, population-based	Crisp	GA-Net (2008)	API
gdmp2	Undirected, weighted	Near-linear / iterative	Crisp	Dense subgraph extraction (2012)	API
girvan_newman	Undirected, weighted	Cubic / repeated edge-betweenness	Crisp	Girvan-Newman (2002)	API
greedy_modularity	Undirected, weighted	Roughly O(m log^2 n)	Crisp	Clauset-Newman-Moore (2004)	API
head_tail	Undirected, weighted	Local / output-dependent	Crisp	Head/Tail communities (2010)	API
infomap	Directed / undirected, weighted	Near-linear / iterative	Crisp	Infomap (2008)	API
kcut	Undirected, weighted	Heuristic / output-dependent	Crisp	K-cut family (CDlib implementation)	API
label_propagation	Undirected, unweighted	Near-linear per iteration	Crisp	Raghavan et al. (2007)	API
label_propagation_raghavan	Undirected, unweighted	Near-linear per iteration	Crisp	Raghavan et al. (2007); alias: label_propagation	API
label_propagation_cordasco_gargano	Undirected, unweighted	Near-linear per iteration	Crisp	Cordasco & Gargano label propagation	API
leiden	Directed / undirected, weighted	Near-linear average	Crisp	Leiden (2018)	API
louvain	Directed / undirected, weighted	Near-linear average	Crisp	Louvain (2008)	API
lswl	Undirected, unweighted	Local / output-dependent	Crisp	LSWL (2008)	API
lswl_plus	Undirected, unweighted	Local / output-dependent	Crisp	LSWL+ (2010)	API
markov_clustering	Undirected, weighted	Super-linear, iterative	Crisp	MCL (2002)	API
mcode	Undirected, weighted	Near-linear / sparse	Crisp	MCODE (2003)	API
mod_m	Undirected, weighted	Local / output-dependent	Crisp	Exploring local community structures (2008)	API
mod_r	Undirected, weighted	Local / output-dependent	Crisp	Finding local community structure (2005)	API
paris	Undirected, weighted	Hierarchical / super-linear	Crisp	Paris (2017)	API
pycombo	Undirected, weighted	Heuristic / super-linear	Crisp	COMBO / PyCombo family	API
rber_pots	Directed / undirected, weighted	Iterative, super-linear	Crisp	Reichardt-Bornholdt (2006)	API
rb_pots	Directed / undirected, weighted	Iterative, super-linear	Crisp	Reichardt-Bornholdt / directed modularity (2006, 2008)	API
ricci_community	Undirected, weighted	Expensive / transport-based	Crisp	Ollivier-Ricci community detection	API
r_spectral_clustering	Undirected, weighted	Spectral / cubic worst-case	Crisp	R spectral clustering	API
scan	Undirected, unweighted	Near-linear	Crisp	SCAN (2007)	API
significance_communities	Undirected, weighted	Super-linear, optimization-based	Crisp	Significant scales in community structure (2013)	API
spinglass	Undirected, weighted	Heuristic / exponential worst-case	Crisp	Statistical mechanics of community detection (2006)	API
spectral	Bipartite / undirected, weighted	Spectral / cubic worst-case	Crisp	Spectral clustering family	API
surprise_communities	Undirected, weighted	Super-linear, optimization-based	Crisp	Asymptotical surprise (2015)	API
threshold_clustering	Directed, unweighted	Near-linear	Crisp	Threshold clustering	API
walktrap	Undirected, weighted	Super-linear, iterative	Crisp	Random walks community detection (2006)	API
sbm_dl	Directed / undirected, weighted	MCMC / greedy, super-linear	Crisp	Bayesian SBM inference (2014)	API
sbm_dl_nested	Directed / undirected, weighted	MCMC / greedy, super-linear	Crisp	Hierarchical SBM inference (2014)	API

Overlapping Communities

Name	Network type	Complexity	Category	Reference	Docs
aslpaw	Undirected, weighted	Iterative, near-linear per pass	Overlapping	ASLPAw (2014)	API
angel	Undirected, unweighted	Local / output-dependent	Overlapping	ANGEL (2019)	API
coach	Undirected, weighted	Local / output-dependent	Overlapping	COACH	API
conga	Undirected, weighted	Super-linear, betweenness-based	Overlapping	CONGA (2007)	API
congo	Undirected, weighted	Super-linear, hierarchical	Overlapping	CONGO (2008)	API
core_expansion	Undirected, weighted	Local / output-dependent	Overlapping	Core expansion (2020)	API
dcs	Undirected, weighted	Local / output-dependent	Overlapping	Divide and Conquer Strategy	API
demon	Undirected, weighted	Near-linear on ego networks	Overlapping	DEMON (2012)	API
dpclus	Undirected, weighted	Local / output-dependent	Overlapping	DPCLUS	API
ebgc	Undirected, weighted	Near-linear / iterative	Overlapping	EBGC	API
ego_networks	Undirected, unweighted	O(sum of ego neighborhoods)	Overlapping	Ego networks	API
endntm	Undirected, weighted	Iterative / output-dependent	Overlapping	EnDNTM	API
kclique	Undirected, unweighted	Exponential in clique size	Overlapping	Clique percolation (2005)	API
graph_entropy	Undirected, weighted	Super-linear	Overlapping	Graph entropy clustering	API
ipca	Undirected, weighted	Spectral / super-linear	Overlapping	IPCA	API
lais2	Undirected, weighted	Local / output-dependent	Overlapping	Efficient identification of overlapping communities (2005)	API
lemon	Undirected, weighted	Local spectral / output-dependent	Overlapping	LEMON (2015)	API
l1_ppr	Undirected, weighted	Local push, roughly O(1/epsilon) localized work	Overlapping	Local Partitioning for Graphs (2006)	API
lpam	Undirected, weighted	Heuristic / super-linear	Overlapping	Link Partitioning Around Medoids (2021)	API
lpanni	Undirected, weighted	Iterative, near-linear per pass	Overlapping	LPANNI (2018)	API
lfm	Undirected, weighted	Local / output-dependent	Overlapping	LFM (2009)	API
multicom	Undirected, weighted	Local / output-dependent	Overlapping	Multicom (2018)	API
node_perception	Undirected, weighted	Super-linear	Overlapping	Node Perception (2015)	API
overlapping_seed_set_expansion	Undirected, weighted	Local / output-dependent	Overlapping	Seed Set Expansion (2013)	API
ppr_sweep	Undirected, weighted	Near-linear / linear-system solve	Overlapping	PageRank-nibble (2006)	API
hk_sweep	Undirected, weighted	O(K * m)	Overlapping	Heat kernel sweep (2009)	API
clauset	Undirected, weighted	Local / output-dependent	Overlapping	Clauset local modularity (2005)	API
umstmo	Undirected, weighted	O(m log n)	Overlapping	Union of maximum spanning trees	API
percomvc	Undirected, weighted	Heuristic / output-dependent	Overlapping	PercoMCV (2019)	API
slpa	Undirected, weighted	O(T * m)	Overlapping	SLPA (2011)	API
walkscan	Undirected, weighted	Local / output-dependent	Overlapping	WalkSCAN	API
wCommunity	Undirected, weighted	Local / output-dependent	Overlapping	Weighted community detection (2010)	API

Fuzzy Communities

Name	Network type	Complexity	Category	Reference	Docs
frc_fgsn	Undirected, weighted	Heuristic / super-linear	Fuzzy	FRC-FGSN (2015)	API
principled_clustering	Undirected, weighted	Heuristic / super-linear	Fuzzy	Principled clustering	API

Attributed Communities

Name	Network type	Complexity	Category	Reference	Docs
eva	Attributed, undirected	Heuristic / super-linear	Attribute-aware	EVA (2020)	API
ilouvain	Attributed, undirected	Heuristic / super-linear	Attribute-aware	iLouvain (2015)	API

Bipartite Graph Communities

Name	Network type	Complexity	Category	Reference	Docs
bimlpa	Bipartite, weighted	Iterative, near-linear per pass	Bipartite	BiMLPA (2020)	API
condor	Bipartite, weighted	Iterative / output-dependent	Bipartite	CONDOR	API
CPM_Bipartite	Bipartite, weighted	Clique-search / exponential worst-case	Bipartite	Barber (2007)	API
infomap_bipartite	Bipartite, weighted	Near-linear / iterative	Bipartite	Bipartite Infomap	API
spectral	Bipartite, weighted	Spectral / cubic worst-case	Bipartite	Spectral bipartite clustering	API

Antichain Communities

Name	Network type	Complexity	Category	Reference	Docs
siblinarity_antichain	DAG, directed	Iterative / output-dependent	Antichain	Siblinarity antichain (2020)	API

Edge Clustering

Name	Network type	Complexity	Category	Reference	Docs
hierarchical_link_community	Undirected, weighted	Super-linear, hierarchical	Edge	Link communities reveal multiscale complexity (2010)	API
hierarchical_link_community_w	Undirected, weighted	Super-linear, hierarchical	Edge	Weighted link communities	API
hierarchical_link_community_full	Undirected, weighted	Super-linear, hierarchical	Edge	Full link community hierarchy	API

Dynamic Community Discovery

Name	Network type	Complexity	Category	Reference	Docs
tiles	Temporal / dynamic, weighted	Iterative, O(T * m)	Dynamic, temporal trade-off	Tiles (2017)	API

Note

Some public API names share the same generated reference page, for example label_propagation and the bipartite spectral entry.