From Louvain to Leiden: guaranteeing well-connected communities

Scientific Reports - Tập 9 Số 1
Vincent Traag1, Ludo Waltman1, Nees Jan van Eck1
1Centre for Science and Technology Studies, Leiden University, Leiden, The Netherlands

Tóm tắt

AbstractCommunity detection is often used to understand the structure of large and complex networks. One of the most popular algorithms for uncovering community structure is the so-called Louvain algorithm. We show that this algorithm has a major defect that largely went unnoticed until now: the Louvain algorithm may yield arbitrarily badly connected communities. In the worst case, communities may even be disconnected, especially when running the algorithm iteratively. In our experimental analysis, we observe that up to 25% of the communities are badly connected and up to 16% are disconnected. To address this problem, we introduce the Leiden algorithm. We prove that the Leiden algorithm yields communities that are guaranteed to be connected. In addition, we prove that, when the Leiden algorithm is applied iteratively, it converges to a partition in which all subsets of all communities are locally optimally assigned. Furthermore, by relying on a fast local move approach, the Leiden algorithm runs faster than the Louvain algorithm. We demonstrate the performance of the Leiden algorithm for several benchmark and real-world networks. We find that the Leiden algorithm is faster than the Louvain algorithm and uncovers better partitions, in addition to providing explicit guarantees.

Từ khóa


Tài liệu tham khảo

Fortunato, S. Community detection in graphs. Phys. Rep. 486, 75–174, https://doi.org/10.1016/j.physrep.2009.11.002 (2010).

Porter, M. A., Onnela, J.-P. & Mucha, P. J. Communities in Networks. Not. AMS 56, 1082–1097 (2009).

Newman, M. E. J. & Girvan, M. Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113, https://doi.org/10.1103/PhysRevE.69.026113 (2004).

Reichardt, J. & Bornholdt, S. Statistical mechanics of community detection. Phys. Rev. E 74, 016110, https://doi.org/10.1103/PhysRevE.74.016110 (2006).

Brandes, U. et al. On Modularity Clustering. IEEE Trans. Knowl. Data Eng. 20, 172–188, https://doi.org/10.1109/TKDE.2007.190689 (2008).

Clauset, A., Newman, M. E. J. & Moore, C. Finding community structure in very large networks. Phys. Rev. E 70, 066111, https://doi.org/10.1103/PhysRevE.70.066111 (2004).

Duch, J. & Arenas, A. Community detection in complex networks using extremal optimization. Phys. Rev. E 72, 027104, https://doi.org/10.1103/PhysRevE.72.027104 (2005).

Guimerà, R. & Nunes Amaral, L. A. Functional cartography of complex metabolic networks. Nature 433, 895–900, https://doi.org/10.1038/nature03288 (2005).

Newman, M. E. J. Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74, 036104, https://doi.org/10.1103/PhysRevE.74.036104 (2006).

Blondel, V. D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. Fast unfolding of communities in large networks. J. Stat. Mech. Theory Exp. 10008, 6, https://doi.org/10.1088/1742-5468/2008/10/P10008 (2008).

Lancichinetti, A. & Fortunato, S. Community detection algorithms: A comparative analysis. Phys. Rev. E 80, 056117, https://doi.org/10.1103/PhysRevE.80.056117 (2009).

Yang, Z., Algesheimer, R. & Tessone, C. J. A Comparative Analysis of Community Detection Algorithms on Artificial Networks. Sci. Rep. 6, 30750, https://doi.org/10.1038/srep30750 (2016).

Traag, V. A., Van Dooren, P. & Nesterov, Y. Narrow scope for resolution-limit-free community detection. Phys. Rev. E 84, 016114, https://doi.org/10.1103/PhysRevE.84.016114 (2011).

Fortunato, S. & Barthélemy, M. Resolution Limit in Community Detection. Proc. Natl. Acad. Sci. USA 104, 36, https://doi.org/10.1073/pnas.0605965104 (2007).

Waltman, L. & van Eck, N. J. A smart local moving algorithm for large-scale modularity-based community detection. Eur. Phys. J. B 86, 471, https://doi.org/10.1140/epjb/e2013-40829-0 (2013).

Ozaki, N., Tezuka, H. & Inaba, M. A Simple Acceleration Method for the Louvain Algorithm. Int. J. Comput. Electr. Eng. 8, 207–218, https://doi.org/10.17706/IJCEE.2016.8.3.207-218 (2016).

Bae, S., Halperin, D., West, J. D., Rosvall, M. & Howe, B. Scalable and Efficient Flow-Based Community Detection for Large-Scale Graph Analysis. ACM Trans. Knowl. Discov. Data 11, 1–30, https://doi.org/10.1145/2992785 (2017).

Traag, V. A. Faster unfolding of communities: Speeding up the Louvain algorithm. Phys. Rev. E 92, 032801, https://doi.org/10.1103/PhysRevE.92.032801 (2015).

Luecken, M. D. Application of multi-resolution partitioning of interaction networks to the study of complex disease. Ph.D. thesis, (University of Oxford, 2016).

Wolf, F. A. et al. Graph abstraction reconciles clustering with trajectory inference through a topology preserving map of single cells. bioRxiv, https://doi.org/10.1101/208819 (2018).

Raghavan, U., Albert, R. & Kumara, S. Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76, 036106, https://doi.org/10.1103/PhysRevE.76.036106 (2007).

Rotta, R. & Noack, A. Multilevel local search algorithms for modularity clustering. J. Exp. Algorithmics 16, 2.1, https://doi.org/10.1145/1963190.1970376 (2011).

Traag, V. A., Waltman, L. & van Eck, N. J. networkanalysis. Zenodo, https://doi.org/10.5281/zenodo.1466831 https://github.com/CWTSLeiden/networkanalysis. Source Code (2018).

Traag, V. A. leidenalg 0.7.0. Zenodo, https://doi.org/10.5281/zenodo.1469357 https://github.com/vtraag/leidenalg. Source Code (2018).

Bullmore, E. & Sporns, O. Complex brain networks: graph theoretical analysis of structural and functional systems. Nat. Rev. Neurosci. 10, 186–198, https://doi.org/10.1038/nrn2575 (2009).

Waltman, L. & van Eck, N. J. A new methodology for constructing a publication-level classification system of science. J. Am. Soc. Inf. Sci. Technol. 63, 2378–2392, https://doi.org/10.1002/asi.22748 (2012).

Klavans, R. & Boyack, K. W. Which Type of Citation Analysis Generates the Most Accurate Taxonomy of Scientific and Technical Knowledge? J. Assoc. Inf. Sci. Technol. 68, 984–998, https://doi.org/10.1002/asi.23734 (2017).

Lancichinetti, A., Fortunato, S. & Radicchi, F. Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78, 046110, https://doi.org/10.1103/PhysRevE.78.046110 (2008).

Good, B. H., De Montjoye, Y. A. & Clauset, A. Performance of modularity maximization in practical contexts. Phys. Rev. E 81, 046106, https://doi.org/10.1103/PhysRevE.81.046106 (2010).

Thông tin
Thông tin xuất bản

Scientific Reports

Tập 9 Số 1

Thông tin tác giả