Important sources of variation in the spread of HIV in communities arise from overlapping sexual networks and heterogeneity in biological and behavioral risk factors in populations. These sources of variation are not routinely accounted for in the design of HIV prevention trials. In this paper, we use agent-based models to account for these sources of variation. We illustrate the approach with an agent-based model for the spread of HIV infection among men who have sex with men in South Africa. We find that traditional sample size approaches that rely on binomial (or Poisson) models are inadequate and can lead to underpowered studies. We develop sample size and power formulas for community randomized trials that incorporate estimates of variation determined from agent-based models. We conclude that agent-based models offer a useful tool in the design of HIV prevention trials.