Affiliation networks

Abstract

In the last decade, structural properties of several natu- rally arising networks (the Internet, social networks, the web graph, etc.) have been studied intensively with a view to understanding their evolution. In recent empirical work, Leskovec, Kleinberg, and Faloutsos identify two new and surprising properties of the evolution of many real-world net- works: densification (the ratio of edges to vertices grows over time), and shrinking diameter (the diameter reduces over time to a constant). These properties run counter to con- ventional wisdom, and are certainly inconsistent with graph models prior to their work. In this paper, we present the first model that provides a simple, realistic, and mathematically tractable generative model that intrinsically explains all the well-known pro- perties of the social networks, as well as densification and shrinking diameter. Our model is based on ideas studied empirically in the social sciences, primarily on the ground- breaking work of Breiger (1973) on bipartite models of social networks that capture the affiliation of agents to societies. We also present algorithms that harness the structural consequences of our model. Specifically, we show how to overcome the bottleneck of densification in computing short- est paths between vertices by producing sparse subgraphs that preserve or approximate shortest distances to all or a distinguished subset of vertices. This is a rare example of an algorithmic benefit derived from a realistic graph model. Finally, our work also presents a modular approach to con- necting random graph paradigms (preferential attachment, edge-copying, etc.) to structural consequences (heavy-tailed degree distributions, shrinking diameter, etc.).