Small-world properties emerge in highly compartmentalized networks with intermediate group sizes and numbers

Many recent studies have focused on two statistical properties observed in diverse real-world networks: the small-world property and compartmentalization [D. J. Watts and S. H. Strogatz, Nature 393, 440 (1998); M. Girvan and M. E. J. Newman, Proc. Natl. Acad. Sci. 99, 7821 (2002)]. Models that include group affiliations have been shown to produce networks with high clustering coefficients, a necessary condition for small-world properties [M. E. J. Newman, Phys. Rev. E, 68, 026121 (2003); M. E. J. Newman and J. Park, Phys. Rev. E 68, 036122 (2003)]. However, the consequences of varying the number and size of groups in a network are not well understood. In order to investigate the consequences of group organization, we examined sets of networks that varied simultaneously in the size and number of groups, while maintaining the same overall size and average degree. Here we show that the small-world property arises in maximally compartmentalized and clustered networks that occur in the intermediate region between few, very large groups and many, very small groups.