Source-linked AI summary
A smart local moving algorithm for large-scale modularity-based community detection
Ludo Waltman, Nees Jan van Eck
TL;DR
Modularity optimization is NP-hard, creating a need for effective algorithms for large networks. The paper introduces smart local moving (SLM), which applies local moving more sophisticatedly than competing methods. SLM consistently outperforms original Louvain after enough iterations and often achieves higher modularity than ten Louvain runs or Louvain with multilevel refinement, although it can require considerably more computing time.
Problem
Optimizing modularity is NP-hard, while exact algorithms and many heuristics are limited to small networks, motivating scalable modularity optimization.
Method
SLM applies a local moving heuristic in a more sophisticated iterative procedure for modularity-based community detection.
Results
SLM consistently outperforms original Louvain after enough iterations and almost always yields higher modularity than 10 runs of original Louvain or Louvain with multilevel refinement.
Takeaways & Limitations
SLM is intended for community detection in large networks and also yields better results on medium-sized networks.
Takeaways & Limitations
SLM can require considerably more computing time than the compared Louvain approaches.
Abstract
from arXiv · showhide
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.
1. Introduction
Modularity optimization is computationally difficult, motivating efficient heuristics for large networks. The paper introduces SLM, which uses local moving more sophisticatedly than existing algorithms to improve modularity results across network sizes.
- Optimizing modularity is NP-hard, and exact algorithms are limited to small networks.
- Most existing modularity-optimization algorithms are suitable only for small and medium-sized networks.
- SLM is designed to produce high-quality results for networks with tens of millions of nodes and hundreds of millions of edges.
- For small and medium-sized networks, SLM is more or less competitive with the best algorithms presently available.
- The paper compares SLM with existing large-scale modularity-optimization algorithms and evaluates networks of different sizes.
- SLM relies on a local moving heuristic but applies it in a more sophisticated way than existing algorithms.
2. Existing algorithms
Existing modularity-based methods use local node movements and, in Louvain, recursively aggregate communities into reduced networks. These procedures can reach locally optimal solutions, while iterative refinement and merging improve the search.
- An iterative approach reruns the algorithms using each output as the next input, allowing further improvements beyond an initial solution.
- Modularity assigns higher quality to community structures with higher modularity values, which optimization seeks to maximize.
- The local moving heuristic repeatedly moves individual nodes when the move increases modularity, selecting the community with the largest gain.
- The heuristic stops when no individual node movement can further increase modularity, yielding a solution locally optimal for such movements.
- Louvain algorithm: Louvain repeatedly applies local moving, constructs reduced networks whose nodes represent communities, and continues until the network cannot be reduced further.
- Karate club example: On the karate club example, the community structure shown in Figure 5 is reported as globally optimal.
3. Smart local moving algorithm
SLM extends local moving by refining each current community through subnetworks before aggregation, allowing community splitting and group movements. This broader search can improve modularity beyond ordinary node-level and community-merging moves.
- SLM applies local moving within subnetworks formed from the nodes of each current community before constructing a reduced network.
- The reduced network initially groups nodes corresponding to communities from the same subnetwork into one community.
- SLM repeats local moving, subnetwork construction, and reduced-network construction until the network cannot be reduced further.
- Applying local moving at the subnetwork level allows communities to split and sets of nodes to move between communities.
- This additional freedom lets SLM search more broadly for high-quality modularity solutions than Louvain.
- Karate club example: In the karate club example, SLM reaches the same community structure as Louvain with multilevel refinement, reported as globally optimal.
- The iterative SLM variant keeps searching through community splitting and set movements, so further iterations may produce additional improvements.
4. Results
Across small, medium-sized, and large networks, SLM generally achieves higher modularity than Louvain variants when run iteratively, while requiring more computing time per run. Its advantage depends on sufficient iterations, and fewer SLM runs may offset the higher per-run cost.
- For networks beyond the smallest, SLM consistently outperforms both Louvain variants in modularity, with differences up to 1.0%.
- For small and medium-sized networks, SLM competes with the best available algorithms when sufficiently many iterations are used; 100 runs take under 10 seconds on the nine smallest networks.
- With one iteration, SLM slightly exceeds original Louvain but generally trails Louvain with multilevel refinement, sometimes by more than 1%.
- SLM requires more computing time than iterative Louvain variants, but a single SLM run typically outperforms multiple runs of the alternatives.
5. Conclusions
The paper introduces SLM for modularity-based community detection and evaluates it across small, medium-sized, large, and very large networks. SLM generally outperforms Louvain variants, remains competitive with CSA, and can optimize several modularity-function variants.
- 5. Conclusions: The paper introduces iterative variants of both the original Louvain algorithm and Louvain with multilevel refinement, alongside the new SLM algorithm.The work focuses primarily on community detection in large networks and compares these methods with existing algorithms.
- 5. Conclusions: SLM consistently outperforms the original Louvain algorithm and Louvain with multilevel refinement, except that all three perform equally well on very small networks.The analysis covers 13 small and medium-sized networks and six large and very large networks, with up to 40 million nodes and 800 million edges.
- 5. Conclusions: SLM requires considerably more computing time per run than the Louvain variants, but this is counterbalanced by its weaker need for multiple runs.The paper notes that excellent SLM results require a sufficiently large number of iterations per run.
- 5. Conclusions: A single SLM run almost always yields higher modularity than 10 runs of either Louvain variant on the six large networks.This reduces the need for multiple algorithm runs in large networks.
- 5. Conclusions: For 13 small and medium-sized networks, SLM is more or less competitive with CSA, although CSA performs slightly better on four networks and SLM performs better on one.For medium-sized networks, SLM requires much less computing time than CSA.
- 5. Conclusions: Although the experiments optimize the original modularity function, SLM can also be used for variants with a resolution parameter or modified mathematical structure.Examples include variants proposed by Reichardt and Bornholdt, Traag et al., and Waltman et al.
SmartLocalMovingAlgorithm
The SLM algorithm applies local moving to subnetworks, constructs a reduced network, and recursively refines community assignments. Evaluations compare its modularity and computing time with Louvain variants and CSA across small, medium-sized, and large networks.
- SLM starts with an initial node-to-community assignment and runs the local moving heuristic.
- For each community, SLM constructs a subnetwork, applies local moving, and records the resulting subcommunity assignments.
- SLM builds a reduced network from the subnetwork community structure and recursively applies itself before merging communities.
- The karate club example illustrates subnetworks splitting into communities and reduced networks before and after local moving.
- The large-network results report modularity differences relative to CSA for 100 runs with either one or 100 iterations.Negative and positive values indicate worse and better performance than CSA, respectively; equal performance is left unmarked.