We show how the mechanism of preferential attachment can emerge from an underlying network optimization framework. The preferential attachment
(PA) model so obtained has two novel features, saturation and viability,
which have natural interpretations in the underlying network. Like PA,
saturation has previously been assumed at an axiomatic level. The combination of PA and saturation leads to power-law degree distributions with exponential cutoff which give excellent fits to a broad range of empirical observations of networks. Here we show how a simple underlying optimization framework can give rise to both known mechanisms and likewise to a new concept of viability, and suggest that such models form a good starting point for the analysis of many networks. In addition we discuss the fit provided to a broad range of data, including previously unexplained data on the Internet obtained from "whois" tables.
This is joint work with Jennifer Chayes, Christian Borgs, Noam Berger and Bobby Kleinberg.
Audio (MP3 File, Podcast Ready)
Copyright. All Rights Reserved.