Từ Louvain đến Leiden: đảm bảo cộng đồng kết nối tốt
Tóm tắt
Phát hiện cộng đồng thường được sử dụng để hiểu cấu trúc của các mạng lưới lớn và phức tạp. Một trong những thuật toán phổ biến nhất để phát hiện cấu trúc cộng đồng là thuật toán Louvain. Chúng tôi chỉ ra rằng thuật toán này có một khuyết điểm lớn mà cho tới nay hầu như không được chú ý: thuật toán Louvain có thể tạo ra các cộng đồng kết nối kém một cách tùy ý. Trong trường hợp xấu nhất, các cộng đồng thậm chí có thể bị ngắt kết nối, đặc biệt là khi chạy thuật toán theo cách lặp đi lặp lại. Trong phân tích thử nghiệm của chúng tôi, chúng tôi quan sát thấy rằng có tới 25% các cộng đồng bị kết nối kém và lên tới 16% là bị ngắt kết nối. Để giải quyết vấn đề này, chúng tôi giới thiệu thuật toán Leiden. Chúng tôi chứng minh rằng thuật toán Leiden tạo ra các cộng đồng được đảm bảo là kết nối. Ngoài ra, chúng tôi chứng minh rằng, khi thuật toán Leiden được áp dụng theo cách lặp đi lặp lại, nó hội tụ về một phân hoạch trong đó tất cả các tập con của tất cả các cộng đồng được gán một cách tối ưu cục bộ. Hơn nữa, bằng cách dựa vào một phương pháp di chuyển cục bộ nhanh, thuật toán Leiden hoạt động nhanh hơn thuật toán Louvain. Chúng tôi chứng minh hiệu suất của thuật toán Leiden cho một số mạng lưới tham chiếu và thực tế. Chúng tôi nhận thấy rằng thuật toán Leiden nhanh hơn thuật toán Louvain và phát hiện ra các phân hoạch tốt hơn, ngoài việc cung cấp các đảm bảo rõ ràng.
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).