Sampling and Inference for Beta Neutral-to-the-Left Models of Sparse Networks

Benjamin Bloem-Reddy, Adam Foster, Emile Mathieu, Yee Whye Teh
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:476-485, 2018.

Abstract

Empirical evidence suggests that heavy-tailed degree distributions occurring in many real net- works are well-approximated by power laws with exponents $\eta$ that may take values either less than and greater than two. Models based on various forms of exchangeability are able to capture power laws with $\eta$ < 2, and admit tractable inference algorithms; we draw on pre- vious results to show that $\eta$ > 2 cannot be gen- erated by the forms of exchangeability used in existing random graph models. Preferential at- tachment models generate power law exponents greater than two, but have been of limited use as statistical models due to the inherent difficulty of performing inference in non-exchangeable models. Motivated by this gap, we design and implement inference algorithms for a recently proposed class of models that generates $\eta$ of all possible values. We show that although they are not exchangeable, these models have prob- abilistic structure amenable to inference. Our methods make a large class of previously in- tractable models useful for statistical inference.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-bloem-reddy18a, title = {Sampling and Inference for Beta Neutral-to-the-Left Models of Sparse Networks}, author = {Bloem-Reddy, Benjamin and Foster, Adam and Mathieu, Emile and Teh, Yee Whye}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {476--485}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/bloem-reddy18a/bloem-reddy18a.pdf}, url = {https://proceedings.mlr.press/r16/bloem-reddy18a.html}, abstract = {Empirical evidence suggests that heavy-tailed degree distributions occurring in many real net- works are well-approximated by power laws with exponents $\eta$ that may take values either less than and greater than two. Models based on various forms of exchangeability are able to capture power laws with $\eta$ < 2, and admit tractable inference algorithms; we draw on pre- vious results to show that $\eta$ > 2 cannot be gen- erated by the forms of exchangeability used in existing random graph models. Preferential at- tachment models generate power law exponents greater than two, but have been of limited use as statistical models due to the inherent difficulty of performing inference in non-exchangeable models. Motivated by this gap, we design and implement inference algorithms for a recently proposed class of models that generates $\eta$ of all possible values. We show that although they are not exchangeable, these models have prob- abilistic structure amenable to inference. Our methods make a large class of previously in- tractable models useful for statistical inference.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Sampling and Inference for Beta Neutral-to-the-Left Models of Sparse Networks %A Benjamin Bloem-Reddy %A Adam Foster %A Emile Mathieu %A Yee Whye Teh %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-bloem-reddy18a %I PMLR %P 476--485 %U https://proceedings.mlr.press/r16/bloem-reddy18a.html %V R16 %X Empirical evidence suggests that heavy-tailed degree distributions occurring in many real net- works are well-approximated by power laws with exponents $\eta$ that may take values either less than and greater than two. Models based on various forms of exchangeability are able to capture power laws with $\eta$ < 2, and admit tractable inference algorithms; we draw on pre- vious results to show that $\eta$ > 2 cannot be gen- erated by the forms of exchangeability used in existing random graph models. Preferential at- tachment models generate power law exponents greater than two, but have been of limited use as statistical models due to the inherent difficulty of performing inference in non-exchangeable models. Motivated by this gap, we design and implement inference algorithms for a recently proposed class of models that generates $\eta$ of all possible values. We show that although they are not exchangeable, these models have prob- abilistic structure amenable to inference. Our methods make a large class of previously in- tractable models useful for statistical inference. %Z Reissued by PMLR on 04 October 2026.
APA
Bloem-Reddy, B., Foster, A., Mathieu, E. & Teh, Y.W.. (2018). Sampling and Inference for Beta Neutral-to-the-Left Models of Sparse Networks. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:476-485 Available from https://proceedings.mlr.press/r16/bloem-reddy18a.html. Reissued by PMLR on 04 October 2026.

Related Material