Affiliation Networks
Venue
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, ACM (2009), pp. 427-434
Publication Year
2009
Authors
BibTeX
Abstract
In the last decade, structural properties of several naturally 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 networks: 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 conventional 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
properties 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 groundbreaking 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 shortest 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 connecting random graph paradigms (preferential
attachment, edge-copying, etc.) to structural consequences (heavy-tailed degree
distributions, shrinking diameter, etc.)
