Clustering-Guided Dynamic Social Network Graph Partitioning

Graph partitioning is a critical step in distributed computing for large-scale social network graphs, aiming to divide the graph into balanced partitions for downstream tasks. The structure and scale of real-world social network graphs continuously evolve, impacting the quality of graph partitions and, consequently, the performance of downstream tasks. Most existing methods adopt batch incremental partitioning or repartitioning strategies to process dynamic changes, but they often lack real-time processing capabilities and struggle to optimize partition quality. To mitigate these challenges, we propose a clustering-guided dynamic social network graph partitioning method (CG-DGP). In the first stage, we use streaming community detection combined with modularity evaluation to extract clustering information from the social network, enabling tightly connected vertices to be allocated to the same partition. In the second stage, dynamic changes are processed in real time via edge streaming, applying different partitioning strategies for high- and low-degree edges while optimizing partition quality in real time by reassigning edge groups. Experimental results demonstrate that CG-DGP efficiently generates state-of-the-art replication factors while maintaining load balance. The runtime for the downstream tasks of PageRank and connected components can be reduced by up to 9.68% and 10.89%, respectively.