Abstract: Regular 3-SATisfiability (3-SAT) problem was an NP-hard problem. Studying alterations in the cluster structure of solutions to regular 3-SAT problem was undertaken to enhance comprehension of the difficulty involved in problem determination and distribution of satisfiable solutions. However, existing analysis models only studied a few discrete values near clustered phase transition point. Under different constraint densities, a unified analysis model was lacking to describe the structural evolution of solution clusters. To solve this problem, Phase Transition of Solution Cluster Structure (PSSM) was proposed. The main idea of this model was to obtain an initial solution of regular 3-SAT problem using WalkSAT algorithm and information propagation algorithm, construct a solution cluster of initial solution by using random walks, and analyze the solution cluster. Modularity and community were used to measure community structure, and structural entropy was used to measure the complexity of the solution cluster structure. Experimental results show that PSSM can accurately analyze the structural evolution process of solution clusters, and it is found that the phase transition point of regular 3-SAT problem instances is between 13 and 14, which is consistent with the phase transition point obtained using Zchaff solver, further verifying the effectiveness of PSSM.