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

By Ludo Waltman, Nees Jan van Eck. European Physical Journal B : Condensed Matter Physics, 2013

1,012 citations recorded by the source corpus.

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”. 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.

Subfields: Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/589c3bc81af17918b5145ad042d189b19b83502d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

Citations in the corpus

Integrating single-cell transcriptomic data across different conditions, technologies, and species (2018, methodology): “To partition cells into clusters, we used the smart local moving (SLM) algorithm for modularity-based clustering 63 .”
CitNetExplorer: A new software tool for analyzing and visualizing citation networks (2014, methodology): “In order to maximize (4), CitNetExplorer uses the smart local moving algorithm that we introduced in a recent paper (Waltman & Van Eck, 2013).”
Document co-citation analysis to enhance transdisciplinary research (2018, methodology): “Visualization To visualize the networks of co-cited documents as communities, an SLM community detection algorithm (32) was applied within the Sci2 platform to identify modular groupings.”
Ten years of research change using Google Trends: From the perspective of big data utilizations and applications (2017, background): “…life cycle and the trend of developments in related literature, in general, paper publications have a strong tendency to precede patents, while patents have the characteristic of being temporally closer to commercialization (Daim et al., 2005; Martin and Daim, 2007; Watts and Porter, 1997).”
Cell diversity and network dynamics in photosensitive human brain organoids (2017, methodology): “A first round of clustering with the Louvain modularity-based community detection algorithm 40 set at a resolution of 0.01 was used to generate a total of 10 first-round clusters (FindClusters function in Seurat).”
From Louvain to Leiden: guaranteeing well-connected communities (2018, methodology): “The new algorithm integrates several earlier improvements, incorporating a combination of smart local move 15 , fast local move 16,17 and random neighbour move 18 .”
A general and flexible method for signal extraction from single-cell RNA-seq data (2017, positive): “In particular, we applied a popular clustering method, based on the identification of shared nearest neighbors [33], similar to that of Macosko et al.”