基于孤立集的鲁汶社区发掘算法并行优化
Isolate Sets Based Parallel Louvain Method for Community Detection
-
摘要:研究背景 近年来,社交网络、智能推荐系统、生物化学研究以及金融贸易活动等场景产生了大量的复杂网络数据。区别于传统的结构化数据,这些复杂网络数据通常是以图的形式进行存储和计算,因此涌现出了众多图算法,其中社区发掘算法是一种重要的基础性图算法。通过社区发掘,人们将图中的节点划分形成一个个新的节点社区,使得同一社区内的节点间联系相对紧密,不同社区的节点间联系相对松散。根据数学基础的不同,社区发掘的方法有很多,本文关注的是一种基于模块度的社区发掘算法—鲁汶算法。由于鲁汶算法具有收敛速度快、社区发掘效果好以及能够层次化发掘等优点,在业内得到广泛应用。传统的鲁汶算法是典型的串行算法,在处理大规模甚至超大规模的图时具有极高的时间开销,很多情况下不能在给定的时间下完成任务。因此,研究者们提出了许多鲁汶算法的并行优化方法。然而,这些并行的鲁汶算法具有两个缺点:(1)社区信息的更新和同步具有延迟,影响算法的收敛速度;(2)社区发掘过程中产生社区节点交换,影响算法的收敛速度和最终的社区发掘质量。目的 为了克服传统并行鲁汶算法的两个缺点,我们提出了一种基于孤立集划分的并行鲁汶算法。该算法具有以下特点:(1)能够将图中节点进行拓扑解耦,降低节点间的信息同步开销;(2)减少甚至避免信息更新延迟,加速并行算法收敛;(3)通过图分割限制节点间相对移动,提高计算效率并改善社区发掘质量。方法 以往的并行鲁汶算法没有将图上节点进行拓扑解耦,而本方法在社区发掘前根据图中节点的拓扑关系将图划分为若干个孤立集。孤立集的定义为图中没有相同邻居节点的节点形成的集合,因此同一个孤立集中的节点互相解耦。这些孤立集覆盖了图中的所有节点,而且任意两个孤立集的交集都是空集,保证了任意一个图中的节点必定属于且仅属于某一个孤立集。在基于孤立集的鲁汶算法并行社区发掘的过程中,同一个孤立集中的节点进行并行计算,然后串行的遍历这若干个孤立集并迭代,直到算法收敛。这些孤立集中的节点分布具有“长尾效应”,较少的孤立集节点数量会影响并行计算的效率。为了进一步的提高并行计算的效率,我们在基于孤立集的并行鲁汶算法的基础上提出了融合方法。在融合方法中,将若干个节点数量较少的孤立集融合为一个节点规模更大的集合,在社区发掘的过程中,并行计算属于同一个集合中的节点,然后串行的遍历这若干个孤立集以及融合集并迭代,直到算法收敛。结果 通过划分孤立集,使得并行计算的节点互相解耦,显著降低了节点间的通讯开销,缩短了节点间信息同步更新带来的延迟,提高了收敛速度。由于孤立集节点间没有共同的邻居节点,天然地避免了节点相向移动带来的节点交换,提高了并行计算的效率且不同程度的改善了社区发掘的质量。我们在8物理核心的个人电脑上测试了18个不同的数据集,基于孤立集的并行鲁汶算法最高达到4.62x的加速比,而融合并行算法进一步取得了最高7.26x的加速比。社区发掘质量方面,在18个测试集其中的14个,我们的方法取得了高于串行算法的模块度。结论 现有的并行鲁汶算法具有节点信息更新延迟以及社区节点交换带来的影响并行计算效率和社区发掘质量的问题。为了克服这两个问题,我们提出了基于孤立集的鲁汶社区发掘算法的并行优化方法。首先我们提出了一种对图中节点进行拓扑解耦的图划分算法,将图中的节点划分为若干个孤立集。然后在划分的孤立集上,对解耦的节点进行并行社区发掘运算。之后,为了进一步提高孤立集上节点并行计算的效率,我们融合了节点数较少的孤立集形成一个含有较多节点的融合节点集合,并在孤立集和融合节点集上进行并行社区发掘。最后在18个不同的真实世界网络数据集上进行了实验,实验结果与理论预期较为相符,证明了我们的方法较好的解决了之前并行鲁汶算法存在的两个问题,加速了算法的收敛并一定程度的改善了社区发掘质量。Abstract: Community detection is a vital task in many fields, such as social networks and financial analysis, to name a few. The Louvain method, the main workhorse of community detection, is a popular heuristic method. To apply it to large-scale graph networks, researchers have proposed several parallel Louvain methods (PLMs), which suffer from two challenges: the latency in the information synchronization, and the community swap. To tackle these two challenges, we propose an isolate sets based parallel Louvain method (IPLM) and a fusion IPLM with the hashtables based Louvain method (FIPLM), which are based on a novel graph partition algorithm. Our graph partition algorithm divides the graph network into subgraphs called isolate sets, in which the vertices are relatively decoupled from others. We first describe the concepts and properties of the isolate set. Second we propose an algorithm to divide the graph network into isolate sets, which enjoys the same computation complexity as the breadth-first search. Third, we propose IPLM, which can efficiently calculate and update vertices information in parallel without latency or community swap. Finally, we achieve further acceleration by FIPLM, which maintains a high quality of community detection with a faster speedup than IPLM. Our two methods are for shared-memory architecture, and we implement our methods on an 8-core PC; the experiments show that IPLM achieves a maximum speedup of 4.62x and outputs higher modularity (maximum 4.76%) than the serial Louvain method on 14 of 18 datasets. Moreover, FIPLM achieves a maximum speedup of 7.26x.