From Louvain to Leiden: guaranteeing well-connected communities
From Louvain to Leiden: guaranteeing well-connected communities
复制标题
DOI：
10.1038/s41598-019-41695-z
复制
发表时间：
2019-03-26
影响因子：
4.6
通讯作者：
van Eck, N. J.
中科院分区：
文献类型：
--
作者：
Traag, V. A.;Waltman, L.;van Eck, N. J.
社区检测常被用于理解大型复杂网络的结构。用于揭示社区结构的最流行算法之一是所谓的卢万算法。我们表明该算法存在一个重大缺陷，直到现在很大程度上都未被注意到：卢万算法可能产生连接性极差的社区。在最坏的情况下，社区甚至可能是不连通的，尤其是在迭代运行该算法时。在我们的实验分析中，我们观察到多达25%的社区连接性很差，多达16%的社区是不连通的。为了解决这个问题，我们引入了莱顿算法。我们证明莱顿算法产生的社区保证是连通的。此外，我们证明当莱顿算法迭代应用时，它会收敛到一个划分，其中所有社区的所有子集都是局部最优分配的。而且，通过依赖一种快速的局部移动方法，莱顿算法比卢万算法运行得更快。我们展示了莱顿算法在几个基准网络和现实世界网络中的性能。我们发现莱顿算法比卢万算法更快，能揭示出更好的划分，并且还提供了明确的保证。
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.