Abstract
Community detection in large-scale networks often suffers from the "resolution limit," where small, dense communities are merged into larger clusters by algorithms optimizing metrics like Modularity. This paper introduces CEIL (Community detection using External and Internal scores in Large networks), a novel scoring function that balances internal density with external isolation. By utilizing a product-based approach, CEIL remains sensitive to community quality regardless of network size. Implemented via a modified Louvain heuristic, CEIL achieves linear-time scalability while outperforming traditional metrics in accuracy and resolution limit immunity across massive real-world datasets.
Introduction
In network science, communities are defined as groups of nodes with dense internal connections and sparse external connections. Detecting these structures is crucial for understanding complex systems, from social networks to biological interactions. The most prevalent method for community detection involves maximizing Modularity. However, Modularity possesses a fundamental "resolution limit": as the total network size increases, the threshold for what constitutes a distinct community also rises, causing small, tightly-knit groups to be overlooked or merged. Other metrics, such as Conductance, often fail by over-simplifying the network into a single large community.
Methods: The CEIL Score
The authors propose the CEIL score to address these limitations. CEIL evaluates a community based on two primary factors:
- Internal Score: Measures the density of edges within the community.
- External Score: Measures the fraction of edges incident to the community that remain within it, representing external isolation.
By taking the product of these two scores, CEIL ensures that a high-quality community must exhibit both high internal density and strong external separation. Crucially, the mathematical formulation of CEIL is independent of the total network size, making it inherently "resolution limit free."
To ensure scalability for networks with millions of nodes, the authors adapted the Louvain heuristic. This two-phase greedy algorithm iteratively moves nodes to maximize the CEIL score and then compresses identified communities into "super-nodes" for subsequent iterations.
Experimental Evaluation
The researchers evaluated CEIL using large-scale real-world datasets (LiveJournal, Youtube, DBLP, Amazon) and synthetic networks designed to test the resolution limit.
Key Results
- Resolution Limit Immunity: In a "Circle of Cliques" test where Modularity merged 30 small cliques into 15 larger groups, CEIL correctly identified all 30 individual communities.
- Sensitivity to Perturbations: CEIL demonstrated superior sensitivity compared to Modularity, Conductance, and Triad Participation Ratio across various network perturbations, including node swaps and random edge additions.
- Accuracy and Speed: CEIL showed higher Spearman’s rank correlation with ground-truth metrics and achieved higher Rand Index scores on datasets like Youtube and DBLP. Notably, CEIL's execution time is competitive with the standard Louvain method, even outperforming it on the DBLP dataset (77.77s vs 134.39s).
Conclusion
CEIL provides a robust, scalable solution for community detection that overcomes the resolution limit of Modularity. By balancing internal and external connectivity through a product-based scoring function, it identifies meaningful structures in massive networks with high accuracy and efficiency. Future work may involve extending the algorithm to natively detect overlapping communities and directed graphs.
Summary updated