A Bayesian model for sparse graphs with flexible degree distribution and overlapping community structure

Juho Lee, Lancelot James, Seungjin Choi, Francois Caron
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:758-767, 2019.

Abstract

We consider a non-projective class of inhomogeneous random graph models with interpretable parameters and a number of interesting asymptotic properties. Using the results of Bollobás et al. (2007), we show that i) the class of models is sparse and ii) depending on the choice of the parameters, the model is either scale-free, with power-law exponent greater than 2, or with an asymptotic degree distribution which is power-law with exponential cut-off. We propose an extension of the model that can accommodate an overlapping community structure. Scalable posterior inference can be performed due to the specific choice of the link probability. We present experiments on five different real world networks with up to 100,000 nodes and edges, showing that the model can provide a good fit to the degree distribution and recovers well the latent community structure.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-lee19b, title = {A Bayesian model for sparse graphs with flexible degree distribution and overlapping community structure}, author = {Lee, Juho and James, Lancelot and Choi, Seungjin and Caron, Francois}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {758--767}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/lee19b/lee19b.pdf}, url = {https://proceedings.mlr.press/v89/lee19b.html}, abstract = {We consider a non-projective class of inhomogeneous random graph models with interpretable parameters and a number of interesting asymptotic properties. Using the results of Bollobás et al. (2007), we show that i) the class of models is sparse and ii) depending on the choice of the parameters, the model is either scale-free, with power-law exponent greater than 2, or with an asymptotic degree distribution which is power-law with exponential cut-off. We propose an extension of the model that can accommodate an overlapping community structure. Scalable posterior inference can be performed due to the specific choice of the link probability. We present experiments on five different real world networks with up to 100,000 nodes and edges, showing that the model can provide a good fit to the degree distribution and recovers well the latent community structure.} }
Endnote
%0 Conference Paper %T A Bayesian model for sparse graphs with flexible degree distribution and overlapping community structure %A Juho Lee %A Lancelot James %A Seungjin Choi %A Francois Caron %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-lee19b %I PMLR %P 758--767 %U https://proceedings.mlr.press/v89/lee19b.html %V 89 %X We consider a non-projective class of inhomogeneous random graph models with interpretable parameters and a number of interesting asymptotic properties. Using the results of Bollobás et al. (2007), we show that i) the class of models is sparse and ii) depending on the choice of the parameters, the model is either scale-free, with power-law exponent greater than 2, or with an asymptotic degree distribution which is power-law with exponential cut-off. We propose an extension of the model that can accommodate an overlapping community structure. Scalable posterior inference can be performed due to the specific choice of the link probability. We present experiments on five different real world networks with up to 100,000 nodes and edges, showing that the model can provide a good fit to the degree distribution and recovers well the latent community structure.
APA
Lee, J., James, L., Choi, S. & Caron, F.. (2019). A Bayesian model for sparse graphs with flexible degree distribution and overlapping community structure. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:758-767 Available from https://proceedings.mlr.press/v89/lee19b.html.

Related Material