A smart local moving algorithm for large-scale modularity-based community detection

Abstract

We introduce a new algorithm for modularity-based community detection in large networks. The algorithm, which we refer to as a smart local moving algorithm, takes advantage of a well-known local moving heuristic that is also used by other algorithms. Compared with these other algorithms, our proposed algorithm uses the local moving heuristic in a more sophisticated way. Based on an analysis of a diverse set of networks, we show that our smart local moving algorithm identifies community structures with higher modularity values than other algorithms for large-scale modularity optimization, among which the popular 'Louvain algorithm' introduced by Blondel et al. (2008). The computational efficiency of our algorithm makes it possible to perform community detection in networks with tens of millions of nodes and hundreds of millions of edges. Our smart local moving algorithm also performs well in small and medium-sized networks. In short computing times, it identifies community structures with modularity values equally high as, or almost as high as, the highest values reported in the literature, and sometimes even higher than the highest values found in the literature.

References in corpus (12)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Resolution limit in community detection
• Statistical Mechanics of Community Detection
• Community structure in directed networks
• Narrow scope for resolution-limit-free community detection
• Detecting network communities by propagating labels under constraints
• Size reduction of complex networks preserving modularity
• Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
• Deterministic Modularity Optimization

Cited by in corpus (37)

• From Louvain to Leiden: guaranteeing well-connected communities
• Climate Change Research in View of Bibliometrics
• Which type of citation analysis generates the most accurate taxonomy of scientific and technical knowledge?
• Analysis of Network Clustering Algorithms and Cluster Quality Metrics at Scale
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Visualizing the context of citations referencing papers published by Eugene Garfield: A new type of keyword co-occurrence analysis
• Analysis and visualization of spatial transcriptomic data
• Granularity of algorithmically constructed publication-level classifications of research publications: Identification of topics
• Eigenvectors from Eigenvalues Sparse Principal Component Analysis (EESPCA)
• A Novel Approach to Predicting Exceptional Growth in Research
• Granularity of algorithmically constructed publication-level classifications of research publications: Identification of specialties
• Algorithmically generated subject categories based on citation relations: An empirical micro study using papers on overall water splitting
• Mapping social media attention in Microbiology: Identifying main topics and actors
• Quantifying the evolution of a scientific topic: reaction of the academic community to the Chornobyl disaster
• Randomizing growing networks with a time-respecting null model
• Evolution of Ego-networks in Social Media with Link Recommendations
• GVE-Leiden: Fast Leiden Algorithm for Community Detection in Shared Memory Setting
• Worldwide Scientific Landscape on Fires in Photovoltaic
• A Fast and Efficient Incremental Approach toward Dynamic Community Detection
• Community detection by label propagation with compression of flow
• Intermediacy of publications
• Community detection problem based on polarization measures:an application to Twitter: the COVID-19 case in Spain
• Single-cell entropy to quantify the cellular transcription from single-cell RNA-seq data
• Journal Maps, Interactive Overlays, and the Measurement of Interdisciplinarity on the Basis of Scopus Data (1996-2012)
• Additive Approximation Algorithms for Modularity Maximization
• From fuzzy information to community detection: an approach to social networks analysis with soft information
• Citation-based clustering of publications using CitNetExplorer and VOSviewer
• Identifying robust features of community structure in complex networks
• GVE-Louvain: Fast Louvain Algorithm for Community Detection in Shared Memory Setting
• How to interpret algorithmically constructed topical structures of research specialties? A case study comparing an internal and an external mapping of the topical structure of invasion biology
• Normalization of direct citations in publication-level networks: Evaluation of six approaches
• Outlier Edge Detection Using Random Graph Generation Models and Applications
• Community Structure aware Embedding of Nodes in a Network
• Limited Random Walk Algorithm for Big Graph Data Clustering
• Research Portfolio Analysis and Topic Prominence
• Can "Hot Spots" in the Sciences Be Mapped Using the Dynamics of Aggregated Journal-Journal Citation Relations?
• CitNetExplorer: A new software tool for analyzing and visualizing citation networks