The Anopheles gambiae species complex comprises the primary vectors of malaria in much of sub-Saharan Africa. Most of the mating in these species occurs in swarms composed almost entirely of males. Intermittent, organized patterns in such swarms have been observed, but a detailed description of male-male interactions has not previously been available. We identify frequent, time-varying interactions characterized by periods of parallel flight in data from 8 swarms of Anopheles gambiae and 3 swarms of Anopheles coluzzii filmed in 2010 and 2011 in the village of Donéguébogou, Mali. We use the cross correlation of flight direction to quantify these interactions and to induce interaction graphs, which show that males form synchronized subgroups whose size and membership change rapidly. A swarming model with damped springs between each male and the swarm centroid shows good agreement with the correlation data, provided that local interactions represented by damping of relative velocity between males are included.