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 | |||||||||