A basic problem in the design of role-based access control (RBAC) system is to automatically discover roles and configure user-role assignment and permission-role assignment. In order to achieve these objectives, researchers have proposed to discover roles from the existing user-permission assignments using data mining techniques, which is called role mining. But most of the existing role mining techniques do not consider the existing RBAC configurations and try to define everything from scratch. The definitions of similarity in the literature do not satisfy the commutative law. In this paper, we formally present a hybrid role mining method, providing deployed roles set using top-down approach and mining candidate role set using bottom-up approach. We propose the measures of weighted structural complexity for the optimality of the RBAC state. We also present the definitions of similarity of role sets for minimal perturbation that satisfy the commutative law and the similarity computation algorithm. Finally, the hybrid role mining algorithm with minimal perturbation is discussed. The algorithm’ computational complexity is analyzed and the effectiveness of the algorithm is evaluated. The evaluation results demonstrate the correctness and effectiveness of our approach.