Centre for Science and Technology Studies, Leiden University, Leiden, The Netherlands.
Sci Rep. 2019 Mar 26;9(1):5233. doi: 10.1038/s41598-019-41695-z.
Community 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.
社区发现通常用于理解大型复杂网络的结构。揭示社区结构最流行的算法之一是所谓的 Louvain 算法。我们表明，该算法存在一个主要缺陷，直到现在才被广泛注意到：Louvain 算法可能产生任意连接不良的社区。在最坏的情况下，社区甚至可能断开连接，特别是在迭代运行算法时。在我们的实验分析中，我们观察到高达 25%的社区连接不良，高达 16%的社区断开连接。为了解决这个问题，我们引入了 Leiden 算法。我们证明，Leiden 算法产生的社区保证是连通的。此外，我们证明，当应用 Leiden 算法进行迭代时，它会收敛到一个分区，其中所有社区的所有子集都被局部最优分配。此外，通过依赖快速局部移动方法，Leiden 算法比 Louvain 算法运行得更快。我们展示了 Leiden 算法在几个基准和真实网络中的性能。我们发现，Leiden 算法比 Louvain 算法更快，并且除了提供明确的保证外，还能揭示更好的分区。
