As people continue to author and share increasing amounts of information in social media, the opportunity to leverage such information for relationship discovery tasks increases. In this paper, we describe a set of systems that mine, aggregate, and infer a social graph from social media inside an enterprise, resulting in over 73 million relationships between 450,000 people. We then describe SaNDVis, a novel visual analytics tool that supports people-centric tasks like expertise location, team building, and team coordination in the enterprise. We provide details of a 22-month-long, large-scale deployment to over 2,300 users from which we analyze longitudinal usage patterns, classify types of visual analytics queries and users, and extract dominant use cases from log and interview data. By integrating social position, evidence, and facets into SaNDVis, we demonstrate how users can use a visual analytics tool to reflect on existing relationships as well as build new relationships in an enterprise setting. © 2012 IEEE.