A social network graph partitioning algorithm based on double deep Q-Network

Abstract

Abstract With the rapid expansion of social networks, efficiently mining and analyzing massive graph data has become a fundamental challenge in social network research. Graph partitioning plays a pivotal role in enhancing the performance of such analyses. However, conventional graph partitioning methods predominantly rely on local structural information and often overlook the rich attribute information associated with vertices in social network graphs. To overcome this limitation, this paper introduces GP-DQN (Graph Partitioning via Double Deep Q-Network), a large-scale graph partitioning algorithm that jointly considers structural correlations, attribute disparities among user vertices, and partition load balancing. GP-DQN encodes partition load metrics and vertex attributes into vector representations and employs a Graph Convolutional Network (GCN) to aggregate both vertex features and neighborhood structures, thereby improving the accuracy and scalability of the partitioning process. A tailored reward function is designed to guide partitioning actions, where a Double Deep Q-Network (DDQN) predicts the expected partitioning rewards based on GCN-extracted features for assigning each vertex to different partitions. The partitioning strategy is iteratively optimized using both immediate and expected rewards, ultimately achieving balanced load distribution while minimizing the number of edge cuts. Experimental results demonstrate that GP-DQN produces well-balanced partitions with significantly fewer edge cuts, leading to enhanced computational efficiency within each partition.