标题： 通过半同步标签传播算法进行社区检测 显示英文标题

标题： Community Detection via Semi-Synchronous Label Propagation Algorithms

摘要： 一种最近引入的新的社区检测策略基于标签传播算法（LPA），该算法利用网络中的信息扩散来识别社区。 对LPA的研究表明，该策略在寻找良好的社区结构方面是有效的。 标签传播步骤可以在所有节点上并行执行（同步模型）或顺序执行（异步模型）；两种模型都存在一些缺点，例如，在第一种情况下算法终止无法保证，在第二种情况下性能可能更差。 在本文中，我们提出了一种半同步版本的LPA，旨在结合同步和异步模型的优点。 我们证明了我们的模型总是收敛到一个稳定的标记。 此外，我们通过实验研究了所提出策略的有效性，从质量、效率和稳定性三个方面将其性能与异步模型进行比较。 测试结果表明，所提出的协议不会损害划分的质量。 此外，它非常高效；每个传播步骤可以高度并行化，并且由于我们的方案只使用少量的随机化，因此比异步模型更稳定。 显示英文摘要

摘要： A recently introduced novel community detection strategy is based on a label propagation algorithm (LPA) which uses the diffusion of information in the network to identify communities. Studies of LPAs showed that the strategy is effective in finding a good community structure. Label propagation step can be performed in parallel on all nodes (synchronous model) or sequentially (asynchronous model); both models present some drawback, e.g., algorithm termination is nor granted in the first case, performances can be worst in the second case. In this paper, we present a semi-synchronous version of LPA which aims to combine the advantages of both synchronous and asynchronous models. We prove that our models always converge to a stable labeling. Moreover, we experimentally investigate the effectiveness of the proposed strategy comparing its performance with the asynchronous model both in terms of quality, efficiency and stability. Tests show that the proposed protocol does not harm the quality of the partitioning. Moreover it is quite efficient; each propagation step is extremely parallelizable and it is more stable than the asynchronous model, thanks to the fact that only a small amount of randomization is used by our proposal.