News & Events

Subscribe to email list

Please select the email list(s) to which you wish to subscribe.

User menu

You are here

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

Tuesday, January 15, 2019 - 11:00 to 12:00
Benjamin Bloem-Reddy
Statistics Seminar
Room 4192, Earth Sciences Building (2207 Main Mall)


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.