Community Detection Algorithms: Concepts, Types, and Classic Methods

Community detection is a core graph algorithm that aims to identify groups of tightly‑connected nodes (communities) within a network, where connections inside a community are dense and connections between communities are sparse.

It shares similarities with unsupervised clustering—both seek to group data without labels—but differs because community detection operates on graph structures rather than arbitrary feature spaces.

Two main community types exist: non‑overlapping (each node belongs to a single community) and overlapping (nodes may belong to multiple communities).

The quality of a community partition is often measured by modularity , which quantifies the difference between the actual number of intra‑community edges and the expected number in a random graph with the same degree distribution; higher modularity indicates stronger community structure.

Louvain algorithm optimizes modularity through two iterative phases: (1) each node is moved to the neighboring community that yields the greatest modularity gain, and (2) communities are aggregated into super‑nodes to form a new, smaller graph, repeating until modularity no longer improves. This method is fast and scales to large networks.

Another classic approach encodes nodes into vectors (e.g., using node2vec ), then applies traditional clustering algorithms on these embeddings. Node2vec performs biased random walks on the graph to generate node sequences, which are fed into the Skip‑Gram model (borrowed from word2vec) to learn low‑dimensional representations.

The Infomap algorithm adopts an information‑theoretic perspective, seeking to minimize the average description length of a random walk on the graph. It builds a hierarchical coding scheme where nodes within the same community share short codes, effectively compressing the representation of the walk and revealing community structure.

Beyond these, methods based on label propagation, graph partitioning, and generalized community detection also exist, offering flexibility for various domains such as social networks, fraud detection, biology, and epidemiology.

In summary, community detection provides a powerful lens to uncover hidden structures in complex networks, and mastering its concepts and classic algorithms is essential for practitioners in graph analytics and related fields.