Most primates are intensely social and spend a large amount of time servicing social relationships. In this study, we use social network analysis to examine the relationship between primate group size, total brain size, neocortex ratio and several social network metrics concerned with network cohesion. Using female grooming networks from a number of Old World monkey species, we found that neocortex size was a better predictor of network characteristics than endocranial volumes. We further found that when we controlled for group size, neocortex ratio was negatively correlated with network density, connectivity, relative clan size and proportional clan membership, while there was no effect of neocortex ratio on change in connectivity following the removal of the most central female in the network. Thus, in species with larger neocortex ratios, females generally live in more fragmented networks, belong to smaller grooming clans and are members of relatively fewer clans despite living in a closely bonded group. However, even though groups are more fragmented to begin with among species with larger neocortices, the removal of the most central individual does cause groups to fall apart, suggesting that social complexity may ultimately involve the management of highly fragmented social groups while at the same time maintaining overall social cohesion. These results emphasize a need for more detailed brain data on a wider sample of primate species.