Effective HIV prevention requires knowledge of the structure and dynamics of the social networks across which infections are transmitted. These networks most commonly comprise chains of sexual relationships, but in some populations, sharing of contaminated needles is also an important, or even the main mechanism that connects people in the network. Whereas network data have long been collected during survey interviews, new data sources have become increasingly common in recent years, because of advances in molecular biology and the use of partner notification services in HIV prevention and treatment programmes. We review current and emerging methods for collecting HIV-related network data, as well as modelling frameworks commonly used to infer network parameters and map potential HIV transmission pathways within the network. We discuss the relative strengths and weaknesses of existing methods and models, and we propose a research agenda for advancing network analysis in HIV epidemiology. We make the case for a combination approach that integrates multiple data sources into a coherent statistical framework.