Algorithms’ Table

In the following table you can find an up-to-date list of the Community Detection algorithms made available within cdlib.

Algorithms are listed in alphabetical order along with:

  • a few additional information on the graph typologies they handle, and
  • the main expected characteristics of the clustering they produce,
  • (when available) the theoretical computational complexity as estimated by their authors.

All algorithms are assumed - apart few, reported, exceptions - to work on undirected and unweighted graphs.

Complexity notation. When discussing the time complexity the following notation is assumed:

  • n: number of nodes
  • m: number of edges
  • k: number of iterations
  • c: number of communities
  • d: average node degree
Algorithm Network Communities Complexity
Directed Weighted Bipartite Feature-Rich Temporal Crisp Overlaps Nested Fuzzy Hierarchical Time
agdl x x       x         O(n^2)
angel             x       O(n)
aslpaw             x       O(kn)
async_fluid           x         O(m)
belief           x         O(kn)
big_clam           x x x     O(n)
bimlpa     x     x         O(m)
chinesewhispers   x       x         O(km)
condor     x     x          
conga             x        
congo             x       O(nm^2)
core_expansion             x       O(nlogn)
cpm   x       x          
CPM_bipartite     x     x          
coach             x        
danmf   x         x        
dcs   x         x        
demon             x        
der   x       x          
dpclus   x         x        
edmot   x x     x x        
ebgc             x        
ego_networks             x       O(m)
egonet_splitter             x       O(m^3/2 )
eigenvector           x          
em x         x x   x    
endntm             x        
eva       x   x          
frc_fgsn     x       x   x    
ga           x          
gdmp2 x   x     x          
gemsec x         x          
girvan_newman           x       x  
graph_entropy   x         x        
greedy_modularity           x          
head_tail           x          
hierarchical_link_communities             x        
ilouvain       x   x          
infomap x x       x          
infomap_bipartite x x x     x          
ipca   x       x x        
kclique             x        
kcut           x          
label_propagation           x          
lais2             x       O(cm + n)
leiden           x          
lemon             x        
lfm             x     x O(n^2 logn)
louvain           x          
lpam             x       O(2^m)
lpanni             x       O(n)
lswl   x       x x        
lswl_plus   x       x x        
markov_clustering           x          
mcode   x       x          
mnmf             x       O(n^2*m+n^2*k)
mod_m           x         O(nd)
mod_r           x         O(nd)
node_perception             x        
multicom             x        
nnsed             x       O(kn^2)
overlapping_seed_set_expansion             x        
paris   x       x       x  
percomvc             x        
principled_clustering             x   x    
pycombo   x       x         O(n^2 logc)
rb_pots x x       x          
rber_pots   x       x          
ricci_community           x          
r_spectral_clustering           x          
sbm_dl           x          
sbm_dl_nested           x          
scan           x         O(m)
scd           x          
spectral     x     x          
significance_communities           x          
sibilarity_antichain x (DAG)         x          
slpa             x       O(kn)
spinglass           x          
surprise_communities x x       x          
symmnmf             x        
threshold_clustering x x       x          
tiles         x   x        
umstmo             x        
walkscan             x        
walktrap           x         O(n^2 logn)
wCommunity   x         x