Exploring temporal community evolution: algorithmic approaches and parallel optimization for dynamic community detection
Exploring temporal community evolution: algorithmic approaches and parallel optimization for dynamic community detection
复制标题
DOI：
10.1007/s41109-023-00592-1
复制
发表时间：
2023-09
影响因子：
2.2
通讯作者：
Naw Safrin Sattar;A. Buluç;Khaled Z. Ibrahim;S. Arifuzzaman
中科院分区：
文献类型：
--
作者：
Naw Safrin Sattar;A. Buluç;Khaled Z. Ibrahim;S. Arifuzzaman
动态（时态）图是许多实际复杂系统（包括社会联系、商业交易和计算机通信）的方便数学抽象。社区发现是一种广泛使用的图分析内核，具有丰富的静态图文献。然而，由于两个具体原因，动态环境中的社区发现具有挑战性。首先，时间社区的概念缺乏一个被广泛接受的形式化，只有有限的工作存在于理解社区如何随着时间的推移而出现。其次，随着现代图形数据的庞大规模，增加的时间维度沿着需要新的可扩展算法。在本文中，我们研究社区如何随着时间的推移，根据几个图度量的时间形式化。我们比较了六种不同的算法的动态社区检测的质量和运行时间。我们确定，一个顶点为中心的（本地）优化方法的工作效率为经典的基于模块化的方法。其优点是，这种本地计算允许并行算法的有效设计，而不会产生显着的并行开销。基于这一认识，我们设计了一个共享内存并行算法DyComPar，它在具有20个线程的多核机器上展示了4到18倍的速度，用于来自不同领域的几个真实世界和合成图。
Dynamic (temporal) graphs are a convenient mathematical abstraction for many practical complex systems including social contacts, business transactions, and computer communications. Community discovery is an extensively used graph analysis kernel with rich literature for static graphs. However, community discovery in a dynamic setting is challenging for two specific reasons. Firstly, the notion of temporal community lacks a widely accepted formalization, and only limited work exists on understanding how communities emerge over time. Secondly, the added temporal dimension along with the sheer size of modern graph data necessitates new scalable algorithms. In this paper, we investigate how communities evolve over time based on several graph metrics under a temporal formalization. We compare six different algorithmic approaches for dynamic community detection for their quality and runtime. We identify that a vertex-centric (local) optimization method works as efficiently as the classical modularity-based methods. To its advantage, such local computation allows for the efficient design of parallel algorithms without incurring a significant parallel overhead. Based on this insight, we design a shared-memory parallel algorithmDyComPar, which demonstrates between 4 and 18 fold speed-up on a multi-core machine with 20 threads, for several real-world and synthetic graphs from different domains.