Categorization is the foundation of many cognitive functions. Importantly, the categories we use to structure the world are informed by the language we speak. For example, whether we perceive dark blue, light blue, and green to be shades of one, two, or three different colors depends on whether we speak Berinmo, English, or Russian, respectively. Different languages, then, differ by how granular their categories are, but the source of these differences is still poorly understood. Understanding the source of cross-linguistic differences in linguistic categorization is important because categorization influences communicative efficiency and cognitive performance. Here we use computational simulations to show that community structure and specifically community size and community interconnectivity influence the categorization systems that communities create. In particular, the simulations show that the obstacles for diffusion that large communities encounter push them to develop categorization systems that are more expressive and better understood, but only if they have sufficiently long memory to do so. The simulations also show that larger communities are better at creating useful references to rarely communicated meanings, thus further boosting communication in these cases. These findings demonstrate how taking social structure, and especially community size, into account can illuminate why languages evolved to have their current forms. They further show how social constraints, such as those encountered by large communities, can drive the creation of better and more robust systems. As categorization is a building block for many cultural products, these results also have implications for our understanding of cultural evolution more broadly.