Source-linked AI summary
A General Optimization Technique for High Quality Community Detection in Complex Networks
Stanislav Sobolevsky, Riccardo Campari, Alexander Belyi, Carlo Ratti
TL;DR
Community detection often optimizes modularity or alternative objective functions, motivating a general search strategy that can optimize different measures. The paper presents Combo and finds that it consistently outperforms compared algorithms for modularity while matching Infomap for code-length optimization, with memory constraints limiting larger-network use.
Problem
Community detection relies on optimizing objective functions such as modularity, but alternative measures and the quality of their resulting partitions require systematic comparison.
Method
The paper presents Combo, an optimization algorithm for community detection capable of handling various objective functions, and evaluates modularity and description code length.
Results
Combo consistently outperforms compared algorithms for modularity and provides results on par with Infomap for code-length optimization.
Takeaways & Limitations
Combo is a strong choice when maximizing partitioning objective-function quality is more important than strict execution-time limits.
Takeaways & Limitations
The current implementation has a maximal practical network-size limitation because of memory constraints.
Abstract
from arXiv · showhide
Recent years have witnessed the development of a large body of algorithms for community detection in complex networks. Most of them are based upon the optimization of objective functions, among which modularity is the most common, though a number of alternatives have been suggested in the scientific literature. We present here an effective general search strategy for the optimization of various objective functions for community detection purposes. When applied to modularity, on both real-world and synthetic networks, our search strategy substantially outperforms the best existing algorithms in terms of final scores of the objective function; for description length, its performance is on par with the original Infomap algorithm. The execution time of our algorithm is on par with non-greedy alternatives present in literature, and networks of up to 10,000 nodes can be analyzed in time spans ranging from minutes to a few hours on average workstations, making our approach readily applicable to tasks which require the quality of partitioning to be as high as possible, and are not limited by strict time constraints. Finally, based on the most effective of the available optimization techniques, we compare the performance of modularity and code length as objective functions, in terms of the quality of the partitions one can achieve by optimizing them. To this end, we evaluated the ability of each objective function to reconstruct the underlying structure of a large set of synthetic and real-world networks.
1. The algorithm
Combo is a general community-detection optimization strategy that combines mergers, splits, and node recombinations, refining candidate partitions through Kernighan–Lin shifts. Random initial configurations improve modularity but increase runtime, while memory limits constrain larger-network use.
- Search strategy: Combo combines community mergers, splits, and recombinations by evaluating node redistributions between source and destination communities.The destination may be an existing or new community, and complete mergers are included.
- Search strategy: For each candidate configuration, Kernighan–Lin shifts repeatedly move the node with the greatest gain or smallest loss, retaining the best intermediate partition.The algorithm evaluates original, complete-merger, and random intermediate configurations before selecting the highest objective-function score.
- Random initialization: 2%: random initial configurations increase the resulting modularity score on average, sometimes producing considerable partitioning improvements.The randomization is therefore useful despite its computational cost.
- Random initialization: 4.2 times faster: removing random configurations accelerates Combo on average, motivating a simplified version when execution time is more important.Replacing them with partitions from other methods can make the algorithm more prone to local maxima.
- Computational behavior: 1.8: execution time follows an observed power law in network size, with networks up to 30 000 nodes handled within a few hours in the reported setup.The authors also justify an upper bound of O(N^2 log(C)), where N is the number of nodes and C the number of communities.
- Computational behavior: Memory availability is the current implementation’s bottleneck, and virtual-memory use slows computation further on bigger networks.This limits the maximum network size that can be handled within a reasonable time.
2. Modularity optimization benchmarks
The modularity benchmarks compare Combo with established algorithms across literature, telecom, and synthetic networks using partition-quality and execution-time measures. Combo achieves the strongest modularity results, while greedy methods remain faster and may be preferable when computation time dominates.
- Benchmark design: The benchmark spans publicly available networks, five telecom graphs, and ten synthetic networks generated with the Lancichinetti–Fortunato–Radicchi approach.Six algorithms were compared using average ranks for modularity and execution time.
- Partition quality: 0.98: Combo has the highest average normalized partition-quality rank, ahead of Simulated Annealing at 0.67, Louvain at 0.55, and Spectral at 0.51.The rank aggregates algorithm performance across the benchmark networks.
- Execution time: Combo is slower than greedy aggregation algorithms such as Louvain and Le Martelot, but faster than Simulated Annealing and NGA in the reported comparisons.In worst cases, computation takes hours for networks ranging from thousands to tens of thousands of nodes.
- Execution time: When computational time is crucial and partitioning quality is less important, faster approaches may be the better choice.This trade-off follows from Combo’s stronger quality results and slower execution relative to greedy methods.
- Partition quality: Around 2%: Combo exceeds its nearest rivals on average in achieved modularity score.The benchmark emphasizes that even a 0.5% modularity difference can substantially affect community structure.
3. Importance of Precision: The Effect of Small Changes in Modularity Values
Small modularity differences can produce substantially different community partitions, so score precision matters when evaluating optimization methods. Comparisons with synthetic and real-world reference structures show that these partition changes can affect structural agreement.
- Sensitivity to small modularity changes: Differences in modularity below 0.01 or even 0.001 can produce substantial variations in community structure, with NMI sometimes as low as 0.6–0.7.NMI measures similarity between partitions and equals 1 for identical partitions.
- Limits of interpretation: The paper cautions that whether higher modularity means better partition quality remains unresolved because modularity itself has known limitations, including the resolution limit.Known community structure is not necessarily theoretically optimal under modularity.
- Agreement with known structure: On LFR synthetic networks, Combo partitions were 99–100% similar to the planted structure, whereas slightly lower-modularity alternatives usually achieved 95–97% and sometimes only 70% or 15% NMI.The benchmark compared Combo and Louvain partitions with the original community structure used to generate each network.
- Real-world illustration: A modularity gain of only 0.0043 produced visible macroscopic differences in the United Kingdom telephone-network partition.The higher-scoring partition had less spatial noise and better agreement with official administrative divisions.
- Real-world illustration: The telephone-network comparison yielded NMI 0.804 for Combo versus 0.703 for Louvain, despite modularity values of 0.6753 and 0.6710, respectively.The caption reports cleaner geographical separation for Combo and greater similarity to official administrative divisions.
4. Minimum description code length benchmarks
Combo performs competitively when optimizing description code length and enables a direct comparison between code length and modularity. Code length is close to Infomap overall, while objective-function performance varies with network size and noise.
- Benchmark against Infomap: Combo achieves code-length values within 5% on one network and below 3% on all others compared with Infomap.Combo is better on 8 networks, Infomap on 9, and results are identical on the remaining networks.
- Benchmark against Infomap: Combo provides a valid alternative and complement to Infomap, finding better solutions in several cases.The paper reports that Combo efficiently optimizes both modularity and code length.
- Objective-function comparison: Combo’s near-optimal optimization of both objectives permits a fair comparison of modularity and code length as community-detection objectives.The comparison evaluates how well each objective reconstructs pre-imposed community structure in synthetic networks.
- Objective-function comparison: Modularity reconstructs communities more reliably in complex, noisier cases, whereas code length performs poorly on smaller networks.These results concern reconstruction of known community structure in the benchmark networks.
- Objective-function comparison: For larger networks with relatively low noise, code length outperforms modularity, while modularity is recommended for weaker clustering effects.The paper also describes code length as potentially preferable for larger networks with relatively strong communities.
5. Conclusions
The paper presents Combo as a flexible optimization algorithm for community detection, achieving leading modularity results and code-length performance comparable to Infomap. Its practical use is strongest when partition quality matters more than strict runtime constraints and networks remain within current memory limits.
- Combo consistently outperforms compared algorithms, including the current state of the art, when optimizing modularity.
- Combo achieves code-length optimization results on par with Infomap, the defining algorithm for that objective function.
- Combo can handle networks near its applicability threshold within a few hours, while smaller networks of several thousand nodes require minutes.
- Combo is most suitable when partition quality is paramount, networks are not too large, and runtime is not strictly constrained.
- The optimization framework can accommodate other objective functions, limit the number of communities, and fine-tune partitions produced by other algorithms.
- The study compares modularity and description code length by evaluating how well optimized partitions reproduce known network community structure.