Algorithms’ Table

The following table shows 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 estimated by their authors.

Apart from a few reported exceptions, all algorithms are assumed 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