Random Clique Covers for Graphs with Local Density and Global Sparsity

Sinead A. Williamson, Mauricio Tec
Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, PMLR 115:228-238, 2020.

Abstract

Large real-world graphs tend to be sparse, but they often contain many densely connected subgraphs and exhibit high clustering coefficients. While recent random graph models can capture this sparsity, they ignore the local density, or vice versa. We develop a Bayesian nonparametric graph model based on random edge clique covers, and show that this model can capture power law degree distribution, global sparsity and non-vanishing local clustering coefficient. This distribution can be used directly as a prior on observed graphs, or as part of a hierarchical Bayesian model for inferring latent graph structures.

Cite this Paper

BibTeX
@InProceedings{pmlr-v115-williamson20a, title = {Random Clique Covers for Graphs with Local Density and Global Sparsity}, author = {Williamson, Sinead A. and Tec, Mauricio}, booktitle = {Proceedings of The 35th Uncertainty in Artificial Intelligence Conference}, pages = {228--238}, year = {2020}, editor = {Adams, Ryan P. and Gogate, Vibhav}, volume = {115}, series = {Proceedings of Machine Learning Research}, month = {22--25 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v115/williamson20a/williamson20a.pdf}, url = {https://proceedings.mlr.press/v115/williamson20a.html}, abstract = {Large real-world graphs tend to be sparse, but they often contain many densely connected subgraphs and exhibit high clustering coefficients. While recent random graph models can capture this sparsity, they ignore the local density, or vice versa. We develop a Bayesian nonparametric graph model based on random edge clique covers, and show that this model can capture power law degree distribution, global sparsity and non-vanishing local clustering coefficient. This distribution can be used directly as a prior on observed graphs, or as part of a hierarchical Bayesian model for inferring latent graph structures.} }
Endnote
%0 Conference Paper %T Random Clique Covers for Graphs with Local Density and Global Sparsity %A Sinead A. Williamson %A Mauricio Tec %B Proceedings of The 35th Uncertainty in Artificial Intelligence Conference %C Proceedings of Machine Learning Research %D 2020 %E Ryan P. Adams %E Vibhav Gogate %F pmlr-v115-williamson20a %I PMLR %P 228--238 %U https://proceedings.mlr.press/v115/williamson20a.html %V 115 %X Large real-world graphs tend to be sparse, but they often contain many densely connected subgraphs and exhibit high clustering coefficients. While recent random graph models can capture this sparsity, they ignore the local density, or vice versa. We develop a Bayesian nonparametric graph model based on random edge clique covers, and show that this model can capture power law degree distribution, global sparsity and non-vanishing local clustering coefficient. This distribution can be used directly as a prior on observed graphs, or as part of a hierarchical Bayesian model for inferring latent graph structures.
APA
Williamson, S.A. & Tec, M.. (2020). Random Clique Covers for Graphs with Local Density and Global Sparsity. Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, in Proceedings of Machine Learning Research 115:228-238 Available from https://proceedings.mlr.press/v115/williamson20a.html.

Related Material