A Comprehensive Review of Community Detection in Graphs

1.1 Motivation

• Graph-based community detection can provide insights into the functioning and behavior of real-world social, biological, and technological systems.The review also seeks to bridge perspectives from statistical physics and applications across domains.Source: §1.1 · p. 1

1.2 Contribution

• The review categorizes mainstream methods into four frameworks and compares methods from each to examine network dynamics and implications across domains.It also presents Revised Medoid-Shift (RMS), combining Medoid-Shift and K-nearest neighbors to address Mean-Shift’s difficulty with non-Euclidean graph data.Source: §1.2 · p. 2

1.3 Road Map

• The roadmap moves from research background to a review of existing methods and the new algorithm, then to findings and discussion, and finally to conclusions and future directions.The paper identifies these stages as Sections 2, 3, 4, and 5, respectively.Source: §1.3 · p. 2

Community detection foundations

• Community detection seeks groups with strong internal and relatively weak external connections, supporting analysis of network organization, dynamics, and functionality.The cited applications include social networks, biology, and information retrieval.Source: §2 · p. 2

Modularity-based methods

• Modularity optimization compares within-community edge density with a null model and seeks a partition maximizing modularity.The passage names Louvain, Infomap, and Kernighan-Lin as variations or extensions.Source: §2 · p. 3

Spectral methods

• Spectral clustering uses graph Laplacian eigenvectors and eigenvalues to identify communities, with effectiveness noted when networks have clear spectral properties.Normalized Cut and RatioCut are cited examples.Source: §2 · p. 3

Probabilistic models

• Stochastic Block Models assume within-community node pairs are more likely to connect than between-community pairs, with likelihood or Bayesian inference used to estimate model parameters.Source: §2 · p. 3

Deep learning

• Deep-learning approaches, including neural networks, graph neural networks, and reinforcement learning, are used to capture complex network patterns and dependencies.Source: §2 · p. 3

Open challenges

• Persistent challenges include overlapping communities, the resolution limit, scalability on large networks, and robustness to noise and perturbations.The background also notes that modularity, spectral, probabilistic, and machine-learning approaches contribute to ongoing work on complex networks.Source: §2 · p. 3

Methodology overview

• Figure 1 is identified as an overview of the community-detection methodology.Source: Figure 1 · p. 4
• The section reviews existing community-detection approaches and introduces the novel method developed in the study.The stated aim is to give an overview of the landscape and the strengths and limitations of different approaches.Source: §3 · p. 4
• The section organizes its overview around four popular types of methods and models for community detection in graphs.Source: §3 · p. 4

3.1.1 Louvain method

• The Louvain method alternates local modularity refinement and community aggregation; its parallel PLA implementation handled graphs with up to 138 billion edges across thousands of nodes.PLA maintained or slightly improved convergence properties, modularity, and detected-community quality relative to original Louvain.Source: §3.1.1 · p. 5

3.1.2 Infomap method

• Infomap minimizes the description length of a random walker’s journey, while Infomap-SA achieved higher modularity and density with reduced computational complexity versus traditional Infomap.Infomap-SA combines Infomap with simulated annealing to improve exploration of the solution space.Source: §3.1.2 · pp. 7–8

3.1.3 Kernighan-Lin method

• Kernighan–Lin uses greedy node reassignments but may miss the global optimum, while MFTS adds cross-community fine-tuning to improve modularity without increasing computational complexity order.MFTS’s final-tuning step considers moving each node to any community.Source: §3.1.3 · pp. 8–9

3.1.4 EdMot

• EdMot addresses fragmented higher-order network representations by enhancing edges to help connect nodes sharing a community even when they lack hypergraph connections.It targets the limitations of methods that focus on lower-order structures or assume a connected hypergraph.Source: §3.1.4 · p. 9

3.1.5 LPA

• LPA variants stabilize or constrain propagation through node importance, optimization constraints, or influence-aware updates, with LPA-HM reporting strong accuracy for mixing parameters ≥ 0.5.LPA-MNI orders updates by degree centrality; CLPA penalizes undesirable solutions; LPA-HM uses common neighbors and label influence, with early stopping based on modularity and community-number changes.Source: §3.1.5 · pp. 9–11
• FLPA (Traag & ˇSubelj, 2023) uses a dynamic queue to focus label updates on affected nodes, running up to 700 times faster than standard LPA without compromising community quality.Each node retains the majority label within its immediate community.Source: §3.1.5 · p. 11
• LDA-LPA (Wang et al., 2021a) combines topology-based LDA community assignments with LPA refinement and outperforms benchmark methods on real-world and synthetic networks.It treats communities as topics and nodes as documents represented through their neighborhoods, requiring no node or edge attributes.Source: §3.1.5 · p. 11
• DLPA incorporates direction and signed edge weights into propagation and outperforms existing approaches on three measures for directed signed networks.The reported measures are directed signed modularity, directed signed flow-based capacity, and frustration.Source: §3.1.5 · p. 11
• NI-LPA (El Kouni et al., 2020) uses node importance based on degree and clustering coefficient to address LPA instability and improve overlapping-community detection, efficiency, and precision.Its process initializes unique node labels and uses specialized propagation and filtering.Source: §3.1.5 · pp. 11–12
• MSH-LPA (Chen et al., 2020a) uses SH-index centrality and similarity-weighted edges to improve multilayer community detection, achieving higher modularity and accuracy with near-linear computational complexity.It aggregates the original multilayer network into a weighted single-layer network.Source: §3.1.5 · p. 12

3.2 Spectral Clustering Methods

• Spectral clustering constructs a similarity matrix, derives a graph Laplacian, decomposes it, and clusters selected eigenvectors; matrix and Laplacian choices can vary.The number of eigenvectors considered depends on the desired number of communities.Source: §3.2 · p. 12

3.2.1 Normalized Cut algorithm

• Normalized Cut minimizes the normalized cut value by decomposing the normalized Laplacian and clustering the resulting eigenvectors.Source: §3.2.1 · pp. 12–13

3.2.2 RatioCut algorithm

• RatioCut minimizes a dissimilarity measure based on edges between communities relative to edges within each community, using eigenvalue decomposition followed by clustering.Source: §3.2.2 · p. 13

3.2.3 Graph Partitioning by Eigenvectors

• Graph Partitioning by Eigenvectors hierarchically divides nodes by the polarity of leading Laplacian eigenvector components until the desired community count emerges.Its partitioning process is iterative and can be tailored to diverse datasets.Source: §3.2.3 · p. 13
• ASC refines spectral clustering by aggregating nodes using eigenvector-space similarity and edge weights, with conductance as its stopping criterion.Experiments on LiveJournal and Orkut report effective detection, while computational efficiency and choosing the community count remain challenges.Source: §3.2.3 · p. 13

3.2.4 Recursive Spectral Bisection

• Recursive Spectral Bisection repeatedly bisects subgraphs, adapting partitions to local structure to detect communities at multiple granularities.The passage describes the method as robust and scalable across network sizes and densities.Source: §3.2.4 · pp. 13–14
• GRSBM recursively applies spectral bisection after network sparsification, using modularity maximization to guide splits and determine the number of communities without prior specification.Experiments report improved modularity and adjusted rand index over existing methods.Source: §3.2.4 · p. 14

3.2.5 GEMSEC

• GEMSEC jointly learns node embeddings and clusters, optimizing vertex features to preserve sampled neighborhoods while using network-structure regularization.The learned embeddings are intended to capture local connectivity patterns.Source: §3.2.5 · p. 14

3.3 Probabilistic Models

• Probabilistic models use variables, parameters, probability distributions, and inference to quantify uncertainty and derive insights from data.Variables may be observed or latent, and parameters may be fixed or random; inference includes maximum likelihood, Bayesian, and variational approaches.Source: §3.3 · pp. 14–15

3.3.1 Gaussian Mixture Models (GMM)

• GMMs represent data as Gaussian mixtures, with EM iteratively estimating component memberships and updating model parameters.ComE models communities as multivariate Gaussian distributions and jointly learns community-aware node embeddings; a DeepWalk-based variational Bayesian GMM can automatically determine the number of communities (Cavallari et al., 2017; Chen et al., 2020b).Source: §3.3.1 · pp. 15–16

3.3.2 Hidden Markov Models (HMM)

• HMMs model sequential observations through hidden states, transition and emission probabilities, and inference methods such as Viterbi and Forward-Backward.HMM-MODCD combines an HMM with multi-objective evolutionary optimization and uses Viterbi temporal analysis to trace evolving communities in dynamic networks.Source: §3.3.2 · pp. 16–17

3.3.3 Bayesian-based Method

• Bayesian community methods use MCMC or variational inference to model memberships and structure, including cohesion-aware link prediction, generalized communities, and covariate-informed partitions.BCD learns community cohesion to distinguish internal from external link densities; NEGCD addresses assortative and disassortative structures, while BCDC can infer the number of communities without prior specification.Source: §3.3.3 · pp. 17–18

3.3.4 Stochastic Block Model-Based Methods

• Under stated connectivity and community-size conditions, spectral partitioning in sparse stochastic block models keeps misclassified vertices below a small fraction of the network with high probability as n grows.For large-scale networks, DCD uses pilot nodes to identify pseudo-centers, reducing communication and storage needs while avoiding iterative computations on worker servers.Source: §3.3.4 · p. 19

3.3.5 LDA

• LDA-based approaches model communities as latent topics, including topology-only SSN-LDA and LDA-LPA, which represents nodes as random-walk documents and refines assignments with label propagation.SSN-LDA was evaluated on CiteSeer and NanoSCI collaborative networks; LDA-LPA requires structural data rather than node or edge attributes (Zhang et al., 2007; Wang et al., 2021a).Source: §3.3.5 · p. 20

3.3.6 MRF(Markov Random Field) based

• MRF-based community detection models pairwise node potentials, while MRFasGCN combines topology and node semantics and reports superior performance and scalability on large benchmarks.NetMRF rewards internal community edges and penalizes between-community edges; MRFasGCN uses an end-to-end semi-supervised architecture.Source: §3.3.6 · pp. 20–21
• ModMRF models modularity as a Markov Random Field energy and uses belief propagation to infer community counts, addressing over-partitioning while reporting accuracy and efficiency gains on real and synthetic datasets.Its statistical formulation also enables different statistical inference methods for optimization.Source: §3.3.6 · p. 21

3.3.7 Non-negative Matrix Factorization(NMF) based method

• NMF uses nonnegative components for parts-based representations and offers Euclidean-distance and Kullback-Leibler-divergence multiplicative updates, both shown to converge monotonically.The passage notes applications in image processing, text mining, and bioinformatics.Source: §3.3.7 · p. 21
• The NMF community-detection method (Wang et al., 2008) applies similarity measures including diffusion kernels and shortest paths, with diffusion-kernel similarity highlighted for finding biologically meaningful modules in large biological networks.Comparisons report superior performance on synthetic and real-world datasets.Source: §3.3.7 · p. 21
• SymNMF (Kuang et al., 2012) factorizes a symmetric pairwise-similarity matrix that need not be nonnegative, extending NMF to graph clustering; a Newton-like method improves computational efficiency.Source: §3.3.7 · p. 21
• NCNMF combines higher-order proximity and node centrality, using topological similarity and Gini impurity to promote sparse memberships; experiments report superiority to state-of-the-art methods.The method is described as scalable and interpretable.Source: §3.3.7 · pp. 21–22
• PODCD uses a probabilistic graphical framework and temporally regularized NMF to model evolving, overlapping community memberships, with reported gains in mapping evolution accurately and coherently.Memberships are adjusted using historical trends.Source: §3.3.7 · p. 22
• The sparse-network NMF method uses regularization matrices and local feature vectors to represent network topology and address sparsity and noise, reporting higher accuracy than standard NMF methods.The passage identifies further algorithmic-complexity reduction and adaptive community-number estimation as limitations.Source: §3.3.7 · p. 22

3.4 Deep Learning Approaches

• The reviewed deep-learning approaches span graph convolution, graph autoencoders, attention networks, and graph representation learning for community detection.The section presents these as distinct families of methods for graph-structured data.Source: §3.4 · p. 22, §3.4.1 · p. 22, §3.4.2 · p. 23

3.4.1 GCN

• GCN approaches combine graph structure with node attributes or neighborhood information, with examples spanning attributed clustering, unsupervised detection, and community refinement.Attributed graph convolution adapts convolution order and depth; other reviewed methods combine GCNs with label sampling, reinforcement learning, or community-level similarity.Source: §3.4.1 · pp. 22–23

3.4.2 Graph Autoencoders

• Graph autoencoders learn low-dimensional node representations while preserving graph connections; reviewed variants add probabilistic latents, structural weighting, modularity, or community-aware walks.VGAE uses a GCN encoder and inner-product decoder; SSGCAE targets overlapping communities in attributed graphs, while CSEA extracts dense core structure with K-truss.Source: §3.4.2 · pp. 23–24

3.4.3 Graph Attention Networks (GAT)

• GAT methods use attention to weight neighboring-node information, while reviewed applications address attributed, multiplex, and overlapping community detection.HiAN jointly optimizes node representations and community assignments; GEAM fuses multiple network layers, and other reviewed methods combine attention with autoencoders.Source: §3.4.3 · p. 25, §3.4.4 · p. 26

3.4.4 Graph representation learning

• Graph representation-learning methods connect community detection with embeddings, including joint probabilistic modeling, neighborhood aggregation, and dynamic-network representations.vGraph jointly learns node representations and community memberships; GraphSAGE aggregates neighborhood information, while DEDW incorporates historical network structure.Source: §3.4.4 · pp. 26–27

3.5 Our Methodology – RMS

• Medoid-Shift shifts toward a specific neighboring data point, unlike Mean-Shift, which shifts toward a location; the review presents Medoid-Shift as suited to distance-based community detection.RMS changes the neighborhood definition to KNN and selects the next point using similarities between neighborhood points and their KNNs.Source: §3.5 · pp. 27–28, Figure 2 · p. 27

3.5.1 The Definition of Graph in Social Network.

• RMS represents the social network as undirected, aggregating directed-edge weights between each endpoint pair when converting directed graphs.The section describes the network as a graph of nodes and edges representing relationships.Source: §3.5.1 · p. 28

3.5.2 Data Preprocessing of the RMS Algorithm

• RMS uses a similarity matrix for graph weights; for an unweighted graph, it proposes a separate similarity-based weight calculation.The section identifies K-nearest neighbors and connected nodes as components of its similarity representation.Source: §3.5.2 · p. 29

3.5.3 Core Process of the RMS Algorithm

• RMS calculates each point’s similarity sum over its KNN, repeatedly selects the highest-sum point among each medoid and its neighbors, then assigns points by their convergent center.Iterations stop when successive medoid sets match; the stated worst-case complexity is O(|V|^2), usually much less in this work.Source: §3.5.3 · pp. 29–30

4.1 Overall Experiment Setup

• Experiments divide datasets by whether ground-truth partitions are available; the known-partition datasets are unweighted, while the no-ground-truth datasets are weighted.The study evaluates five real-world datasets in each group and reports implementing the compared methods in Python.Source: §4.1 · p. 30, §4.4 · p. 31, §4.5 · p. 33

4.2 Evaluation Metrics

• For evaluating experimental results, the study uses modularity on datasets without ground-truth partitions and Normalized Mutual Information (NMI) on datasets with ground-truth partitions.Table 2 reports NMI, and the number of clusters is given in parentheses.Source: §4.1 · p. 30, §4.5 · p. 33

4.3 Comparative Methods

• The comparison includes classical and state-of-the-art methods, including Label Propagation, TNS-LPA, EdMot, GraphSage, VGAE, and Medoid-Shift.The reported comparison also includes methods such as Girvan Newman, Louvain-LPA, GEMSEC, ComE, RSBM, and LDA-LPA.Source: §4.3 · p. 30

4.4 Experimental Results for the Datasets without Ground Truth Partition

• RMS records modularity scores of 0.5379, 0.5650, 0.4271, 0.1413, and 0.8357 on Cell Phone, Enron Email, Lesmis, USA Airport, and ASTRO-PH, respectively.It does not lead on every dataset: ComE has the highest scores on Lesmis and USA Airport, while LDA-LPA leads on ASTRO-PH.Source: §4.4 · pp. 31, 33, Table 1 · p. 32
• Across the no-ground-truth datasets, RMS is described as competitive with most methods, but ComE leads on Lesmis and USA Airport and LDA-LPA leads on ASTRO-PH.TNS-LPA, LDA-LPA, and ComE are identified as achieving state-of-the-art-level performance in their respective approaches.Source: §4.4 · pp. 31, 33

4.5 Experimental Results for the Datasets with Ground Truth Partition

• RMS achieves NMI values of 0.7846 on Dolphins and 0.7768 on American Football, outperforming most comparative methods on Dolphins and showing competitive performance on American Football.TNS-LPA and LDA-LPA are also described as competitive on multiple datasets, while GraphSage and Infomap-SA perform relatively poorly on most datasets.Source: §4.5 · pp. 33, 35, Table 2 · p. 34

• The survey synthesizes modularity-based, spectral, probabilistic, and deep-learning perspectives, reporting their effectiveness across diverse network structures.Source: §5 · p. 35
• Evaluation on commonly used datasets with NMI and modularity offered insights into method strengths and limitations to guide selection for specific requirements.Source: §5 · p. 35
• Future work proposes combining perspectives for potentially greater accuracy and robustness while addressing scalability and efficiency in growing networks.Source: §5 · p. 35
• Future applications could investigate community detection in social, biological, and recommendation networks for practical insights and solutions.Source: §5 · p. 35
• RMS outperformed traditional methods, automatically selects the optimal number of communities, and uses KNN to define neighborhoods more effectively than a fixed-radius parameter.Source: §5 · p. 35
• The tested methods have not yet mostly matched ground-truth partitions, and further improvement on partitions evaluated by NMI and modularity remains necessary.Source: §5 · p. 35
• Future analysis could test RMS in graph scenarios and examine how methods unsuited to non-Euclidean spaces can use distance or similarity matrices.Source: §5 · pp. 35–36