Digital contact tracing has been suggested as an effective strategy for controlling an epidemic without severely limiting personal mobility. Here, we use smartphone proximity data to explore how social structure affects contact tracing of COVID-19. We model the spread of COVID-19 and find that the effectiveness of contact tracing depends strongly on social network structure and heterogeneous social activity. Contact tracing is shown to be remarkably effective in a workplace environment and the effectiveness depends strongly on the minimum duration of contact required to initiate quarantine. In a realistic social network, we find that forward contact tracing with immediate isolation can reduce an epidemic by more than 70%. In perspective, our findings highlight the necessity of incorporating social heterogeneity into models of mitigation strategies. Graphic abstract