Preferential attachment and neutral random graphs: statistically useful generative models of network data

Preferential attachment (PA) and other probabilistic generative models of network growth have been popular for their ability to explain large-scale phenomena from simple interaction mechanisms. However, PA has been of limited use as a statistical model, due to its lack of exchangeability: in a statically observed network with n edges, inference requires considering all n! possible edge arrival orders. Moreover, in models based on forms of exchangeability, inference algorithms benefit from an edge-decoupled representation, in which all dependence between edges is captured by some latent quantity; no such representation is known for PA models. I will describe my work toward making PA useful as a statistical model: an edge-decoupled representation for a class of generalized PA models is established, and it reveals probabilistic structure, called left-neutrality, that can be exploited for efficient inference algorithms even in the presence of unknown edge arrival order. Furthermore, the edge-decoupled representation endows the PA model with a set of interpretable model parameters. Finally, I will describe how exchangeability still plays a role, despite PA's non-exchangeability.

This work was done in collaboration with Christian Borgs, Jennifer T. Chayes, Adam Foster, Emile Mathieu, Peter Orbanz, and Yee Whye Teh.