============================== 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 ^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. list-table:: :header-rows: 1 :widths: 16 20 16 12 20 16 * - Name - Network type - Complexity - Category - Reference - Docs * - agdl - Undirected / directed, weighted - Super-linear, iterative - Crisp - AGDL (2012) - :doc:`API ` * - async_fluid - Undirected, unweighted - Near-linear per iteration - Crisp - Fluid Communities (2018) - :doc:`API ` * - label_propagation - Undirected, unweighted - Near-linear per iteration - Crisp - Alias of label_propagation_raghavan - :doc:`API ` * - bayan - Undirected, weighted - Exponential worst-case, exact/heuristic - Crisp - Bayan (2022) - :doc:`API ` * - belief - Undirected, unweighted - Iterative, near-linear per pass - Crisp - Scalable detection by message passing (2014) - :doc:`API ` * - cpm - Undirected, unweighted - Clique-search / exponential worst-case - Crisp - CPM (2011) - :doc:`API ` * - der - Undirected, weighted - Spectral / super-linear - Crisp - Community Detection via Measure Space Embedding (2015) - :doc:`API ` * - eigenvector - Undirected, weighted - Spectral, iterative - Crisp - Eigenvector modularity method (2006) - :doc:`API ` * - em - Undirected, weighted - Iterative, parameter-dependent - Crisp - Mixture community / EM analysis (2007) - :doc:`API ` * - ga - Undirected, unweighted - Heuristic, population-based - Crisp - GA-Net (2008) - :doc:`API ` * - gdmp2 - Undirected, weighted - Near-linear / iterative - Crisp - Dense subgraph extraction (2012) - :doc:`API ` * - girvan_newman - Undirected, weighted - Cubic / repeated edge-betweenness - Crisp - Girvan-Newman (2002) - :doc:`API ` * - greedy_modularity - Undirected, weighted - Roughly O(m log^2 n) - Crisp - Clauset-Newman-Moore (2004) - :doc:`API ` * - head_tail - Undirected, weighted - Local / output-dependent - Crisp - Head/Tail communities (2010) - :doc:`API ` * - infomap - Directed / undirected, weighted - Near-linear / iterative - Crisp - Infomap (2008) - :doc:`API ` * - kcut - Undirected, weighted - Heuristic / output-dependent - Crisp - K-cut family (CDlib implementation) - :doc:`API ` * - label_propagation - Undirected, unweighted - Near-linear per iteration - Crisp - Raghavan et al. (2007) - :doc:`API ` * - label_propagation_raghavan - Undirected, unweighted - Near-linear per iteration - Crisp - Raghavan et al. (2007); alias: label_propagation - :doc:`API ` * - label_propagation_cordasco_gargano - Undirected, unweighted - Near-linear per iteration - Crisp - Cordasco & Gargano label propagation - :doc:`API ` * - leiden - Directed / undirected, weighted - Near-linear average - Crisp - Leiden (2018) - :doc:`API ` * - louvain - Directed / undirected, weighted - Near-linear average - Crisp - Louvain (2008) - :doc:`API ` * - lswl - Undirected, unweighted - Local / output-dependent - Crisp - LSWL (2008) - :doc:`API ` * - lswl_plus - Undirected, unweighted - Local / output-dependent - Crisp - LSWL+ (2010) - :doc:`API ` * - markov_clustering - Undirected, weighted - Super-linear, iterative - Crisp - MCL (2002) - :doc:`API ` * - mcode - Undirected, weighted - Near-linear / sparse - Crisp - MCODE (2003) - :doc:`API ` * - mod_m - Undirected, weighted - Local / output-dependent - Crisp - Exploring local community structures (2008) - :doc:`API ` * - mod_r - Undirected, weighted - Local / output-dependent - Crisp - Finding local community structure (2005) - :doc:`API ` * - paris - Undirected, weighted - Hierarchical / super-linear - Crisp - Paris (2017) - :doc:`API ` * - pycombo - Undirected, weighted - Heuristic / super-linear - Crisp - COMBO / PyCombo family - :doc:`API ` * - rber_pots - Directed / undirected, weighted - Iterative, super-linear - Crisp - Reichardt-Bornholdt (2006) - :doc:`API ` * - rb_pots - Directed / undirected, weighted - Iterative, super-linear - Crisp - Reichardt-Bornholdt / directed modularity (2006, 2008) - :doc:`API ` * - ricci_community - Undirected, weighted - Expensive / transport-based - Crisp - Ollivier-Ricci community detection - :doc:`API ` * - r_spectral_clustering - Undirected, weighted - Spectral / cubic worst-case - Crisp - R spectral clustering - :doc:`API ` * - scan - Undirected, unweighted - Near-linear - Crisp - SCAN (2007) - :doc:`API ` * - significance_communities - Undirected, weighted - Super-linear, optimization-based - Crisp - Significant scales in community structure (2013) - :doc:`API ` * - spinglass - Undirected, weighted - Heuristic / exponential worst-case - Crisp - Statistical mechanics of community detection (2006) - :doc:`API ` * - spectral - Bipartite / undirected, weighted - Spectral / cubic worst-case - Crisp - Spectral clustering family - :doc:`API ` * - surprise_communities - Undirected, weighted - Super-linear, optimization-based - Crisp - Asymptotical surprise (2015) - :doc:`API ` * - threshold_clustering - Directed, unweighted - Near-linear - Crisp - Threshold clustering - :doc:`API ` * - walktrap - Undirected, weighted - Super-linear, iterative - Crisp - Random walks community detection (2006) - :doc:`API ` * - sbm_dl - Directed / undirected, weighted - MCMC / greedy, super-linear - Crisp - Bayesian SBM inference (2014) - :doc:`API ` * - sbm_dl_nested - Directed / undirected, weighted - MCMC / greedy, super-linear - Crisp - Hierarchical SBM inference (2014) - :doc:`API ` ^^^^^^^^^^^^^^^^^^^^^^^ Overlapping Communities ^^^^^^^^^^^^^^^^^^^^^^^ .. list-table:: :header-rows: 1 :widths: 16 20 16 12 20 16 * - Name - Network type - Complexity - Category - Reference - Docs * - aslpaw - Undirected, weighted - Iterative, near-linear per pass - Overlapping - ASLPAw (2014) - :doc:`API ` * - angel - Undirected, unweighted - Local / output-dependent - Overlapping - ANGEL (2019) - :doc:`API ` * - coach - Undirected, weighted - Local / output-dependent - Overlapping - COACH - :doc:`API ` * - conga - Undirected, weighted - Super-linear, betweenness-based - Overlapping - CONGA (2007) - :doc:`API ` * - congo - Undirected, weighted - Super-linear, hierarchical - Overlapping - CONGO (2008) - :doc:`API ` * - core_expansion - Undirected, weighted - Local / output-dependent - Overlapping - Core expansion (2020) - :doc:`API ` * - dcs - Undirected, weighted - Local / output-dependent - Overlapping - Divide and Conquer Strategy - :doc:`API ` * - demon - Undirected, weighted - Near-linear on ego networks - Overlapping - DEMON (2012) - :doc:`API ` * - dpclus - Undirected, weighted - Local / output-dependent - Overlapping - DPCLUS - :doc:`API ` * - ebgc - Undirected, weighted - Near-linear / iterative - Overlapping - EBGC - :doc:`API ` * - ego_networks - Undirected, unweighted - O(sum of ego neighborhoods) - Overlapping - Ego networks - :doc:`API ` * - endntm - Undirected, weighted - Iterative / output-dependent - Overlapping - EnDNTM - :doc:`API ` * - kclique - Undirected, unweighted - Exponential in clique size - Overlapping - Clique percolation (2005) - :doc:`API ` * - graph_entropy - Undirected, weighted - Super-linear - Overlapping - Graph entropy clustering - :doc:`API ` * - ipca - Undirected, weighted - Spectral / super-linear - Overlapping - IPCA - :doc:`API ` * - lais2 - Undirected, weighted - Local / output-dependent - Overlapping - Efficient identification of overlapping communities (2005) - :doc:`API ` * - lemon - Undirected, weighted - Local spectral / output-dependent - Overlapping - LEMON (2015) - :doc:`API ` * - l1_ppr - Undirected, weighted - Local push, roughly O(1/epsilon) localized work - Overlapping - Local Partitioning for Graphs (2006) - :doc:`API ` * - lpam - Undirected, weighted - Heuristic / super-linear - Overlapping - Link Partitioning Around Medoids (2021) - :doc:`API ` * - lpanni - Undirected, weighted - Iterative, near-linear per pass - Overlapping - LPANNI (2018) - :doc:`API ` * - lfm - Undirected, weighted - Local / output-dependent - Overlapping - LFM (2009) - :doc:`API ` * - multicom - Undirected, weighted - Local / output-dependent - Overlapping - Multicom (2018) - :doc:`API ` * - node_perception - Undirected, weighted - Super-linear - Overlapping - Node Perception (2015) - :doc:`API ` * - overlapping_seed_set_expansion - Undirected, weighted - Local / output-dependent - Overlapping - Seed Set Expansion (2013) - :doc:`API ` * - ppr_sweep - Undirected, weighted - Near-linear / linear-system solve - Overlapping - PageRank-nibble (2006) - :doc:`API ` * - hk_sweep - Undirected, weighted - O(K * m) - Overlapping - Heat kernel sweep (2009) - :doc:`API ` * - clauset - Undirected, weighted - Local / output-dependent - Overlapping - Clauset local modularity (2005) - :doc:`API ` * - umstmo - Undirected, weighted - O(m log n) - Overlapping - Union of maximum spanning trees - :doc:`API ` * - percomvc - Undirected, weighted - Heuristic / output-dependent - Overlapping - PercoMCV (2019) - :doc:`API ` * - slpa - Undirected, weighted - O(T * m) - Overlapping - SLPA (2011) - :doc:`API ` * - walkscan - Undirected, weighted - Local / output-dependent - Overlapping - WalkSCAN - :doc:`API ` * - wCommunity - Undirected, weighted - Local / output-dependent - Overlapping - Weighted community detection (2010) - :doc:`API ` ^^^^^^^^^^^^^^^^^ Fuzzy Communities ^^^^^^^^^^^^^^^^^ .. list-table:: :header-rows: 1 :widths: 16 20 16 12 20 16 * - Name - Network type - Complexity - Category - Reference - Docs * - frc_fgsn - Undirected, weighted - Heuristic / super-linear - Fuzzy - FRC-FGSN (2015) - :doc:`API ` * - principled_clustering - Undirected, weighted - Heuristic / super-linear - Fuzzy - Principled clustering - :doc:`API ` ^^^^^^^^^^^^^^^^^^^^^^ Attributed Communities ^^^^^^^^^^^^^^^^^^^^^^ .. list-table:: :header-rows: 1 :widths: 16 20 16 12 20 16 * - Name - Network type - Complexity - Category - Reference - Docs * - eva - Attributed, undirected - Heuristic / super-linear - Attribute-aware - EVA (2020) - :doc:`API ` * - ilouvain - Attributed, undirected - Heuristic / super-linear - Attribute-aware - iLouvain (2015) - :doc:`API ` ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Bipartite Graph Communities ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. list-table:: :header-rows: 1 :widths: 16 20 16 12 20 16 * - Name - Network type - Complexity - Category - Reference - Docs * - bimlpa - Bipartite, weighted - Iterative, near-linear per pass - Bipartite - BiMLPA (2020) - :doc:`API ` * - condor - Bipartite, weighted - Iterative / output-dependent - Bipartite - CONDOR - :doc:`API ` * - CPM_Bipartite - Bipartite, weighted - Clique-search / exponential worst-case - Bipartite - Barber (2007) - :doc:`API ` * - infomap_bipartite - Bipartite, weighted - Near-linear / iterative - Bipartite - Bipartite Infomap - :doc:`API ` * - spectral - Bipartite, weighted - Spectral / cubic worst-case - Bipartite - Spectral bipartite clustering - :doc:`API ` ^^^^^^^^^^^^^^^^^^^^^^^ Antichain Communities ^^^^^^^^^^^^^^^^^^^^^^^ .. list-table:: :header-rows: 1 :widths: 16 20 16 12 20 16 * - Name - Network type - Complexity - Category - Reference - Docs * - siblinarity_antichain - DAG, directed - Iterative / output-dependent - Antichain - Siblinarity antichain (2020) - :doc:`API ` ^^^^^^^^^^^^^^^^^^^ Edge Clustering ^^^^^^^^^^^^^^^^^^^ .. list-table:: :header-rows: 1 :widths: 16 20 16 12 20 16 * - Name - Network type - Complexity - Category - Reference - Docs * - hierarchical_link_community - Undirected, weighted - Super-linear, hierarchical - Edge - Link communities reveal multiscale complexity (2010) - :doc:`API ` * - hierarchical_link_community_w - Undirected, weighted - Super-linear, hierarchical - Edge - Weighted link communities - :doc:`API ` * - hierarchical_link_community_full - Undirected, weighted - Super-linear, hierarchical - Edge - Full link community hierarchy - :doc:`API ` ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Dynamic Community Discovery ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. list-table:: :header-rows: 1 :widths: 16 20 16 12 20 16 * - Name - Network type - Complexity - Category - Reference - Docs * - tiles - Temporal / dynamic, weighted - Iterative, O(T * m) - Dynamic, temporal trade-off - Tiles (2017) - :doc:`API ` .. note:: Some public API names share the same generated reference page, for example ``label_propagation`` and the bipartite ``spectral`` entry.