IT services delivery is a complex ecosystem that engages 100000s of system administrators in service delivery centers globally managing 1000s of IT systems on behalf of customers. Such large-scale hosting environments require a flexible identity management system to provision necessary access rights, in order to ensure compliance posture of an organization. A popular and effective access control scheme is Role Based Access Control (RBAC). Ideally, a role should correspond to a business function performed within an enterprise. Several role mining algorithms have been proposed which attempt to automate the process of role discovery. In this paper, we represent the user-permission assignments as a bi-partite graph with users/permissions as vertices and user-permission assignments as edges. Given a user-permission bi-partite graph, most role mining algorithms focus on discovering roles that cover all the user-permission assignments. We show that by relaxing the coverage requirement, one can improve the accuracy of role detection. We propose a parameterized definition of a role based on graph theoretical properties, and demonstrate that the role parameters can be controlled to balance the accuracy and coverage of the roles detected. Finally, we propose a heuristic to illustrate the efficacy of our approach and validate it on real and artificial organizational access control data. © 2012 IEEE.