This work addresses the important problem of the discovery and analysis of social networks from surveillance video. A computer vision approach to this problem is made possible by the proliferation of video data obtained from camera networks, particularly state-of-the-art Pan-Tilt-Zoom (PTZ) and tracking camera systems that have the capability to acquire high-resolution face images as well as tracks of people under challenging conditions. We perform ldquoopportunisticrdquo face recognition on captured images and compute motion similarities between tracks of people on the ground plane. To deal with the unknown correspondences between faces and tracks, we present a novel graph-cut based algorithm to solve this association problem. It enables the robust estimation of a social network that captures the interactions between individuals in spite of large amounts of noise in the datasets. We also introduce an algorithm that we call ldquomodularity-cutrdquo, which is an Eigen-analysis based approach for discovering community and leadership structure in the estimated social network. Our approach is illustrated with promising results from a fully integrated multi-camera system under challenging conditions over long period of time.