First to Market is not Everything: Phase Transitions in Preferential Attachment with Fitness

Christian Borgs
Microsoft Research
Theory Group

Preferential attachment is probably the most widely used model to describe power law networks in economics, social science, or technology. In this model, the existing nodes in a network gain new neighbors with probability proportional to their current degree. But, as often observed, preferential attachment does not capture one important aspect of these networks: in real life, not all nodes are born equal, with their attractiveness only depending on their current degree. Instead, nodes tend to be born with different "fitnesses", so that fitter nodes have a good chance to attain high degrees, even though they start off with much lower degrees than vertices which were born earlier.

In talk, I present a rigorous analysis of "preferential attachment with fitness", a model suggested by Bianconi and Barabasi, in which the degree of a vertex is scaled by its quality to determine its attractiveness. This models has many interesting features, among them a phase transition related to the so-called Bose-Einstein Condensation in quantum mechanics, and a dynamic behavior in which the fitness of a node can be read off from the way its degree grows with time.

This is joint work with Jennifer Chayes, Constantinos Daskalakis and Sebastien Roch.

Audio (MP3 File, Podcast Ready)

Back to Workshop III: Random and Dynamic Graphs and Networks