论文标题
通过快速标签传播大型网络社区检测
Large network community detection by fast label propagation
论文作者
论文摘要
许多网络都表现出一些社区结构。存在各种各样的方法来检测网络中的社区，每种都提供不同的解释和相关算法。对于大型网络，还有速度的其他要求。在这种情况下，提出了所谓的标签传播算法（LPA），该算法在接近线性的时间内运行。在LPA发现的分区中，确保每个节点都具有指定社区的大多数链接。我们在这里提出了LPA（FLPA）的快速变体，该变体基于处理最近发生变化的节点的队列。我们在基准网络和经验网络上详尽地测试了FLPA，发现它的运行速度比LPA快700倍。在FLPA发现的分区中，我们证明每个节点再次保证与其分配的社区具有大多数链接。我们的结果表明，FLPA通常比LPA更可取。
Many networks exhibit some community structure. There exists a wide variety of approaches to detect communities in networks, each offering different interpretations and associated algorithms. For large networks, there is the additional requirement of speed. In this context, the so-called label propagation algorithm (LPA) was proposed, which runs in near-linear time. In partitions uncovered by LPA, each node is ensured to have most links to its assigned community. We here propose a fast variant of LPA (FLPA) that is based on processing a queue of nodes whose neighbourhood recently changed. We test FLPA exhaustively on benchmark networks and empirical networks, finding that it can run up to 700 times faster than LPA. In partitions found by FLPA, we prove that each node is again guaranteed to have most links to its assigned community. Our results show that FLPA is generally preferable to LPA.
