Exploring temporal community evolution: algorithmic approaches and parallel optimization for dynamic community detection

Applied Network Science

Research

Aydin Buluc¹  Khaled Z. Ibrahim¹  Naw Safrin Sattar²  Shaikh Arifuzzaman³ 

[1] Lawrence Berkeley National Laboratory, 94720, Berkeley, CA, USA;Oak Ridge National Laboratory, 37831, Oak Ridge, TN, USA;University of Nevada, 89154, Las Vegas, NV, USA;

关键词: Dynamic network;    Community detection;    Community evolution;    Temporal network;    Permanence;    Parallel algorithm;    Multi-threading;   

DOI  :  10.1007/s41109-023-00592-1

 received in 2023-05-30, accepted in 2023-09-07,  发布年份 2023

来源: Springer

【 摘 要 】

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 algorithm DyComPar, 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.

【 授权许可】

CC BY   
© Springer Nature Switzerland AG 2023

【 图 表 】

13690_2023_1170_Article_IEq157.gif

Fig. 2

Fig. 2

Fig. 4

13690_2023_1170_Article_IEq155.gif

Fig. 1

Fig. 5

Fig. 7

Fig. 11

Fig. 6

Fig. 7

40708_2023_202_Article_IEq25.gif

Fig. 3

Fig. 1

40677_2023_249_Article_IEq40.gif

41523_2023_572_Article_IEq1.gif

Fig. 1

Fig. 2

12888_2023_5172_Article_IEq48.gif

41408_2023_919_Article_IEq15.gif

Fig. 7

12888_2023_5172_Article_IEq40.gif

13690_2023_1177_Figc_HTML.png

12888_2023_5172_Article_IEq38.gif

13690_2023_1177_Figb_HTML.png

Fig. 2

41408_2023_919_Article_IEq4.gif

12888_2023_5172_Article_IEq30.gif

Fig. 5

Fig. 6

Fig. 3

Fig. 2

Fig. 1

Fig. 4

Fig. 1

Fig. 3

42004_2023_995_Article_IEq1.gif

Fig. 1

13690_2023_1170_Article_IEq94.gif

Fig. 4

Fig. 6

Fig. 5

Fig. 4

13690_2023_1170_Article_IEq219.gif

12888_2023_5172_Article_IEq1.gif

12888_2023_5142_Article_IEq25.gif

13690_2023_1170_Article_IEq196.gif

12888_2023_5142_Article_IEq8.gif

Fig. 5

Fig. 1

Fig. 2

Fig. 1

13690_2023_1170_Article_IEq173.gif

Fig. 1

12951_2023_2095_Article_IEq1.gif

Fig. 1

40798_2023_628_Figa_HTML.png