Direction-optimizing label propagation and its application to community detection
Direction-optimizing label propagation and its application to community detection
复制标题
DOI：
10.1145/3387902.3392634
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Xu T. Liu;M. Halappanavar;K. Barker;A. Lumsdaine;A. Gebremedhin
中科院分区：
文献类型：
--
作者：
Xu T. Liu;M. Halappanavar;K. Barker;A. Lumsdaine;A. Gebremedhin
标签传播虽然通常称为用于分类的机器学习算法，但也是检测网络中社区的有效方法。我们提出了一个新的方向优化标签传播算法（DOLPA），该算法依赖于前沿和标签推拉和标签拉动操作之间的交替来增强标准标签传播算法（LPA）的性能。具体而言，DOLPA具有用于调整图表中顶点的处理顺序的参数，进而减少所访问的边缘数量并提高所获得的解决方案的质量。我们将DOLPA应用于社区检测问题，介绍算法的设计和实现，并使用OpenMP讨论其共享记忆并行化。从经验上讲，我们使用合成图和现实世界网络评估算法。与最先进的并行标签传播算法相比，我们至少达到了F-评分的两倍，同时将运行时减少了50％，用于具有重叠群落的合成图。我们还使用相同的图表将DOLPA与Louvain方法的最先进实现的状态进行了比较，并表明DOLPA在运行时的F-评分达到了F-评分的三倍。
Label Propagation, while more commonly known as a machine learning algorithm for classification, is also an effective method for detecting communities in networks. We propose a new Direction Optimizing Label Propagation Algorithm (DOLPA) that relies on the use of frontiers and alternates between label push and label pull operations to enhance the performance of the standard Label Propagation Algorithm (LPA). Specifically, DOLPA has parameters for tuning the processing order of vertices in a graph, which in turn reduces the number of edges visited and improves the quality of solution obtained. We apply DOLPA to the community detection problem, present the design and implementation of the algorithm, and discuss its shared-memory parallelization using OpenMP. Empirically, we evaluate our algorithm using synthetic graphs as well as real-world networks. Compared with the state-of-the-art Parallel Label Propagation algorithm, we achieve at least two times the F-Score while reducing the runtime by 50% for synthetic graphs with overlapping communities. We also compare DOLPA against state of the art parallel implementation of the Louvain method using the same graphs and show that DOLPA achieves about three times the F-Score at 10% the runtime.