  Hyperbolic models can reproduce the heavy-tailed degree distribution, high
clustering, and hierarchical structure of empirical networks. Current
algorithms for finding the hyperbolic coordinates of networks, however, do not
quantify uncertainty in the inferred coordinates. We present BIGUE, a Markov
chain Monte Carlo (MCMC) algorithm that samples the posterior distribution of a
Bayesian hyperbolic random graph model. We show that combining random walk and
random cluster transformations significantly improves mixing compared to the
commonly used and state-of-the-art dynamic Hamiltonian Monte Carlo algorithm.
Using this algorithm, we also provide evidence that the posterior distribution
cannot be approximated by a multivariate normal distribution, thereby
justifying the use of MCMC to quantify the uncertainty of the inferred
parameters.
