Background Cluster randomized trials have been utilized to evaluate the effectiveness of HIV prevention strategies on reducing incidence. Design of such studies must take into account possible correlation of outcomes within randomized units. Purpose To discuss power and sample size considerations for cluster randomized trials of combination HIV prevention, using an HIV prevention study in Botswana as an illustration. Methods We introduce a new agent-based model to simulate the community-level impact of a combination prevention strategy and investigate how correlation structure within a community affects the coefficient of variation - an essential parameter in designing a cluster randomized trial. Results We construct collections of sexual networks and then propagate HIV on them to simulate the disease epidemic. Increasing level of sexual mixing between intervention and standard-of-care (SOC) communities reduces the difference in cumulative incidence in the two sets of communities. Fifteen clusters per arm and 500 incidence cohort members per community provide 95% power to detect the projected difference in cumulative HIV incidence between SOC and intervention communities (3.93% and 2.34%) at the end of the third study year, using a coefficient of variation 0.25. Although available formulas for calculating sample size for cluster randomized trials can be derived by assuming an exchangeable correlation structure within clusters, we show that deviations from this assumption do not generally affect the validity of such formulas. Limitations We construct sexual networks based on data from Likoma Island, Malawi, and base disease progression on longitudinal estimates from an incidence cohort in Botswana and in Durban as well as a household survey in Mochudi, Botswana. Network data from Botswana and larger sample sizes to estimate rates of disease progression would be useful in assessing the robustness of our model results. Conclusion Epidemic modeling plays a critical role in planning and evaluating interventions for prevention. Simulation studies allow us to take into consideration available information on sexual network characteristics, such as mixing within and between communities as well as coverage levels for different prevention modalities in the combination prevention package.