Static Community Discovery

Node Clustering

Algorithms falling in this category generate communities composed by nodes. The communities can represent neat, crisp, partition as well as overlapping or even fuzzy ones.

Note

The following lists are aligned to CD methods available in the GitHub main branch of CDlib. In particular, the following algorithms are not yet released in the packaged version of the library: coach, mcode, ipca, dpclus, graph_entropy, ebgc, r_spectral_clustering.

Crisp Communities

A clustering is said to be a partition if each node belongs to one and only one community. Methods in this subclass return as result a NodeClustering object instance.

agdl(g_original, number_communities, kc)	AGDL is a graph-based agglomerative algorithm, for clustering high-dimensional data.
async_fluid(g_original, k)	Fluid Communities (FluidC) is based on the simple idea of fluids (i.e., communities) interacting in an environment (i.e., a non-complete graph), expanding and contracting.
bayan(g_original, threshold, time_allowed, …)	The Bayan algorithm is community detection method that is capable of providing a globally optimal solution to the modularity maximization problem.
belief(g_original, max_it, eps, …)	Belief community seeks the consensus of many high-modularity partitions.
cpm(g_original, initial_membership, weights, …)	CPM is a model where the quality function to optimize is:
der(g_original, walk_len, threshold, iter_bound)	DER is a Diffusion Entropy Reducer graph clustering algorithm.
eigenvector(g_original)	Newman’s leading eigenvector method for detecting community structure based on modularity.
em(g_original, k)	EM is based on based on a mixture model.
ga(g_original, population, generation, r)	Genetic based approach to discover communities in social networks.
gdmp2(g_original, min_threshold)	Gdmp2 is a method for identifying a set of dense subgraphs of a given sparse graph.
girvan_newman(g_original, level)	The Girvan–Newman algorithm detects communities by progressively removing edges from the original graph.
greedy_modularity(g_original, weight)	The CNM algorithm uses the modularity to find the communities strcutures.
head_tail(g_original, head_tail_ratio)	Identifying homogeneous communities in complex networks by applying head/tail breaks on edge betweenness given its heavy-tailed distribution.
infomap(g_original, flags)	Infomap is based on ideas of information theory.
kcut(g_original, kmax)	An Efficient Spectral Algorithm for Network Community Discovery.
label_propagation(g_original)	The Label Propagation algorithm (LPA) detects communities using network structure alone.
leiden(g_original, initial_membership, weights)	The Leiden algorithm is an improvement of the Louvain algorithm.
louvain(g_original, weight, resolution, …)	Louvain maximizes a modularity score for each community.
lswl(g_original, query_node, strength_type, …)	LSWL locally discovers networks’ the communities precisely, deterministically, and quickly.
lswl_plus(g_original, strength_type, …)	LSWL+ is capable of finding a partition with overlapping communities or without them, based on user preferences.
markov_clustering(g_original, expansion, …)	The Markov clustering algorithm (MCL) is based on simulation of (stochastic) flow in graphs.
mcode(g_original, weights, weight_threshold)	MCODE is the earliest seed-growth method for predicting protein complexes from PPI networks.
mod_m(g_original, query_node)	Community Discovery algorithm designed to find local optimal community structures in large networks starting from a given source vertex.
mod_r(g_original, query_node)	Community Discovery algorithm that infers the hierarchy of communities that enclose a given vertex by exploring the graph one vertex at a time.
paris(g_original)	Paris is a hierarchical graph clustering algorithm inspired by modularity-based clustering techniques.
pycombo(g_original, weight, max_communities, …)	This is an implementation (for Modularity maximization) of the community detection algorithm called “Combo”.
rber_pots(g_original, initial_membership, …)	rber_pots is a model where the quality function to optimize is:
rb_pots(g_original, initial_membership, …)	Rb_pots is a model where the quality function to optimize is:
ricci_community(g_original, alpha, method)	Curvature is a geometric property to describe the local shape of an object.
r_spectral_clustering(g_original, …)	Spectral clustering partitions the nodes of a graph into groups based upon the eigenvectors of the graph Laplacian.
scan(g_original, epsilon, mu)	SCAN (Structural Clustering Algorithm for Networks) is an algorithm which detects clusters, hubs and outliers in networks.
significance_communities(g_original, …)	Significance_communities is a model where the quality function to optimize is:
spinglass(g_original, spins)	Spinglass relies on an analogy between a very popular statistical mechanic model called Potts spin glass, and the community structure.
surprise_communities(g_original, …)	Surprise_communities is a model where the quality function to optimize is:
walktrap(g_original)	walktrap is an approach based on random walks.
sbm_dl(g_original)	Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models.
sbm_dl_nested(g_original)	Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models.
spectral(g_original, kmax, …)	SCD implements a Spectral Clustering algorithm for Communities Discovery.
threshold_clustering(g_original, …)	Developed for semantic similarity networks, this algorithm specifically targets weighted and directed graphs.

Overlapping Communities

A clustering is said to be overlapping if any generic node can be assigned to more than one community. Methods in this subclass return as result a NodeClustering object instance.

aslpaw(g_original)	ASLPAw can be used for disjoint and overlapping community detection and works on weighted/unweighted and directed/undirected networks.
angel(g_original, threshold, min_community_size)	Angel is a node-centric bottom-up community discovery algorithm.
coach(g_original, density_threshold, …)	The motivation behind the core-attachment (CoAch) algorithm comes from the observation that protein complexes often have a dense core of highly interactive proteins.
conga(g_original, number_communities)	CONGA (Cluster-Overlap Newman Girvan Algorithm) is an algorithm for discovering overlapping communities.
congo(g_original, number_communities, height)	CONGO (CONGA Optimized) is an optimization of the CONGA algortithm.
core_expansion(g_original, tolerance)	Core Expansion automatically detect the core of each possible community in the network.
dcs(g_original)	Divide and Conquer Strategy
demon(g_original, epsilon, min_com_size)	Demon is a node-centric bottom-up overlapping community discovery algorithm.
dpclus(g_original, weights, d_threshold, …)	DPClus projects weights onto an unweighted graph using a common neighbors approach.
ebgc(g_original)	The entropy-based clustering approach finds locally optimal clusters by growing a random seed in a manner that minimizes graph entropy.
ego_networks(g_original, level)	Ego-networks returns overlapping communities centered at each nodes within a given radius.
endntm(g_original, clusterings, epsilon)	Overlapping community detection algorithm based on an ensemble approach with a distributed neighbourhood threshold method (EnDNTM).
kclique(g_original, k)	Find k-clique communities in graph using the percolation method.
graph_entropy(g_original, weights)	This method takes advantage of the use of entropy with regard to information theory.
ipca(g_original, weights, t_in)	IPCA was introduced by Li et al.
lais2(g_original)	LAIS2 is an overlapping community discovery algorithm based on the density function.
lemon(g_original, seeds, min_com_size, …)	Lemon is a large scale overlapping community detection method based on local expansion via minimum one norm.
lpam(g_original, k, threshold, distance, seed)	Link Partitioning Around Medoids
lpanni(g_original, threshold)	LPANNI (Label Propagation Algorithm with Neighbor Node Influence) detects overlapping community structures by adopting fixed label propagation sequence based on the ascending order of node importance and label update strategy based on neighbor node influence and historical label preferred strategy.
lfm(g_original, alpha)	LFM is based on the local optimization of a fitness function.
multicom(g_original, seed_node)	MULTICOM is an algorithm for detecting multiple local communities, possibly overlapping, by expanding the initial seed set.
node_perception(g_original, threshold, …)	Node perception is based on the idea of joining together small sets of nodes.
overlapping_seed_set_expansion(g_original, …)	OSSE is an overlapping community detection algorithm optimizing the conductance community score The algorithm uses a seed set expansion approach; the key idea is to find good seeds, and then expand these seed sets using the personalized PageRank clustering procedure.
umstmo(g_original)	Overlapping community detection based on the union of all maximum spanning trees
percomvc(g_original)	The PercoMVC approach composes of two steps.
slpa(g_original, t, r)	SLPA is an overlapping community discovery that extends tha LPA.
walkscan(g_original, nb_steps, eps, …)	Random walk community detection method leveraging PageRank node scoring.
wCommunity(g_original, min_bel_degree, …)	Algorithm to identify overlapping communities in weighted graphs

Fuzzy Communities

A clustering is said to be a fuzzy if each node can belongs (with a different degree of likelihood) to more than one community. Methods in this subclass return as result a FuzzyNodeClustering object instance.

frc_fgsn(g_original, theta, eps, r)	Fuzzy-Rough Community Detection on Fuzzy Granular model of Social Network.
principled_clustering(g_original, cluster_count)	An efficient and principled method for detecting communities in networks

Node Attribute

Methods in this subclass return as result a AttrNodeClustering object instance.

eva(g_original, labels, weight, resolution, …)	The Eva algorithm extends the Louvain approach in order to deal with the attributes of the nodes (aka Louvain Extended to Vertex Attributes).
ilouvain(g_original, labels)	The I-Louvain algorithm extends the Louvain approach in order to deal only with the scalar attributes of the nodes.

Bipartite Graph Communities

Methods in this subclass return as result a BiNodeClustering object instance.

bimlpa(g_original, theta, lambd)	BiMLPA is designed to detect the many-to-many correspondence community in bipartite networks using multi-label propagation algorithm.
condor(g_original)	BRIM algorithm for bipartite community structure detection.
CPM_Bipartite(g_original, …)	CPM_Bipartite is the extension of CPM to bipartite graphs
infomap_bipartite(g_original, flags)	Infomap is based on ideas of information theory.
spectral(g_original, kmax, …)	SCD implements a Spectral Clustering algorithm for Communities Discovery.

Antichain Communities

Methods in this subclass are designed to extract communities from Directed Acyclic Graphs (DAG) and return as result a NodeClustering object instance.

siblinarity_antichain(g_original, …)

The algorithm extract communities from a DAG that (i) respects its intrinsic order and (ii) are composed of similar nodes.

Edge Clustering

Algorithms falling in this category generates communities composed by edges. They return as result a EdgeClustering object instance.

hierarchical_link_community(g_original)

HLC (hierarchical link clustering) is a method to classify links into topologically related groups.