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

Area of Science:

• Computer Science
• Network Analysis
• Artificial Intelligence

Background:

• Social network analysis faces challenges with large graph data mining.
• Traditional graph partitioning methods often ignore vertex attribute information.
• Efficient graph partitioning is crucial for scalable social network analysis.

Purpose of the Study:

• To develop a large-scale graph partitioning algorithm that integrates structural and attribute information.
• To improve the accuracy and scalability of graph partitioning in social networks.
• To enhance computational efficiency through balanced partitions with minimal edge cuts.

Main Methods:

• Introduced GP-DQN (Graph Partitioning via Double Deep Q-Network) algorithm.
• Utilized Graph Convolutional Network (GCN) for feature aggregation.
• Employed Double Deep Q-Network (DDQN) with a tailored reward function for optimization.

Main Results:

• GP-DQN achieved well-balanced partitions.
• Significantly reduced the number of edge cuts compared to conventional methods.
• Demonstrated enhanced computational efficiency within partitions.

Conclusions:

• GP-DQN offers an effective solution for large-scale graph partitioning in social networks.
• The joint consideration of structure, attributes, and load balancing improves partitioning quality.
• This approach enhances the performance of social network data analysis.