The Cuban contact-tracing detection system set up in 1986 has made the collection of detailed epidemic data at the individual level possible. In this study, we reconstruct the related network (counting 5389 vertices and 4073 edges) and analyse its structure by means of recent developments in the field of graph theory, shedding light onto a variety of mechanisms underlying the spread of HIV and the role of contact-tracing. In particular, degree distributions, clustering/assortativity coefficients and path lengths are statistically measured. Because of the size of the graph (with a giant component of 2386 nodes and 3168 edges), basic graph representations fail to provide a clear view of the network structure. Clustering based on modularity optimization is implemented to detect community structures and obtain a better visualization and understanding of the social network, in combination with the study of the other covariates. It shows that the graph has a globally low but heterogeneous density, with some clusters of high intra-connectivity, but low inter-connectivity. Though descriptive, the results presented in this article pave the way for properly incorporating heterogeneity and structure in the dynamics of a stochastic SIR epidemic spreading on a social network.